LuoguP2396题解

发表于

有点难想的状态压缩dp

Description

一群同学在和yyy玩一个游戏

每次,他们会给yyy n张卡片,卡片上有数字,所有的数字都是”幸运数字”,我们认为第i张卡片上数字是ai

每次yyy可以选择向前走ai步并且丢掉第i张卡片

当他手上没有卡片的时候他就赢了

但是呢,大家对”厄运数字”的位置布置下了陷阱,如果yyy停在这个格子上,那么他就输了

(注意:即使到了终点,但是这个位置是厄运数字,那么也输了)

现在,有些同学开始问:

yyy有多大的概率会赢呢?

大家觉得这是个好问题

有人立即让yyy写个程序

“电脑运行速度很快!24的阶乘也不过就620448401733239439360000,yyy你快写个程序来算一算”

yyy表示很无语,他表示他不想算概率,最多算算赢的方案数,而且是%1,000,000,007以后的值

大家都不会写程序,只好妥协

但是这时候yyy为难了,24!太大了,要跑好长时间.

他时间严重不够!需要你的帮助!

由于yyy人格分裂，某个数字可能既属于幸运数字又属于厄运数字。

Samples

Input #1

1
2
3
8
1 3 1 5 2 2 2 3
0

Output #1

1
40320

Input #2

1
0

Hint

数据范围:

10%的数据n<=10

50%的数据n<=23

100%的数据n<=24

Solution

观察到$n$的范围极小, 那么考虑状压dp.

我们设$dp_i$表示选择了集合$i$内的卡片的方案数, 然后记一个$dist_i$表示使用集合$i$内卡片所到达的位置.

显然在$dist_i$是厄运数字的时候是不能转移的, 那么特判掉.

考虑转移, 我们可以枚举当前使用的卡片$j, j \in i$, 可以得出:

$$dp_i = \sum_{j=1}^n [j \in i] dp_{i \text{ } \rm{xor} \text{ }j}$$

这里的$dp_{i \text{ } \rm{xor} \text{ }j}$是表示集合$i$在删除$j$这个元素时的答案.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/* Headers */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 20 + 4;
const int mod = 1e9 + 7;
int n, m, un[2], dist[1 << MAXN], dp[1 << MAXN];
/* functions */
inline int quick_plus(int x, int y) {
	int res = x + y;
	return (res >= mod) ? (res - mod) : res;
}
int main(int argc,char *argv[]){
	scanf("%d", &n);
	FORR(i, 0, n - 1, 1) scanf("%d", &dist[1 << i]);
	scanf("%d", &m); dp[0] = 1;
	FORR(i, 0, m - 1, 1) scanf("%d", &un[i]);
	FORR(i, 1, (1 << n) - 1, 1) {
		int p = lowbit(i);
		dist[i] = dist[i ^ p] + dist[p];
		if(dist[i] == un[0] || dist[i] == un[1]) continue;//特判掉厄运数字的情况
		for(register int j = i, k; j; j ^= k) 
			k = lowbit(j), dp[i] = quick_plus(dp[i], dp[i ^ k]);
	}
	printf("%d\n", dp[(1 << n) - 1]);	
	return 0;
}

THE END