题解 P5343 [XR-1]分块

发表于 | 更新于 | 分类于 | 阅读次数：

题面
首先搞出合法的块长
然后考虑dp,那么

边界$f_x=0(x<0),f_0 = 1$ 块长最大只有100 所以直接矩阵快速幂即可 

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
#include <bits/stdc++.h>
using namespace std;
const int n = 100, mod = 1000000007;
struct matrix {
    int a[110][110];
    inline int* operator [] (int x) {return a[x];}
    inline matrix() {memset(a, 0, sizeof a);}
    friend inline matrix operator * (matrix &a, matrix &b) {
        matrix ans;
        for(int i = 0; i < n; i++)
            for(int k = 0; k < n; k++)
                for(int j = 0; j < n; j++) ans[i][j] = (ans[i][j] + 1ll * a[i][k] * b[k][j]) % mod;
        return ans;
    }
} res, ans;
int pr, nf, able[110];
long long len;
int main() {
    scanf("%lld%d", &len, &pr);
    for(int i = 0, x; i < pr; i++) scanf("%d", &x), able[x] = 1;
    scanf("%d", &nf);
    for(int i = 0; i < n; i++) ans[i][i] = 1;
    for(int i = 1; i < n; i++) res[i][i - 1] = 1;
    for(int x, i = 0; i < nf; i++) {
        scanf("%d", &x);
        if(able[x]) res[n - x][n - 1] = 1;
    }
    for(; len; len >>= 1, res = res * res) if(len & 1) ans = ans * res;
    printf("%d\n", ans[n - 1][n - 1]);
    return 0;
}