题意我觉得还是好理解的。 我感觉就是有n*n堆石头,有n个人,每人挑个石堆站在后面。
三种操作:http://acm.hdu.edu.cn/showproblem.php?pid=4304
1. 人全部右移(石头不动)。
2. 人全部左移。
3. 将自己面前的石头全部用脑袋砸碎。
满足条件:
1.左右移的时候不能移出去,就是每人面前都得有一堆石头,无论是坏的还是好的。
2.砸的时候只能砸未砸过的石头。
最后将全部石头砸碎就行。 问第一堆石头必须有人站在后面的能成功的开始状态有几种。
然后题解就Orz,真不会了。莫名奇妙就转化成因数分解和排列了。
以下是多校解题报告:
这个问题等价于把N因数分解,不能有1
然后将序列交替组合的方案数算出来就可以了
比如6=2*3
我们有[6],[2,3],[3,2]
交替组合有
A6B6 B6A6
A2B6A3 A3B6A2 B2A6B3 B3A6B2
A2B2A3B3 A2B3A3B2 A3B3A2B2 A3B2A2B3
B2A2B3A3 B2A3B3A2 B3A3B2A2 B3A2B2A3
共14种
再比如8=2*2*2=2*4
我们有[8],[2,4],[4,2],[2,2,2]
交替组合有
A8B8 B8A8
A2B8A4 A4B8A2 B2A8B4 B4A8B2
A2B2A4B4 A2B4A4B2 A4B2A2B4 A4B4A2B2
B2A2B4A4 B2A4B4A2 B4A2B2A4 B4A4B2A2
A2B2A2B4A2 A2B4A2B2A2 B2A2B2A4B2 B2A4B2A2B2
A2B2A2B2A2B2 B2A2B2A2B2A2
共20种
#include <cstdio> #include <cstring> int coef[20],delt[20],inx[20],base[20]; int mark[1000010],pri[1000010],priN; __int64 dp[2000][20]; void init() { int i,j; for(i=2; i<=1000000; i++) mark[i]=i; for(i=2; i<=1000000; i++) { if(mark[i]==i) pri[priN++]=i; for(j=0; j<priN&&i*pri[j]<=1000000; j++) { mark[i*pri[j]]=pri[j]; if(i%pri[j]==0) break; } } } void deal() { __int64 u,ans,num,t,tmpv; int cnt,i,j,k,l,prod,tot,amn,m; scanf("%I64d", &u); for(cnt=0,num=u; num-1;) { if(num>1000000) { t=num; for(j=0; j<priN; j++) { if(num%pri[j]==0) { t=pri[j]; break; } } } else t=mark[num]; inx[cnt]=0; while(num%t==0) num/=t,inx[cnt]++; cnt++; } for(tot=0,prod=1,i=cnt-1; i>=0; i--) { tot+=inx[i],base[i]=prod,prod*=(inx[i]+1); } for(i=0; i<=tot; i++) for(j=0; j<prod; j++) dp[j][i]=0; dp[0][0]=1; for(i=1; i<prod; i++) { for(j=0; j<cnt; j++) delt[j]=i/base[j]%(inx[j]+1); for(j=prod-1; j>=0; j--) { amn=0x3fffffff; for(k=0; k<cnt; k++) { coef[k]=j/base[k]%(inx[k]+1); if(delt[k]) { tmpv=(inx[k]-coef[k])/delt[k]; if(tmpv<amn) amn=tmpv; } } for(l=1; l<=amn; l++) { for(k=0; k+l<=tot; k++) { tmpv=dp[j][k]; for(m=1; m<=l; m++) tmpv*=m+k,tmpv/=m; dp[j+i*l][k+l]+=tmpv; } } } } for(ans=dp[prod-1][tot]*dp[prod-1][tot],i=0; i<tot; i++) { ans+=(dp[prod-1][i]+dp[prod-1][i+1])*(dp[prod-1][i]+dp[prod-1][i+1]); } printf("%I64d\n", ans); } int main() { init(); int t; scanf("%d", &t); while(t--) deal(); return 0; }