【纪中集训2019.3.13】fft

题意：

描述

一共有\(n+m\)道题，其中\(n\)道答案是\(A\)，\(m\)道答案是\(B\)；

你事先知道\(n和m\),问在最优情况下的期望答错次数，对\(998244353\)取模；

范围

\(n,m \le 1e5\)

题解

• 考虑答对的期望次数；
• 显然最优策略是答个数多的那一个；
• 这样如果把状态写成一个 $n \times m $ 网格图，那么一个点的贡献 \({i,j}\) 就是 \(max(i,j)\) ;
• 考虑所有从\((0,0)\)走到\((n,m)\)的方案的和，答案就是

\[ \begin{align} n + m - \frac{\sum_{i=0}^{n} \sum_{j=0}^{m} \frac{max(i,j)}{i+j}C_{i+j}^{i}C_{n-i+m-j}^{n-i} }{C_{n+m}^{n}} (i+j!=0) \end{align} \]

• 然后我就去特别死板的化式子。。。。。。，浪费了很多时间；

• 答案也确实是一个比较特别的式子 ：
  \[ n - \frac{ \sum_{i=0}^{n} C^{i}_{2i}C^{n-i}_{n+m-2i} }{2C_{n+m}^{n}} (n<=m) \]

• 考虑实际意义，对于一个实际的路径，在\(i!=j\)的点一定是可以知道回答什么，所以一定不会错，即会答对\(max(n,m)\)次

• 而在\(i==j\)的点会随便回答一个，答对的次数是\(1/2\)；

• 所以去掉一个\(max(n,m)\)之后只考虑所有\(i==j\)的点\(O(n)\)计算；

  #include<bits/stdc++.h>
  #define ll long long
  #define mod 998244353
  using namespace std;
  const int N=1000010;
  int n,m,fac[N],ifac[N],inv[N];
  int cal(int x,int y){return (ll)fac[x+y]*ifac[x]%mod*ifac[y]%mod;}
  int cal2(int x,int y){return (ll)fac[x]*fac[y]%mod*ifac[x+y]%mod;}
  int main(){
    freopen("fft.in","r",stdin);
    freopen("fft.out","w",stdout);
    scanf("%d%d",&n,&m);
    fac[0]=ifac[0]=1;
    for(int i=1;i<=n+m;++i){
        if(i==1)inv[i]=1;else inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
        fac[i]=(ll)fac[i-1]*i%mod;
        ifac[i]=(ll)ifac[i-1]*inv[i]%mod;
    }
    int ans=0;
    /*
    for(int i=0;i<=n;++i)
    for(int j=0;j<=m;++j)if(i==j)*/
    for(int i=1;i<=n&&i<=m;++i){
        int j=i;
        ans = (ans + (ll)max(i,j) * inv[i+j] %mod * cal(i,j) %mod * cal(n-i,m-j) %mod )%mod;    
    //  ans = (ans + (ll)min(i,j) * inv[i+j] %mod * cal(i,j) %mod * cal(n-i,m-j) %mod )%mod;
    }
    ans = (ll)( min(n,m)  - (ll)ans * cal2(n,m)%mod + mod)%mod;
  //    ans = ((ll)n + m - (ll)ans * cal2(n,m)%mod + mod)%mod;
  //    ans = ((ll)ans *cal2(n,m)%mod);
    cout << ans << endl;
    return 0;
  }

【纪中集训2019.3.13】fft

原文：https://www.cnblogs.com/Paul-Guderian/p/10533053.html