律师函警告
考虑容斥,减去至少一个cxk的
枚举有i个cxk,方案数:C(n-3*i,i)因为不相交,所以直接扣掉剩下3个,选择第一个开始的位置,一一对应
剩下的?随便,统计多了?
二项式反演!
需要计算:(a-i,b-i,c-i,d-i,n-4*i)
表示用a-i,b-i,c-i,d-i,填n-4*i的队列的不同方案数。
指数生成函数搞定。
O(4*500log500*(1000/4))
const int N=1005;int n,t[4];int h[N],f[N],g[N];ll ans;int jie[N],inv[N];int C[N][N];int calc(int p){ int goal=n-4*p; // cout<<" calc "<<<" goal "<
< =0;--i) inv[i]=mul(inv[i+1],i+1); C[0][0]=1; for(reg i=1;i<=N-3;++i){ C[i][0]=1; for(reg j=1;j<=i;++j){ C[i][j]=ad(C[i-1][j],C[i-1][j-1]); } } // cout<<" C,jie,inv"<