学步园

The 11th Zhejiang Provincial Collegiate Programming Contest is coming! As a problem setter, Edward is going to arrange the order of the problems. As we know, the arrangement will have a great effect on the result of the contest. For example, it will take
more time to finish the first problem if the easiest problem hides in the middle of the problem list.

There are N problems in the contest. Certainly, it's not interesting if the problems are sorted in the order of increasing difficulty. Edward decides to arrange the problems in a different way. After a careful study, he found out that the i-th
problem placed in the j-th position will add P_ij points of "interesting value" to the contest.

Edward wrote a program which can generate a random permutation of the problems. If the total interesting value of a permutation is larger than or equal to
M points, the permutation is acceptable. Edward wants to know the expected times of generation needed to obtain the first acceptable permutation.

Input

There are multiple test cases. The first line of input contains an integer
T indicating the number of test cases. For each test case:

The first line contains two integers N (1 <= N <= 12) and
M (1 <= M <= 500).

The next N lines, each line contains N integers. The j-th integer in the i-th line is
P_ij (0 <= P_ij <= 100).

Output

For each test case, output the expected times in the form of irreducible fraction. An irreducible fraction is a fraction in which the numerator and denominator are positive integers and have no other common divisors than 1. If it is impossible to get an
acceptable permutation, output "No solution" instead.

Sample Input

2
3 10
2 4 1
3 2 2
4 5 3
2 6
1 3
2 4

Sample Output

3/1
No solution

Source: The 11th Zhejiang Provincial Collegiate Programming Contest

题意：

告诉你有n（1<=n<=12）道ACM题目。每道题目放在不同的位置都有一个happy值。以n*n矩阵给出。第i行第j列的值表示第i个为题放在第j个位置的happy值p[i][j](0<=p[i][j]<=100)。现在有个人写了个随机算法。问你他要得到一个happy值不小于m(1<=m<=500)的排列。问他生成次数的期望。

思路：

如果知道他一次随机生成的序列为满足条件的序列的概率p。那么期望E=1/p了。而p又为满足条件的方案数/总发难数。最简单粗暴的方法就是dfs暴力每种选择然后统计满足条件的方案数。但是dfs时间复杂度为O(n!)。明显超时的节奏。只有换种方法。受到以前做过一道题的启发。可以用背包算出生成的序列每种happy值的方案数。那么最后统计下就行了。但是题目中限制每行每列只能选择一个。所以就想到了用壮压来记录已经选择的列。n的范围正好！那么思路大概就清晰了。dp[i][j]表示。目前列的选择状态为i.happy值为j的方案数。i中二进制位中k位为1表示第k列已经选择。需要注意的是这里不用枚举行数。因为i中1的个数就可以代表行数了。递推时只需根据1的个数就可确定了。这样就不会出现某一行重复选多次的情况。比赛时忽略这一点导致错误的认为这个算法要超时。。。。真是逗。

详细见代码：

#include<bits/stdc++.h>
using namespace std;

int dp[1<<12][510],p[15][15],base[15],one[1<<12],ml[12];
void init()//预处理
{
    int i,t,ct;
    base[0]=ml[0]=1;//base[i]表示2^i.ml[i]表示i!。one[i]比奥斯i中1的个数。
    for(i=1;i<=12;i++)
        base[i]=base[i-1]<<1,ml[i]=ml[i-1]*i;
    for(i=0;i<=base[12];i++)
    {
        t=i,ct=0;
        while(t)
            ct+=t&1,t>>=1;
        one[i]=ct;
    }
}
int gcd(int x,int y)//求x,y的最大公约数
{
    int tp;
    while(tp=x%y)
        x=y,y=tp;
    return y;
}
int main()
{
    int i,j,k,n,m,t,tp,ns,ans;

    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                scanf("%d",&p[i][j]);
        m--,ans=0;
        memset(dp,0,sizeof dp);
        dp[0][0]=1;
        for(i=0;i<base[n];i++)//枚举上一状态
        {
            tp=one[i];//注意是从0开始算的。所以tp=one[i]+1-1.
            for(j=0;j<n;j++)//枚举下个状态tp行选第j列。
            {
                if(base[j]&i)//检查j列是否占用。
                    continue;
                for(k=m,ns=i|base[j];k>=p[tp][j];k--)//01背包。
                    if(dp[i][k-p[tp][j]])
                        dp[ns][k]+=dp[i][k-p[tp][j]];
            }
//            printf("bit %o\n",i);
//            for(k=0;k<=m;k++)
//                printf("%d %d\n",k,dp[i][k]);
        }
        for(i=0,tp=base[n]-1;i<=m;i++)
            ans+=dp[tp][i];//计算不满足的个数。
        ans=ml[n]-ans,tp=gcd(ans,ml[n]);//总个数减不满足的个数即为满足个数。
        if(!ans)
            printf("No solution\n");
        else
            printf("%d/%d\n",ml[n]/tp,ans/tp);
    }
    return 0;
}