P2150 [NOI2015] 寿司晚宴

考虑状压。

先考虑 n <= 30 的做法。

30 以内一共有 10 个质数。设 dp[i][j] 表示 A 集合的质因子并为 i 且 B 集合的质因子并为 j.

dp[u][i][j] += dp[u - 1][i | k][j]; (k & j == 0) dp[u][i][j] += dp[u - 1][i][j | k]; (i & k == 0)

埋伏一手优化掉第一维。

复杂度 O(n\times 2^{20})

考虑正解。

有个神奇的性质，对于 n <= 500 大于等于 23 的因子最多只有一个。

瞎搞求出每个数的最大因子和小于 23 的因子构成。

然后开始dp。

但是我们发现大于 23 的因子竟然没法统计！

因此按照最大的因子大小排个序，按照最大因子的顺序进行转移，相同的一起转移，这样我们发现巧妙的避开了最大因子重复的问题。

值得注意的是如果没有大因子每次都要 merge。

完。

#include <bits/stdc++.h>
#define ms(x) memset(x, 0, sizeof x)
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
using namespace std;
#define int long long
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

const vector<int> Primes {2, 3, 5, 7, 11, 13, 17, 19};
const int N = (1 << 8);
int f[N][N], f1[N][N], f2[N][N], mod;

struct Node {
    int v, st, big;
    Node() : v(0), st(0), big(0) { }
    void init() {
        int cv = v;
        for(int i = 0; i < (int) Primes.size(); i++) {
            if(cv % Primes[i]) continue;
            st |= (1 << i); 
            while(cv % Primes[i] == 0) cv /= Primes[i]; 
        }
        if(cv > 1) big = cv;
        else big = -1;
    }

    bool operator<(const Node &b) const {
        return big < b.big;
    }
} node[503];

int positive(int x, int mod) {
    return (x % mod + mod) % mod;
}

void Merge() {
    for(int a = (1 << 8) - 1; ~a; --a) {
        for(int b = (1 << 8) - 1; ~b; --b) {
            if(a & b) continue;
            f[a][b] = positive(f1[a][b] + f2[a][b] - f[a][b], mod);
        }
    }
}

signed main() {
    int n = rd() - 1; mod = rd();
    for(int i = 1; i <= n; i++) node[i].v = i + 1, node[i].init();
    sort(node + 1, node + n + 1);

    f[0][0] = f1[0][0] = f2[0][0] = 1;

    for(int i = 1; i <= n; i++) {
        if(node[i].big != node[i - 1].big || node[i].big == -1) {
            Merge();
            memcpy(f1, f, sizeof f1);
            memcpy(f2, f, sizeof f2);
        }

        int st = node[i].st;
        for(int a = (1 << 8) - 1; ~a; --a) {
            for(int b = (1 << 8) - 1; ~b; --b) {
                if(a & b) continue;
                if((st & a) == 0) f2[a][b | st] = (f2[a][b | st] + f2[a][b]) % mod;
                if((st & b) == 0) f1[a | st][b] = (f1[a | st][b] + f1[a][b]) % mod;
            }
        }
    }

    Merge();

    int ans = 0;
    for(int i = 0; i < (1 << 8); i++) {
        for(int j = 0; j < (1 << 8); j++) {
            if(i & j) continue; 
            ans = (ans + f[i][j]) % mod;
        }
    }

    cout << ans << endl;
    return 0;
}

seg

小而美系列。

先考虑没有正偶数的条件，仅为全部出现。

上双指针。对于一个极小全部包含的段 [l, r] ， [1, l - 1] 必然是全部连续段。

发现 m 好像很小？ 考虑状压。一段区间某数出现次数为奇数则为 1 否则为 0。

枚举前缀中 [1, l - 1] 的合法状态。

设 sum[i] 表示 [1, i] 的前缀异或和。

注意到二进制表达，若异或和为 0 则所有数出现次数均为偶数次（0 也是偶数）。

我们计 f[i] 表示目前状态前缀异或和为 i 的状态个数。

这样我们发现，如果 sum[x] ^ sum[r] 则 [x + 1, r] 的异或和为 0，即出现了偶数次。

这样即加入了偶数的限制。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define dd(x) cerr << #x << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

const int N = 4e6 + 6;
int sum[N], que[23], num;
int f[N], a[N], n, m, l = 0;

signed main() {
    n = rd(), m = rd();
    for(int i = 1; i <= n; i++) {
        a[i] = rd();
    }

    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] ^ (1 << (a[i] - 1));
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(++que[a[i]] == 1) ++num;
        while(num == m && que[a[l + 1]] > 1) {
            --que[a[l + 1]], f[sum[l]]++, ++l;
        }
        if(num == m) ans += f[sum[i]];
    }

    cout << ans << endl;
    return 0;
}

jump