LOADING

加载过慢请开启缓存,浏览器默认开启

daily 1

2023/5/1 daily

CF 575H

let ${dp[i][j]}$ denote the times one win i rounds and second win j rounds

then number of times is ${\sum{i=0}^{n}\sum{j=0}^{n}(C_{i+j}^j)}$

we could merge the second sum using some basic combo tricks

ll quick_pow(ll x,ll exp,int p)
{
      ll ans=1;
      while(exp)
      {
        if(exp&1)ans=ans*x%p;
        exp>>=1;
        x=x*x%p;
      }
      return ans;
}
ll inv[MAXN],fac[MAXN];
void init(int n,int p)
{
  memset(inv,0,sizeof(inv));
  memset(fac,0,sizeof(fac));
  inv[0]=fac[0]=1;
  for(int i=1;i<=n;++i)
  {
    fac[i]=fac[i-1]*i%p;
  }
  inv[n]=quick_pow(fac[n],p-2,p)%p;
  for(int i=n;i>=1;--i)inv[i-1]=inv[i]*i%p;
}
ll C(ll n,ll m,ll p)
{
  if(m>n||m<0)return 0;
  return fac[n]*inv[n-m]%p*inv[m]%p;
}
void solve(){
  int n;
  cin>>n;
  ll ans=0;
  for(int i=0;i<=n;++i){
    ans=(ans+C(i+n+1,i+1,MOD))%MOD;
  }
  ans%=MOD;
  cout<<ans<<'\n';
  return;
}