CCPC 2016 G Marriage（HDU6270） 组合数学：容斥原理+NTT+启发式合并
呜呜呜，为什么我长春CCPC，知乎上出题人的题解都咕着，我写了I的题解，结果没人看呢，PTA只有4A，不会是都不补题吧T_T（其实是百度不到我）。本来想蹭一波阅读量，大失败。
咳咳，回到正题。
题目意思是，一个城市里总共有N个家庭，第i个家庭有ai个男孩和bi个女孩，已知城市里男女比例1：1，在不近亲结婚且异性恋情况下，共有多少种不同的婚配方法（有一个人配偶不同即不同）
对于每个家庭，我们可以得到至少有i对近亲配对的方法。从而得到一个生成函数。对于这n个多项式，我们乘起来就得到了，城市里至少有i对近亲结婚的方法。我们可以用容斥原理计算，这里需要注意的是，不要忘记了给剩下的人配对，即总共有N对。对至少有i对近亲结婚的方法，要乘上（N-i）！
一开始WA了好多发，后来发现。。。我优先队列没pop干净，不过我塞了n个，每次取两个再塞一个进行n-1次，为什么我只pop一个没pop干净呢？疑惑。。。
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const long long MOD=998244353; 4 const long long g=3; 5 vector <long long> c[300010]; 6 long long x1[300010],x2[300010],p[300010],inv[300010],invp[300010],rev[200010],t,sum,a[100010],b[100010]; 7 long long ksm(long long x,long long y) 8 { 9 long long res=x; 10 long long ans=1; 11 while (y) 12 { 13 if (y&1) ans=ans*res%MOD; 14 res=res*res%MOD; 15 y=y>>1; 16 } 17 return ans; 18 } 19 struct cmp 20 { 21 bool operator()(int x, int y) 22 { 23 return c[x].size()>c[y].size(); 24 } 25 };priority_queue <long long,vector<long long>,cmp> q; 26 void init() 27 { 28 p[0]=1; 29 for (int i=1;i<=300000;i++) 30 { 31 p[i]=p[i-1]*i%MOD; 32 } 33 inv[1]=1; 34 for(int i=2;i<=300000;i++) 35 { 36 inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD; 37 } 38 invp[0]=1; 39 invp[1]=1; 40 for (int i=2;i<=300000;i++) 41 { 42 invp[i]=invp[i-1]*inv[i]%MOD; 43 } 44 } 45 long long C(long long x,long long y) 46 { 47 return (p[x]*invp[y]%MOD)*invp[x-y]%MOD; 48 } 49 inline void NTT(long long *z,long long len,long long invv) 50 { 51 long long bit=0; 52 while ((1<<bit)<len) 53 { 54 ++bit; 55 } 56 for(int i=0;i<=len-1;i++) 57 { 58 rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1)); 59 if (i<rev[i])swap(z[i],z[rev[i]]); 60 } 61 for (int mid=1;mid<len;mid*=2) 62 { 63 long long tmp=ksm(g,(MOD-1)/(mid*2)); 64 if (invv==-1) tmp=ksm(tmp,MOD-2); 65 for (int i=0;i<len;i+=mid*2) 66 { 67 long long omega=1; 68 for (long long j=0;j<mid;++j,omega=omega*tmp%MOD) 69 { 70 long long x=z[i+j],y=omega*z[i+j+mid]%MOD; 71 z[i+j]=(x+y)%MOD; 72 z[i+j+mid]=(x-y+MOD)%MOD; 73 } 74 } 75 } 76 if (invv==-1) 77 for (int i=0;i<len;i++) 78 { 79 z[i]=z[i]*inv[len]%MOD; 80 } 81 } 82 void mul(vector<long long> &x,vector<long long> &y,vector<long long> &z) 83 { 84 long long len=1; 85 while (len<x.size()+y.size()) 86 { 87 len=len<<1; 88 } 89 for (int i=0;i<x.size();i++) 90 { 91 x1[i]=x[i]; 92 } 93 for (int i=x.size();i<len;i++) 94 { 95 x1[i]=0; 96 } 97 for (int i=0;i<y.size();i++) 98 { 99 x2[i]=y[i]; 100 } 101 for (int i=y.size();i<len;i++) 102 { 103 x2[i]=0; 104 } 105 NTT(x1,len,1); 106 NTT(x2,len,1); 107 for (int i=0;i<len;i++) 108 { 109 x1[i]=x1[i]*x2[i]%MOD; 110 } 111 NTT(x1,len,-1); 112 for (int i=0;i<x.size()+y.size()-1;i++) 113 { 114 z.push_back(x1[i]); 115 } 116 } 117 int main() 118 { 119 long long t,n,i,j,flag,ans; 120 init(); 121 scanf("%lld",&t); 122 while (t--) 123 { 124 scanf("%lld",&n); 125 for (i=0;i<=n*2;i++) 126 { 127 c[i].clear(); 128 } 129 sum=0; 130 for (i=1;i<=n;i++) 131 { 132 scanf("%lld%lld",&a[i],&b[i]); 133 sum=sum+a[i]; 134 for (j=0;j<=b[i]&&j<=a[i];j++) 135 { 136 c[i].push_back((C(a[i],j)*C(b[i],j)%MOD)*p[j]%MOD); 137 } 138 q.push(i); 139 } 140 for (i=n+1;i<n*2;i++) 141 { 142 int x=q.top();q.pop(); 143 int y=q.top();q.pop(); 144 mul(c[x],c[y],c[i]); 145 q.push(i); 146 } 147 while (!q.empty()) q.pop(); 148 flag=1; 149 ans=0; 150 for (i=0;i<c[n*2-1].size();i++) 151 { 152 ans=ans+flag*p[sum-i]*c[n*2-1][i]%MOD; 153 ans=(ans+MOD)%MOD; 154 flag=0-flag; 155 } 156 ans=(ans+MOD)%MOD; 157 printf("%lld ",ans); 158 } 159 return 0; 160 }
后记：明天JSCPC啦，早睡早睡。疫情之下，第一场线下赛。