Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF294C Shaass and Lights

Posted on

组合计数。

第二道做出来的组合啦。

Solution

题目比较简单，不难发现每个灯与灯之间的数删去的方案与外界独立， 于是先单独算出来每个间隔内的数的删除方案，具体的，如果在边界，只有一种方案，在中间，有$2^{len-1}$种方案（最后一个只有一种删除方法），然后考虑合并间隔，不难发现答案等于两堆的方案数相乘再乘上将这两堆融合在一起的方案数，具体的，设第一堆的方案数为$val_i$ ，数的个数为$len_i$，第二堆方案数为$val_j$，个数为$len_j$，合并出来的答案为$C_{len_i+len_j}^{len_i}\cdot val_i \cdot val_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
#include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	if(flag) res = -res; 
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
	if(res < 0) putchar('-'), res = -res;
	if(res > 9) write(res / 10);
	putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); } 
const int N = 1005, mod = 1e9 + 7;
int n, m, T;
int C[N][N];
inline void init()
{
    for(int i = 0;i < N;i ++) C[i][0] = 1;
    for(int i = 1;i < N;i ++)
        for(int j = 1;j <= i;j ++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod; 
}
int ans = 1;
int a[N], l = 0, r = 0, flag = 0;
inline int qpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod;
        k >>= 1;
    }
    return res;
}
vector<int>s;
int main()
{
    read(n, m);
    init();
    for(int i = 1, o;i <= m;i ++) read(o), a[o] = 1;
    for(int i = 1, cnt = 0, tot = 0;i <= n;i ++)
    {
        if(!a[i]) cnt ++;
        else {
            if(!tot) s.emplace_back(cnt);
            else if(cnt) s.emplace_back(cnt), flag |= cnt, ans = 1ll * ans * qpow(2, cnt - 1) % mod;
            cnt = 0;
            tot ++;
        }
        if(i == n) s.emplace_back(cnt);
    }
    int last = 0;
    for(int i : s)
        ans = 1ll * ans * C[last + i][i] % mod, last += i;
    write(ans);
    return 0;
}