提供一个不一样的思路,就是硬着头皮做统计方案数背包。
有经验的老手会发现拼凑背包方案数$F[i+j]+=f1[i]×f2[j]$是一个卷积式。
然后我们可以想到$NTT$优化,复杂度$O(6mlog_2m)$。
这个做法优点如下:
- 可以统计方案数,不单是可行性
- 可以算任意体积方案数
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int ksm(int x,int y){
int s=1;
while(y){
if(y&1)s=s*x%mod;x=x*x%mod;y>>=1;
}
return s;
}
int G=3,G_inv=ksm(3,mod-2),Root;
int n,m,x,num[10],a[7][N],f[N],g[N],bit,tot,rev[N],F[N];
void NTT(int *a,int op){
for(int i=0;i<tot;i++)
if(i<rev[i])swap(a[i],a[rev[i]]);
int w1,w,L,R;
for(int mid=1;mid<tot;mid<<=1){
Root=(op==1?G:G_inv);
w1=ksm(Root,(mod-1)/(mid*2));
for(int i=0;i<tot;i+=mid*2){
w=1;
for(int j=i;j<i+mid;j++,w=w*w1%mod){
L=a[j];R=a[j+mid];
a[j]=(L+w*R%mod)%mod;
a[j+mid]=(L-w*R%mod+mod)%mod;
}
}
}
}
signed main(){
while(scanf("%d%d%d%d%d%d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6]),num[1]||num[2]||num[3]||num[4]||num[5]||num[6]){
m=0;
for(int i=1;i<=6;i++)m+=num[i]*i;
if(m%2){
printf("Can't\n");continue;
}
bit=0;
while((1<<bit)<=m)bit++;
tot=1<<bit;
for(int i=0;i<tot;i++){
rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
}
for(int i=1;i<=6;i++){
a[i][0]=1;
for(int j=1;j<=m;j++)a[i][j]=0;
for(int j=i;j<=num[i]*i&&j<=m;j+=i)a[i][j]=1;
}
for(int i=0;i<tot;i++)F[i]=0;F[0]=1;
for(int i=1;i<=6;i++){
for(int j=0;j<tot;j++)f[j]=g[j]=0;
for(int j=0;j<=m;j++)f[j]=F[j];
for(int j=0;j<=m;j++)g[j]=a[i][j];
NTT(f,1);NTT(g,1);
for(int j=0;j<tot;j++)f[j]=f[j]*g[j]%mod;
NTT(f,-1);
int inv=ksm(tot,mod-2);
for(int j=0;j<tot;j++)F[j]=f[j]*inv%mod;
}
printf("%s\n",F[m/2]?"Can":"Can't");
}
return 0;
}