题目地址：洛谷：【P2396】yyy loves Maths VII – 洛谷

题目背景

yyy对某些数字有着情有独钟的喜爱,他叫他们为幸运数字;然而他作死太多,所以把自己讨厌的数字成为”厄运数字”

题目描述

一群同学在和yyy玩一个游戏
每次,他们会给yyy n张卡片,卡片上有数字,所有的数字都是”幸运数字”,我们认为第i张卡片上数字是ai
每次yyy可以选择向前走ai步并且丢掉第i张卡片
当他手上没有卡片的时候他就赢了
但是呢,大家对”厄运数字”的位置布置下了陷阱,如果yyy停在这个格子上,那么他就输了
(注意:即使到了终点,但是这个位置是厄运数字,那么也输了)
现在,有些同学开始问:
yyy有多大的概率会赢呢?
大家觉得这是个好问题
有人立即让yyy写个程序
“电脑运行速度很快!24的阶乘也不过就620448401733239439360000,yyy你快写个程序来算一算”
yyy表示很无语,他表示他不想算概率,最多算算赢的方案数,而且是%1,000,000,007以后的值
大家都不会写程序,只好妥协
但是这时候yyy为难了,24!太大了,要跑好长时间.
他时间严重不够!需要你的帮助!
由于yyy人格分裂，某个数字可能既属于幸运数字又属于厄运数字。

输入输出格式

输入格式：
第一行n
下面一行n张卡片
第三行m 表示yyy的厄运数字个数(最多2个)
最后一行是m个厄运数字

输出格式：
方案数%1,000,000,007

输入输出样例

输入样例#1：

8
1 3 1 5 2 2 2 3
0

输出样例#1：

40320

输入样例#2：

24
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
10 15

输出样例#2：

0

说明

数据范围:
10%的数据n<=10
50%的数据n<=23
100%的数据n<=24

题解

勉强算可以状压吧。
考虑状压DP统计方案数，方程比较容易想出
\displaystyle dp[S] = \sum_{i \in S, i \neq \text{厄运}} dp[S \backslash \{i\}]
我们预处理出数组dis[S]表示S这些卡片的和，方便判断是否可以转移。
复杂度是O(2^n)。然而很卡常，所以还是开O2吧23333。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = (1 << 24) + 5, MO = 1e9 + 7;

inline int lowbit(int x) {
    return x & -x;
}

int n, m, num[5], dis[MAXN], dp[MAXN];

int main() {
    n = readint();
    for(register int i = 1; i <= n; i++) {
        dis[1 << (i - 1)] = readint();
    }
    m = readint();
    for(register int i = 1; i <= m; i++) {
        num[i] = readint();
    }
    for(register int i = 1; i < 1 << n; i++) {
        register int j = lowbit(i);
        dis[i] = dis[i ^ j] + dis[j];
    }
    dp[0] = 1;
    for(register int i = 1; i < 1 << n; i++) {
        register bool can = true;
        for(register int j = 1; j <= m; j++) {
            if(dis[i] == num[j]) {
                can = false; break;
            }
        }
        if(!can) continue;
        for(register int j = i, k = lowbit(j); j; j -= k, k = lowbit(j)) {
            dp[i] += dp[i ^ k];
            if(dp[i] >= MO) dp[i] -= MO;
        }
    }
    printf("%d", dp[(1 << n) - 1]);
    return 0;
}