A. Accelerator

實質上就是求n個多項式相乘
$$(a_1+x)(a_2+x)\dots (a_n+x)$$
對于$[x^m]$的系數即是從$n$個選出$n?m$的乘積之和。

每次從$n$個選出$n?m$的概率顯然為
$$\frac{\left(\genfrac{}{}{0ex}{}{n}{m}\right)}{n!}$$

然后期望累加即可。

---

或者說求
$$(1+a_{1}x)(1+a_{2}x)\dots (1+a_{n}x)$$
對于$[x^m]$的系數即是從$n$個選出$m$的乘積之和。

#include<bits/stdc++.h>using namespace std; using ll=long long;const int N=300010; const int P=998244353; const int G=3,Gi=332748118; const int mod=998244353;int qmi(int a,int b) {int v=1;while(b){if(b&1) v=1ll*v*a%P;a=1ll*a*a%P;b>>=1;}return v; } int rev[N]; void NTT(int *a,int n,int inv) {for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);for(int mid=1;mid<n;mid<<=1){int Wn=qmi((inv==1)?G:Gi,(P-1)/(mid<<1));for(int i=0;i<n;i+=(mid<<1)){int w=1;for(int j=0;j<mid;j++,w=1ll*w*Wn%P){int x=a[i+j],y=1ll*w*a[i+j+mid]%P;a[i+j]=(x+y)%P;a[i+j+mid]=(x-y+P)%P;}}}if(inv==-1) {int invn=qmi(n,P-2);for(int i=0;i<n;i++) a[i]=1ll*a[i]*invn%P;} } //======================================================= int fact[N],infact[N]; void init() {fact[0]=1;for(int i=1;i<=100000;i++) fact[i]=1ll*i*fact[i-1]%mod;infact[100000]=qmi(fact[100000],mod-2);for(int i=99999;i;i--) infact[i]=1ll*infact[i+1]*(i+1)%mod; } int n,A[N],B[N],C[N]; int Mul(int *a,int *b,int n,int m,int *ans) {int bit=0,num=1;while(num<n+m+1) num<<=1,bit++;for(int i=0;i<num;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));for(int i=0;i<=n;i++) A[i]=a[i];for(int i=0;i<=m;i++) B[i]=b[i];for(int i=n+1;i<num;i++) A[i]=0;for(int i=m+1;i<num;i++) B[i]=0;NTT(A,num,1);NTT(B,num,1);for(int i=0;i<num;i++) C[i]=1ll*A[i]*B[i]%mod;NTT(C,num,-1);for(int i=0;i<=n+m;i++) ans[i]=C[i];return n+m; }int pool[N<<1],tot; struct Node {int *p,n;void init(int x){this->n=1;p=pool+tot;for(int i=0;i<=n;i++) p[i]=0;p[0]=x;p[1]=1;tot+=n+1;}void mul(const Node&o){n=Mul(p,o.p,n,o.n,p);} }; Node solve(int l,int r) {Node ans;if(l==r){int x;cin>>x;ans.init(x);return ans;}int mid=l+r>>1;ans=solve(l,mid);ans.mul(solve(mid+1,r));return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);init();int Tc;cin>>Tc;while(Tc--){cin>>n;Node res=solve(1,n);ll ans=0;for(int i=1;i<=n;i++)ans=(ans+1ll*res.p[n-i]*fact[i]%mod*fact[n-i]%mod)%mod;ans=ans*infact[n]%mod;printf("%lld\n",ans);}return 0;}

總結

以上是生活随笔為你收集整理的The 2020 ICPC Asia Macau Regional Contest A. Accelerator（分治+NTT）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。