题目大意：
你和朋友两人玩游戏，将一个图片均等切割成W* H块，打乱每一小块的位置。拼图游戏开始。每次，可以交换任意两块，记下交换的次数，图片还原游戏结束。得分为执行交换的次数。得分越小越好。
现在，给你W和H， 还有你朋友的得分S，问，你能够得到小于S分的概率。
解题思路：
首先，在考虑问题时，只和块数有关，所以，N = W * H， W和H可以无视之。
然后，用 P[N][K] 表示：图片被分割成 N 块，需要交换 K 次才能使图片还原 的情况数目。那么，我们再 加上一小块，也就是说，把图片分割成 N + 1 块。假如，新加入的第 N + 1 块 它就在正确的位置上，那么，使图片还原需要 K 次操作]； 假如，新加入的第 N + 1 块不在正确的位置上，那么，它必定和前面 N 块中的某一块交换了位置， 则要把图片还原，就需要 K + 1 次操作。
整理一下可以得到下面的递推式：
p[i][j] = p[i - 1][j] + p[i - 1][j - 1] * (i - 1)
#include <iostream>
using namespace std;
__int64 p[][];
__int64 gcd(__int64 a, __int64 b)
{
return b ? gcd(b, a % b) : a;
}
void init()
{
int i, j;
for (i = ; i <= ; ++i)
{
p[i][] = ;
p[i][i] = ;
}
for (i = ; i <= ; ++i)
for (j = ; j < i; ++j)
p[i][j] = p[i - ][j] + p[i - ][j - ] * (i - );
}
void solve(int s, int n)
{
__int64 sum = , total = , g;
int i;
for (i = ; i < s; ++i)
sum += p[n][i];
total = sum;
for ( ; i < n; ++i)
total += p[n][i];
g = gcd(sum, total);
sum /= g;
total /= g;
if (total == && sum == )
printf("1\n");
else if (sum == )
printf("0\n");
else printf("%I64d/%I64d\n", sum, total);
}
int main()
{
init();
int tcase, w, h, n, s;
scanf("%d", &tcase);
while (tcase--)
{
scanf("%d%d%d", &w, &h, &s);
solve(s, w * h);
}
return ;
}