题解：P8478 「GLR-R3」清明
Union_of_Britain
·
·
题解
考试数据分治写挂了，，还发现 O(n3^{n/2}) 比 O(n^32^{n/2}) 快。
写出生成函数：
=\left[\prod x_i^{a_i}\right]\left.\prod _i\frac{\partial}{\partial y}\prod_{i-m\le k\le i}\frac{1}{1-x_ky}\right|_{y=1}\\
=\left[\prod x_i^{a_i}\right]\prod_i\prod_{i-m\le j\le i}\frac{1}{1-x_j}\sum_{i-m\le k\le i}\frac{x_k}{1-x_k}\\
设
F_i=\prod_{j\le i} \frac{1}{1-x_j}
则
ans=\left[\prod x_i^{a_i}\right]\left(\prod_{n-m\le i\le n}F_i\right)\left(\prod _i \sum_{i-m\le k\le i}\frac{x_k}{1-x_k}\right)
后半部分相当于每个 i 选择一个 k，然后贡献只跟每个 k 被选择的次数相关，且事实上等于乘积，即设被选择次数为 c_{1:n}，造成贡献是
\prod_i f_{i,c_i}
当 $m\le \frac n2$ 时，直接状压 dp 并使用子集卷积获得 $O(n^32^{n/2})$ 的复杂度。当 $m>\frac n2$ 时，对后 $n-m-1$ 个位置状压，前面的 $m+1$ 位置 $i$ 可以钦定任意 $j\le i$ ，因此前面部分可以背包记录。这部分的复杂度也是 $O(n^32^{n/2})$。
最终复杂度 $O(n^32^{n/2})$，实际上子集卷积不如暴力转移快。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
namespace FWT{
// #define Poly vector<int>
int n,A[(1<<17)+5],B[(1<<17)+5],C[(1<<17)+5];
void work(){
int sz=0,len=1<<n;
for(int S=0;S<len;++S) sz+=(A[S]>0);
for(int S=0;S<len;++S) sz-=(B[S]>0);
if(sz>0) for(int i=0;i<len;++i) swap(A[i],B[i]);
for(int S=0;S<len;++S)
if(A[S]){
int v=A[S],TT=len-S-1;
for(int T=TT;~T;T=(T-1)&TT){
if(B[T]) C[S+T]=(C[S+T]+v*B[T])%mod;
if(!T) break;
}
}
}
void clear(){
for(int j=0;j<(1<<FWT::n);j++)FWT::A[j]=FWT::B[j]=FWT::C[j]=0;
}
}
int f[40][40],F[40][(1<<17)+5],n,m,a[40],g[2][40][(1<<16)+5];
int qp(int a,int b){
if(b==0)return 1;
int T=qp(a,b>>1);T=T*T%mod;
if(b&1)T=T*a%mod;
return T;
}
int C(int a,int b){
int z=1;
for(int i=a;i>=a-b+1;i--)z=z*i%mod;
for(int i=1;i<=b;i++)z=z*qp(i,mod-2)%mod;
z=(z%mod+mod)%mod;
return z;
}
inline int pop(int x){return __builtin_popcount(x);}
int high[(1<<17)+5],Ci[40][40];
int CL(int i){return min(n-i+1,m+1);}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int N=35;
for(int i=0;i<=N;i++){
Ci[i][0]=1;
for(int j=1;j<=i;j++)Ci[i][j]=(Ci[i-1][j]+Ci[i-1][j-1])%mod;
}
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
int b;
if(i<n-m)b=m;
else b=n-i;
for(int j=0;j<=min(m+1,a[i]);j++)f[i][j]=C(a[i]+b,b+j);
}
if(m==0){
int ans=1;
for(int i=1;i<=n;i++)ans=ans*f[i][1]%mod;
cout<<ans<<endl;
}else if(m<=14){
for(int j=0;j<(1<<m+1);j++){
high[j]=-1;
for(int k=0;k<m+1;k++)if(j&(1<<k))high[j]=k;
}
F[0][0]=1;
for(int i=1;i<=n;i++){
FWT::n=m+1;
for(int j=0;j<(1<<m+1);j++)FWT::A[j]=FWT::B[j]=FWT::C[j]=0;
for(int j=0;j<(1<<m+1);j++){
(FWT::A[j>>1]+=F[i-1][j])%=mod;
if(high[j]+i<=n)FWT::B[j]=f[i][pop(j)];
}
FWT::work();
for(int j=0;j<(1<<m+1);j++)F[i][j]=FWT::C[j];
for(int j=0;j<(1<<m+1);j++)if(!(j&1))F[i][j]=0;
}
int ans=0;
for(int i=0;i<(1<<m);i++)(ans+=F[n][i])%=mod;
cout<<ans<<endl;
}else{
F[n+1][0]=1;
for(int i=n;i>=m+2;i--){
int cl=min(n-i+1,m+1);
FWT::n=cl;
for(int j=0;j<(1<<cl);j++){
FWT::B[j]=f[i][pop(j)];
if(!(j&1))FWT::A[j]=F[i+1][j>>1];
}
FWT::work();
for(int j=0;j<(1<<cl);j++)F[i][j]=FWT::C[j];
FWT::clear();
}
int cur=0,lst=CL(m+2);
for(int j=0;j<(1<<CL(m+2));j++)g[0][0][j]=F[m+2][j];
for(int i=m+1;i>=1;i--){
int cl=min(n-m-1,i-1),c2=m+1-i;
for(int j=0;j<=c2;j++)for(int k=0;k<(1<<cl);k++){
if(lst>cl)g[cur][j][k]=0;
}
for(int j=0;j<=c2;j++)for(int k=0;k<(1<<lst);k++){
if(k>=(1<<cl)){
if((k|((1<<cl)-1))!=(1<<lst)-1)continue;
(g[cur][j][k&((1<<cl)-1)]+=g[cur][j][k])%=mod;
}
}
for(int j=0;j<(1<<cl);j++)for(int k=0;k<=m+2-i;k++)g[cur^1][k][j]=0;
for(int j=0;j<=c2;j++){
for(int k=0;k<=m+2-i-j;k++){
FWT::n=cl;
for(int t=0;t<(1<<cl);t++){
FWT::B[t]=f[i][pop(t)+k];
FWT::A[t]=g[cur][j][t];
}
FWT::work();
for(int t=0;t<(1<<cl);t++){
(g[cur^1][j+k][t]+=FWT::C[t]*Ci[m+2-i-j][k])%=mod;
}
FWT::clear();
}
}
lst=cl;
cur^=1;
}
int ans=g[cur][m+1][0];
cout<<ans<<endl;
}
return 0;
}
```
代码的 $m>14$ 部分可能在搬过来处理 $m\le 14$ 的时候会出现问题。