LINK：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3777

题意：有N(\( N <= 12 \))道题,排顺序,当某道题选择了放在第j个位置时,会获得Pij的点数,但其他题目就不能选择j位置了。要求总获得的点数要大于M(\(1 <= M <= 500\)),问在所有方案中选择出合法方案的次数的期望值。

思路：题目要求的期望值,比较简单,就是总方案数和合法方案数的比值。看题目就知道是个DP,重点在于状态设计上。首先我们考虑到每个j位置只能被选择一次,也就意味着所有N门课所具有的状态是不同,而且某题选择位置后就不用再考虑它其他位置上的点数,即无后效性,这时很容易想到状压,二进制位对应当前状态下某个位置是否已被选择。

dp[s][j]代表s状态,不小于j点数的方案数。转移上,枚举旧状态,再枚举下一状态所有可行的选择方案(没被选择过的位置),旧状态到新状态。嘛,就是个背包。dp[s | (1<<k)][j] += dp[s][j - p[cnt][k]] 其中cnt表示前cnt题已进行过选择。

/** @Date    : 2017-03-27-15.47

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version :

  */

#include<bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

LL gcd(LL a, LL b)

{

    return b?gcd(b, a % b):a;

}

LL fac(int x)

{

    LL ans = 1;

    while(x)

    {

        ans *= x;

        x--;

    }

    return ans;

}

LL a[15][15];

LL dp[(1 << 12)+20][510];

int main()

{

    int T;

    cin >> T;

    while(T--)

    {

        LL n, k;

        cin >> n >> k;

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

        {

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

            {

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

            }

        }

        MMF(dp);

        dp[0][0] = 1;

        for(int s = 0; s < (1 << n); s++)//枚举旧状态

        {

            int cnt = 0;

            int t = s;

            while(t)

            {

                if(t & 1)

                    cnt++;

                t >>= 1;

            }

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

            {

                if((1 << i) & s) continue;

                for(int j = k; j >= 0; j--)

                {

                    if(j >= a[cnt][i])

                        dp[s | (1 << i)][j] += dp[s][j - a[cnt][i]];//

                }

            }

        }

        LL ans = 0;

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

        {

            ans += dp[(1 << n) - 1][i];//求不符合要去的

        }

        //cout << ans << endl;

        LL x = fac(n);

        LL y = x - ans;

        LL g = 1;

        g = gcd(x, y);

        if(y == 0)

            printf("No solution\n");

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

    }

    return 0;

}