P5343 【XR-1】分块

· · 题解

题目地址：P5343 【XR-1】分块

命题人来水官方题解啦

首先显然要求两个不可重集合的交

这个乱搞就行了

然后是显而易见的 dp

时间复杂度 O(xn)

由于 x 是常数所以实际上是线性的

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 6, P = 1e9 + 7;
int n, m = 10, f[N], p;
bitset<N> x, y;

inline void add(int &x, int y) {
    if ((x += y) >= P) x -= P;
}

int main() {
    cin >> n;
    f[0] = 1;
    cin >> p;
    while (p--) {
        int k;
        scanf("%d", &k);
        x[k] = 1;
    }
    cin >> p;
    while (p--) {
        int k;
        scanf("%d", &k);
        y[k] = 1;
    }
    x &= y;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (x[j]) add(f[i], f[i-j]);
    cout << f[n] << endl;
    return 0;
}

60分到手了

看一眼这个 dp

哇，可以矩阵快速幂加速递推诶

时间复杂度 O(x ^ 3\log n)

由于 x 是常数所以实际上是 \log 的

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 106, P = 1e9 + 7;
ll n, f[N], a[N][N];
int m = 100, p;
bitset<N> x, y;

void mul() {
    ll c[N];
    memset(c, 0, sizeof(c));
    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= m; i++)
            c[i] = (c[i] + f[j] * a[j][i]) % P;
    for (int i = 1; i <= m; i++) f[i] = c[i];
}

void mulself() {
    ll c[N][N];
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= m; i++)
        for (int k = 1; k <= m; k++)
            for (int j = 1; j <= m; j++)
                c[i][j] = (c[i][j] + a[i][k] * a[k][j]) % P;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = c[i][j];
}

int main() {
    cin >> n;
    f[m] = 1;
    for (int i = 1; i < m; i++) a[i+1][i] = 1;
    cin >> p;
    while (p--) {
        int k;
        scanf("%d", &k);
        x[k] = 1;
    }
    cin >> p;
    while (p--) {
        int k;
        scanf("%d", &k);
        y[k] = 1;
    }
    x &= y;
    for (int i = 1; i <= m; i++)
        if (x[i]) a[m-i+1][m] = 1;
    while (n) {
        if (n & 1) mul();
        mulself();
        n >>= 1;
    }
    cout << f[m] << endl;
    return 0;
}

100 分到手了

我知道这道题 x 可以开到 10 ^ 4！但是这是签到题！况且命题人这么菜也不会鸭 QwQ