http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5264
题意：给出n道题目以及每一道题目不同时间做的兴趣值，让你求出所有做题顺序中兴趣值大于等于m的比例。用一个分数表示。
状压dp。 枚举每一个状态，用二进制表示。dp[i][j]表示第i个题目，兴趣值为j的个数。
转移方程 dp[i|(1<<j)][k+a[num][j]]+=dp[i][k];兴趣值大于m的为 dp[1|(1<<j)][m]+=dp[i][k];
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std; int t,n,m;
int p[][];
int dp[<<][];
int f[]; LL gcd(LL a,LL b)
{
return b==?a:gcd(b,a%b);
} int main()
{
scanf("%d",&t);
f[]=;
for(int i=; i<=; i++)
{
f[i]=f[i-]*i;
}
while(t--)
{
scanf("%d%d",&n,&m);
memset(dp,,sizeof(dp));
for(int i=; i<n; i++)
{
for(int j=; j<n; j++)
{
scanf("%d",&p[i][j]);
}
}
dp[][]=;
for(int i=; i<=(<<n); i++)
{
int num=;
for(int j=; j<n; j++)
{
if(i&(<<j)) num++;
}
for(int j=; j<n; j++)
{
if(i&(<<j)) continue;
for(int k=; k<=m; k++)
{
if(k+p[num][j]>=m)
{
dp[i|(<<j)][m]+=dp[i][k];
}
else
{
dp[i|(<<j)][k+p[num][j]]+=dp[i][k];
}
}
}
}
if(dp[(<<n)-][m]==)
{
printf("No solution\n");
}
else
{
int g=gcd(f[n],dp[(<<n)-][m]);
printf("%d/%d\n",f[n]/g,dp[(<<n)-][m]/g);
}
}
return ;
}