yukicoder No.498 ワープクリスタル (給料日編)

問題はこちら
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