题目链接：http://poj.org/problem?id=2279 题意：给出一个n行的矩阵，每一行有a[i]个数，总共有sum个数，要求每一个位置的数必须比上面的数和左面的数大，求总方案数 题解： 刚开始看到这道题，潜意识里是要爆搜（貌似我也只会这样做了） 毕竟暴力出滑稽 但貌似有DP解法？？？（听lyd讲了还是不会啊） 只好强势安利一个【杨氏矩阵/钩子公式】了
以下部分转自 ACdreamers 杨氏矩阵又叫杨氏图表，它是这样一个矩阵，满足条件：
(1)如果格子(i,j)没有元素，则它右边和上边的相邻格子也一定没有元素。 (2)如果格子(i,j)有元素a[i][j]，则它右边和上边的相邻格子要么没有元素，要么有元素且比a[i][j]大。
1 ~ n所组成杨氏矩阵的个数可以通过下面的递推式得到：
下面介绍一个公式，那就是著名的钩子公式。
对于给定形状，不同的杨氏矩阵的个数为：n！/(每个格子的钩子长度加1的积)。 其中钩子长度定义为该格子右边的格子数和它上边的格子数之和。
证明的话…… 只好挖个坑了 路过了大佬如果知道的话麻烦指教一下蒟蒻
回到这道题目 就是把杨氏矩阵转了个圈 直接套用公式就好了 但为了防止中间结果溢出要步步约分
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; int n,num[10],tot; LL t1,t2,tmp[110],hhh; LL gcd(LL a,LL b) { return b?gcd(b,a%b):a; } int main() { while(scanf("%d",&n)&&n) { memset(tmp,0,sizeof(tmp)); t1=1,t2=1,tot=0; for(int i=1;i<=n;i++) scanf("%d",&num[i]); for(int i=1;i<=n;i++) for(int j=1;j<=num[i];j++) { tmp[++tot]+=num[i]-j+1; for(int k=i+1;k<=n;k++) tmp[tot]+=(num[k]>=j); } for(int i=1;i<=tot;i++) { t1*=i;t2*=tmp[i]; hhh=gcd(t1,t2); t1/=hhh;t2/=hhh; } printf("%lld\n",t1/t2); } return 0; }听说POJ1825是双倍经验题（手动滑稽）
