[POJ 2279] Mr. Young's Picture Permutations

[题目链接]
[算法]
杨氏矩阵与勾长公式
[代码]
#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 35

typedef long long ll;

ll i,j,k,tmp,n,cnt;

ll a[MAXN];

ll num[MAXN*MAXN];

ll x,y;

ll gcd(ll x,ll y)

{

    return y ==  ? x : gcd(y,x % y);

}

int main()

{

    while (scanf("%lld",&n) != EOF && n)

    {

        cnt = ;

        memset(num,,sizeof(num));

        for (i = ; i <= n; i++) scanf("%lld",&a[i]);

        for (i = ; i <= n; i++)

        {

            for (j = ; j <= a[i]; j++)

            {

                cnt++;

                for (k = i + ; k <= n; k++)

                {

                    if (a[k] >= j) num[cnt]++;

                    else break;

                }

                num[cnt] += a[i] - j + ;

            }

        }

        x = ; y = ;

        for (i = ; i <= cnt; i++)

        {

            x *= i;

            y *= num[i];

            tmp = gcd(x,y);

            x /= tmp;

            y /= tmp;

        }

        printf("%lld\n",x/y);

    }

    return ;

}