poj2278(钩子公式)

链接：点击打开链接
题意：求给定形状的杨氏矩阵的种数

代码：

#include <map>
#include <set>
#include <queue>
#include <string>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int a[105],b[105];
int main(){
    int n,i,j,k;
    long long u,v,x,y,w;
    while(scanf("%d",&n)!=EOF&&n){
        for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
        v=0;
        for(i=1;i<=n;i++){                      //钩子公式，n!/∏(ni) ni为每个点当前行和列比当前值
            for(j=1;j<=a[i];j++){               //大的个数+1
                u=a[i]-j;
                for(k=i+1;k<=n;k++)
                if(a[k]>=j)
                u++;
                b[++v]=u+1;
            }
        }
        x=y=1;                                  //上溢，维护一下分数
        for(i=1;i<=v;i++){
            x*=i,y*=b[i];
            w=__gcd(x,y);
            x/=w,y/=w;
        }
        printf("%I64d\n",x/y);
    }

    return 0;
}