ZOJ - 3777(状压dp)

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 Tindicating 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

Sample Output

3/1

No solution

题意是首先输入n和m，接下来n行n列输入pij，代表第i个问题放在位置j的值，求满足所有问题放在合适的位置上的值的和大于等于m的期望
，也就是求有多少种可能的组合。
shu[i] 代表用二进制表示的已经表示的数的情况，1表示已经使用，0表示没使用，具体可以看一下状压dp的简单介绍，用二进制存储状态
judge[i] 代表i的阶乘
dp[i][j] 代表将i的二进制位为1的位数的值的和为j时的个数枚举就是，
k代表已经表示了的题最后结果就是dp[ shu[n] - 1 ][m] ，不过要和judge[n]一起gcd一下
另外长记性了，写错了gcd，一直没改出来，还是用__gcd吧

minn = min(m , l + a[j][k]); 这里如果大于m，就让他等于m，这样dp[][m]才是正确答案

#include <iostream>

#include <algorithm>

#include <string.h>

#include <cstdio>

using namespace std;

int a[][];

int dp[ (<<) +  ][];

int shu[];

int judge[];

int minn,n,m,k;

void init()

{

    shu[] = ;

    judge[] = ;

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

    {

        shu[i] = shu[i-]*;

        judge[i] = judge[i-]*i;

    }

    return ;

}

void init2()

{

        for(int i=;i<shu[n];i++)

        {

            for(int j=;j<=m;j++)

            {

                dp[i][j] = ;

            }

        }

        dp[][] = ;

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

        {

            for(int j=;j<n;j++)

            {

                scanf("%d",&a[i][j]);

            }

        }

        return ;

}

int main()

{

    int t;

    scanf("%d",&t);

    init();

    while(t--)

    {

        scanf("%d%d",&n,&m);

        init2();

        for(int i=;i<shu[n];i++)

        {

            k = ;

            for(int j=;j<n;j++)

            {

                if(i&shu[j])

                {

                    k++;

                }

            }

            for(int j=;j<n;j++)

            {

                if(!(i&shu[j]))

                {

                    for(int l=;l<=m;l++)

                    {

                        minn = min(m , l + a[j][k]);

                        dp[i|shu[j]][minn] += dp[i][l];

                    }

                }

            }

        }

        int k1 = judge[n];

        int k2 = dp[shu[n] - ][m];

        if(!k2){

            cout<<"No solution"<<endl;

        }

        else{

            int k3 = __gcd(k1,k2);

            cout<<k1/k3<<"/"<<k2/k3<<endl;

        }

    }

    return  ;

}

巴特西

ZOJ - 3777(状压dp)

最新文章

热门文章