班服 (shirt. pas/. c/. cpp)

时间限制 1s 内存限制 128MB

题目描述

要开运动会了, 神犇学校的 n 个班级要选班服, 班服共有 100 种样式, 编号 1~ 100. 现在每个班都挑出了一些样式待选, 每个班最多有 100 个待选的样式. 要求每个班最终选定一种样式作为班服, 且该班的样式不能与其他班级的相同, 求所有可能方案的总数, 由于方案总数可能很大, 所以要求输出 mod 1000000007 后的答案.

输入描述

共有 T 组数据.

对于每组数据, 第一行为一个整数 n, 表示有 n 个班级.

2~ n+1 行, 每行有最多 100 个数字, 表示第 i-1 班待选班服的编号.

输出描述

对于每组数据, 输出方案总数 mod 1000000007 后的答案.

样例输入

2
3
5 100 1
2
5 100
2
3 5
8 100

样例输出

4
4

数据范围

对于 30% 的数据,\(1 \leq T \leq 3\),\(1 \leq n \leq 3\), 每班待选样式不超过 10 种.

对于 50% 的数据,\(1 \leq T \leq 5\),\(1 \leq n \leq 5\), 每班待选样式不超过 50 种.

对于 100% 的数据,\(1 \leq T \leq 10\),\(1 \leq n \leq 10\), 每班待选样式不超过 100 种.

Explanation

简单状压 DP (看到那么小的\(n\) 就应该想到状压的好不好), 然后把每一个班选没选这种 衣服压成一个大小不超过\(1023\) 的状态并集, 然后直接 DP.

话说没有把has 数组memset 成全零调了我半个小时 233~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <sstream>

using namespace std;
typedef long long lli;
const int maxn = 1050, maxm = 110, maxc = 11;
const lli modr = 1000000007;

int T, n;
lli dp[maxm][maxn];
bool has[maxc][maxm];

lli eval(void)
{
    memset(dp, 0, sizeof(dp));
    // There is one way to assign nothing to no classes.
    dp[0][0] = 1;
    // For i in all of the possible clothes
    for (int i = 1; i <= 100; i++) {
        // Continuing state from last type of clothes
        for (int j = 0; j < (1 << n); j++)
            dp[i][j] = dp[i - 1][j];
        // For any kind of clothes j
        for (int j = 1; j <= n; j++) {
            // This class #j does not prefer clothing #i.
            if (!has[j][i])
                continue;
            // Iterate all those states in binary, and insert type j as an addition
            for (int k = 0; k < (1 << n); k++)
                if ((k & (1 << (j - 1))) == 0)
                    dp[i][k + (1 << (j - 1))] = (dp[i][k + (1 << (j - 1))] +
                        dp[i - 1][k]) % modr;
        }
    }
    return dp[100][(1 << n) - 1];
}

int main(int argc, char** argv)
{
    cin >> T;
    for (int idx = 1; idx <= T; idx++) {
        cin >> n;
        string null_str; getline(cin, null_str);
        memset(has, 0, sizeof(has)); // This bugged me for half an hour...
        for (int i = 1; i <= n; i++) {
            string str;
            getline(cin, str);
            stringstream trm;
            trm << str << " 0";
            int tmp = 0;
            while (true) {
                trm >> tmp;
                if (!tmp) break;
                has[i][tmp] = true;
            }
        }
        // Done reading, evaluating
        lli res = eval();
        printf("%lld\n", res);
    }
    return 0;
}