2024.10.30 2022CCPC女生赛 D. Devil May Cry
题意
求长度为 \(n\)，元素为 \(1\) 到 \(m\) 之间的整数，且满足下面两个条件的序列的数量：
- \(i\) 的出现次数不超过 \(l_i\)
- \(a_{p_i}\neq s_i, \forall i=1,\dots,r\)
\(n\leq 20 ,m\leq 100, r\leq 1000\)
前置知识 1. 子集卷积
首先本题有一个简单的状压 dp 做法：枚举 i 出现的位置集合，然后
这个做法复杂度是 \(O(m3^n)\)，显然是过不了的。
我们令 \(F_i(x) = \sum_{S}[S\cap T_i=\emptyset][|S|\leq l_i]x^S\)，则答案为\([x^U]\prod_{i=1}^m F_i(x)\)。\(U\) 表示全集。
注意这里的卷积是子集卷积而不是子集或卷积。二者的区别
即子集卷积要求没有重复元素。
子集卷积的一般做法是，将 \(F_i(x)\) 的系数改为 \(n\) 次多项式，\(x^Sy^k\) 的系数是集合为 \(S\)，集合元素数量（重复元素算多次）为 \(k\) 的方案数。则 \(F_i(x,y)=\sum_S[S\cap T_i=\emptyset][|S|\leq l_i]x^Sy^{|S|}\)。这样最后 \(x^Uy^n\) 的系数就是最终答案了。
加一维的好处是，我们已经把无法优化的子集卷积转化为可以用 FWT 优化的子集或卷积了。只不过子集或卷积的系数都是多项式。单次子集或卷积的加减次数为 \(O(n2^n)\)，而多项式的加减复杂度是 \(O(n)\)，所以子集卷积的复杂度为 \(O(n^22^n)\)。
总复杂度从 \(O(m3^n)\) 优化到了 \(O(mn^22^n)\)，还是无法通过 \(n=20\) 的数据。
PS：子集卷积的另一道板题是 [WC2018]州区划分
前置知识 2. 集合幂级数的对数和指数运算
系数是整数的集合幂级数是无法定义对数和指数运算的（log 和 exp 在模剩余系下没有定义）。但本题集合幂级数的系数都是多项式，因此可借助多项式的对数和指数运算定义和计算。
定义一个集合幂级数 \(F\) 的对数级数为（要求常数项为 1）：
这个级数有意义是因为\(k>n\)时\((F-1)^k\)就是0了。
同理可以定义指数级数为（要求常数项为 0）：
同样的，\(k>n\) 时 \(F^k\) 就是0了，所以级数是有意义的。
集合幂级数的对数和指数怎么算呢？很简单，FWT一遍，然后对 \(2^n\) 个多项式分别求对数或指数，再IFWT一遍，就结束了。
现在回到原题。我们需要计算 \(\prod_{i=1}^m F_i(x)\)，那么因为 log 和 exp 可以把连乘和连加互相转化，所以即计算 \(\exp(\sum_{i=1}^m\log F_i(x))\)。那么我们只需快速计算所有 \(\log F_i(x)\) 即可。
——我会多项式全家桶！只需\(O(2^nn\log n)\) 就能计算 \(\log F_i\) 了。
——醒醒，\(n\leq 20\)。多项式全家桶跑不过暴力递推。
关于 log 和 exp 的暴力递推求法（当然不是硬上定义式求），可以记下这个公式：
那么直接暴力还是 \(O(mn^22^n)\) 的（要做 \(m2^n\) 次多项式 log）。如何进一步优化呢？
本题题解
我们把上面的算法流程写下来，看看能发现什么。
Poly F[M][S],ans[S];
int main(){
// 算 F
for(int i=1;i<=m;++i){
FWT(F[i]);
for(int j=0;j<1<<n;++j)
Log(F[i][j]);
IFWT(F[i]);
for(int j=0;j<1<<n;++j)
ans[j]+=F[i][j];
}
FWT(ans);
for(int j=0;j<1<<n;++j)Exp(ans[j]);
IFWT(ans);
cout<<ans[(1<<n)-1][n]<<endl;
}
看瓶颈部分。我们需要对所有的 \(i,S\) 计算 \(\log([x^S]FWT(F_i))\)。
因此，本质不同的 \([x^S]FWT(F_i)\) 只有 \(O(n^2)\) 种。我们可以预处理出这些多项式的 log。这样需要用的时候直接取出来即可。
另外，因为 FWT 是线性的，所以 log 的 IFWT 和 exp 的 FWT 可以抵消掉。这样我们就优化掉了对 \(F_i\) 的所有变换。
总复杂度 \(O(n^4+mn2^n+n^22^n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=21,M=105,S=1<<20,mod=998244353;
int sub(int x,int y){return x^(x&y);}
ll inv[N],c[N][N];
valarray<ll> Log(const valarray<ll>& f){
int n=f.size()-1;
valarray<ll> g(n+1);
for(int i=1;i<=n;++i){
ll tmp=0;
for(int j=1;j<i;++j)
tmp=(tmp+j*g[j]%mod*f[i-j])%mod;
g[i]=(f[i]-inv[i]*tmp%mod+mod)%mod;
}
return g;
}
valarray<ll> Exp(const valarray<ll>& f){
int n=f.size()-1;
valarray<ll> g(n+1);
g[0]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j)
g[i]=(g[i]+j*f[j]%mod*g[i-j])%mod;
g[i]=g[i]*inv[i]%mod;
}
return g;
}
void FWT_OR(valarray<ll>* a,int n){
for(int k=1;k<n;k<<=1)
for(int i=0;i<n;i+=k<<1)
for(int j=0;j<k;++j)
(a[i+j+k]+=a[i+j])%=mod;
}
void IFWT_OR(valarray<ll>* a,int n){
for(int k=1;k<n;k<<=1)
for(int i=0;i<n;i+=k<<1)
for(int j=0;j<k;++j)
(a[i+j+k]+=mod-a[i+j])%=mod;
}
valarray<ll> g[N][N];
void init(int n){
inv[1]=1;
for(int i=2;i<=n;++i)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
for(int i=0;i<=n;++i){
c[i][0]=1;
for(int j=1;j<=i;++j)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j){
g[i][j].resize(n+1);
for(int t=0;t<=j;++t)g[i][j][t]=c[i][t];
g[i][j]=Log(g[i][j]);
}
}
int n,m,lim[M],q,t[M],x,y;
valarray<ll> f[S];
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
init(n);
for(int i=1;i<=m;++i)cin>>lim[i];
cin>>q;
while(q--)cin>>x>>y,--x,t[y]|=1<<x;
for(int i=0;i<1<<n;++i){
f[i].resize(n+1);
for(int j=1;j<=m;++j)
f[i]=(f[i]+g[__builtin_popcount(sub(i,t[j]))][lim[j]])%mod;
f[i]=Exp(f[i]);
}
IFWT_OR(f,1<<n);
cout<<f[(1<<n)-1][n]<<'\n';
}
valarray是个好东西。用起来有点py那味了（