問題はこちら
No.498 ワープクリスタル (給料日編) - yukicoder
各クリスタルをni個使う時、それらを使う順序は(Σni)!/Π(ni!)通りある(重複順列)
Niが小さいので、各クリスタルを何個使うかを全探索すればよい。
for文を5重に書くのが面倒だったので以下では再帰で書いている
long fact[80],invfact[80],M=1e9+7; p[9],q[9],c[9],cnt[9]; x,y,n; dfs(k){ if(k==n){ int xx=0,yy=0,s=0,deno=1; for(int i=0;i<n;i++){ xx+=p[i]*cnt[i]; yy+=q[i]*cnt[i]; s+=cnt[i]; deno=deno*invfact[cnt[i]]%M; } if(xx==x&&yy==y)return fact[s]*deno%M; else return 0; }else{ int ret=0; for(int i=0;i<=c[k];i++){ cnt[k]=i; ret=(ret+dfs(k+1))%M;; } return ret; } } main(){ fact[0]=invfact[0]=1; for(int i=1;i<=75;i++){ fact[i]=fact[i-1]*i%M; int k=0; while((M*k+invfact[i-1])%i)k++; invfact[i]=(M*k+invfact[i-1])/i; //iが小さいのでナイーブに計算して間に合う } scanf("%d%d%d",&x,&y,&n); for(int i=0;i<n;i++)scanf("%d%d%d",p+i,q+i,c+i); printf("%d",dfs(0)); }
上では予め階乗を計算してテーブルを用意したが、毎回計算しても間に合う
各クリスタルを使う個数は15個以下、つまり4bitに収まるので、(4*5)bitを全探索すると考えればループは1つで済む
とりあえず短くなりそうな方針を、ということではじめに考えたのがこれ
M=1e9+7; c[9],a[99];long n,i,j,k,t,T,f,p,q,s,S; main(){ for(;~scanf("%d",a+n);n++); for(;i++<1<<n/3*4;){ //x個目のクリスタルを((1>>(x*4))&15)個使う f=1;//条件にあうかどうかのフラグ T=s=p=q=0; for(j=0;j<n/3;j++){ c[j]=t=i>>j*4&15; p+=t*a[3*j+3]; q+=t*a[3*j+4]; f&=t<=a[3*j+5]; s+=t; } if(p==a[0]&&q==a[1]&&f)for(T=1,j=0;j<n/3;j++){ //重複順列の計算 for(k=0;k++<c[j];){ T=(T*s--)%M; while(T%k)T+=M; T/=k; } } S+=T; } printf("%d",S%M); }
で、ちょっと考えるとここまではすぐ縮む
M=1e9+7; a[99];n,i,j,p,q,s,f; long T,S; main(t){ for(;~scanf("%d",a+n++);); for(;i++<1<<n/3*4;S+=T){//fを反転した for(f=T=s=p=q=j=0;j<n/3;p+=t*a[3*++j],q+=t*a[3*j+1],f|=t>a[3*j+2])s+=t=i>>j*4&15; if(!(p-a[0]|q-a[1]|f))for(T=1;j--;)for(t=i>>j*4&15;t;T=(T/t--*s--)%M)for(;T%t;T+=M); } printf("%d",S%M); }
ぐっとにらみながらループ圧縮
if(!(p-a[0]|q-a[1]|f))for(T=1;j--;)for(t=i>>j*4&15;t;T=(T/t--*s--)%M)for(;T%t;T+=M); //(T/t--*s--)%Mは0にならないので圧縮できる if(!(p-a[0]|q-a[1]|f))for(T=1;j--;)for(t=i>>j*4&15;t?T=T%t?T+M:(T/t--*s--)%M:0;); //前のループでtの値がいい感じになっていることがから1回目初期化を省略できるので圧縮できる if(!(p-a[0]|q-a[1]|f))for(T=1;t?T=T%t?T+M:(T/t--*s--)%M:(t=i>>--j*4-4&15,j);); for(T=1;p-a[0]|q-a[1]|f?0:t?T=T%t?T+M:(T/t--*s--)%M:(t=i>>--j*4-4&15,j);); //Tが必ず1になるので、ループ後のS+=TをS+=T*!jとしなければならなくなったが、Tの初期化と合わせて3B短縮
あとは、よく考えるとnの値がいらないことがわかるので
M=1e9+7; a[99];i,j,p,q,s,f; long T,S; main(t){ for(;~scanf("%d",a+j++);); for(;i++<1<<20;S+=T*!j){ for(f=s=p=q=j=0;j<5;p+=t*a[3*++j],q+=t*a[3*j+1],f|=t>a[3*j+2])s+=t=i>>j*4&15; for(T=1;p-a[0]|q-a[1]|f?0:t?T=T%t?T+M:(T/t--*s--)%M:(t=i>>--j*4-4&15,j);); } printf("%d",S%M); }
263B