题目：http://poj.org/problem?id=2279
书上的DP做法会爆内存，尝试写了一个，过了样例。
转载：
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #define ll unsigned long long using namespace std; ll k,n[7],f[35][35][35][35][35]; void cl(ll a1,ll a2,ll a3,ll a4,ll a5) { if(a1)f[a1][a2][a3][a4][a5]+=f[a1-1][a2][a3][a4][a5]; if(a2)f[a1][a2][a3][a4][a5]+=f[a1][a2-1][a3][a4][a5]; if(a3)f[a1][a2][a3][a4][a5]+=f[a1][a2][a3-1][a4][a5]; if(a4)f[a1][a2][a3][a4][a5]+=f[a1][a2][a3][a4-1][a5]; if(a5)f[a1][a2][a3][a4][a5]+=f[a1][a2][a3][a4][a5-1]; } int main() { while(scanf("%lld",&k)==1) { memset(f,0,sizeof f); memset(n,0,sizeof n);//!!! if(!k)return 0; for(ll i=1;i<=k;i++) scanf("%lld",&n[i]); f[0][0][0][0][0]=1; for(ll a1=0;a1<=n[1];a1++) { if(k>=2) for(ll a2=0;a2<=n[2]&&a2<=a1;a2++) { if(k>=3) for(ll a3=0;a3<=n[3]&&a3<=a2;a3++) { if(k>=4) for(ll a4=0;a4<=n[4]&&a4<=a3;a4++) { if(k>=5) for(ll a5=0;a5<=n[5]&&a5<=a4;a5++) cl(a1,a2,a3,a4,a5); else cl(a1,a2,a3,a4,0); } else cl(a1,a2,a3,0,0); } else cl(a1,a2,0,0,0); } else cl(a1,0,0,0,0); } printf("%lld ",f[n[1]][n[2]][n[3]][n[4]][n[5]]); } return 0; }
然后看到了“杨氏矩阵”与“钩子公式”。
转载：
杨氏矩阵定义（需满足的条件/特征）：（1）若格子（i，j），则该格子的右边和上边一定没有元素；
（2）若格子（i，j）有元素data[i][j]，则该格子右边和上边相邻的格子
要么没有元素，要么有比data[i][j]大的元素。
显然有同已写元素组成的杨氏矩阵不唯一，1~n组成杨氏矩阵的个数可以写出：F[1]=1，F[2]=2，
F[n]=F[n-1]+(n-1)*F[n-2] (n>2)。
钩子长度的定义：该格子右边的格子数和它上边的格子数之和;
钩子公式：对于给定形状，不同的杨氏矩阵的个数为(n！/(每个格子的钩子长度加1的积))。
于是直接用了，注意要步步约分。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #define ll unsigned long long using namespace std; int k,n[7]; ll h[35][35],s1,s2; ll gcd(ll x,ll y){ return x%y==0?y:gcd(y,x%y);} int main() { while(scanf("%d",&k)==1) { if(!k)return 0; memset(h,0,sizeof h); memset(n,0,sizeof n);//! for(int i=1;i<=k;i++) scanf("%d",&n[i]); for(int i=1;i<=k;i++) for(int j=1;j<=n[i];j++) { h[i][j]=n[i]-j+1; int k=i+1; while(n[k]>=j)h[i][j]++,k++; } int t=0;s1=1;s2=1; for(int i=1;i<=k;i++) for(int j=1;j<=n[i];j++) { t++; s1*=t;s2*=h[i][j]; ll tmp=gcd(s1,s2); s1/=tmp;s2/=tmp; } printf("%lld ",s1/s2); } return 0; }