251029 模拟赛

T1

构造一个长为 \(n\) 的正整数序列，满足异或和为 \(0\)，以及 \(m\) 个限制形如 \(a[x_i]\ne y_i\)。输出字典序最小的解。

\(n\le 10^5\)

确定任意 \(n-1\) 个数后都可以唯一确定剩下的一个数。只要前 \(n-2\) 个数的异或和不为 \(0\)，都可以通过调整倒数第二个数字构造一种合法的方案。因此先将前 \(n-2\) 个数取字典序最小的解即可，在第 \(n-2\) 个位置特判一下异或和为 \(0\) 的情况，然后从小到大枚举第 \(n-1\) 个数的取值集合，计算最后一个数是否符合条件即可。

T2

有 \(n\) 个房间，第 \(i\) 个房间有 \(a_i\) 只奶龙。你有 \(2k\) 个箱子，每个箱子可以装任意只奶龙（可以不装），但一个箱子只能装来自同一个房间的奶龙。房间中的奶龙可以不全部抓走（也可以不抓）。在你决定分配方案之后，会出现一个捣蛋鬼拿走 \(2k\) 个箱子中奶龙数量前 \(k\) 大的箱子，剩下的箱子归你所有。你希望最大化你拥有的奶龙数量，在此基础上希望捣蛋鬼拿到的奶龙尽可能少。

\(1\le n\le 3\times 10^5,~1\le k\le 10^{11},~1\le a_i\le 3\times 10^5\)

考虑枚举捣蛋鬼拿走的箱子中奶龙数量的最小值（记为 \(x\)），那么剩下的 \(k\) 个箱子的奶龙数量都不多于 \(x\)。考虑如何对一个 \(x\) 求答案。我们要给捣蛋鬼留足够的奶龙（\(xk\) 个），因此首先需要满足 \(\sum\lfloor\frac{a_i}{x}\rfloor\ge k\)。考虑剩下什么，由于我们的单个箱子不能装超过 \(x\) 个奶龙，因此先尝试装 \(x\) 只奶龙，这样可以有 \(\min(k,\sum\lfloor\frac{a_i}{x}\rfloor-k)\) 个箱子。如果还有剩余的箱子，此时每个房间只剩下 \(a_i\bmod x\) 只奶龙，就将 \(a_i\bmod x\) 从大到小排序取前 \(2k-\sum\lfloor\frac{a_i}{x}\rfloor\) 个。

考虑如何维护，发现难点在于排序后取 \(a_i\bmod x\) 的前 \(r\) 大之和。考虑二分，先二分出第 \(r\) 大的值，考虑如何快速 check。发现模 \(x\) 余数大于等于 \(mid\) 的数字在值域上形成 \(\lceil\frac{V}{x}\rceil\) 个连续段。用前缀和处理每个连续段的贡献，这样时间复杂度形如一个调和级数。这样前 \(r\) 大的也是好做的。

时间复杂度 \(O(n\log \log n)\)（\(n\) 和值域同阶）。

T3

对于一个长为 \(n\) 的 01 串（下标从 \(1\) 开始），称一个下标二元组 \((i,j)\) 是好的，当且仅当 \(0<|i-j|<k\) 并且 \(a_i=a_j=1\)。\(k\) 是给定的常数。

给定一个包含 0,1,? 的字符串，问有多少种将 ? 填成 0,1 的方案，使得好的二元组数量恰好有 \(x\) 个。对所有 \(0\le x\le m\) 求出答案。对给定的质数取模。

\(1\le n\le 50,~0\le m\le \frac{1}{2}n(n-1),~1\le k\le n\)

部分分 \(1\)：\(k\le 10\) 部分分 \(2\)：\(n\le 30\)

\(k\) 较小时显然可以直接 \(O(nm2^k)\) 暴力状压。考虑 \(k\) 较大时怎么做。假设 \(k\ge \frac{n}{2}\)，那么我们可以指数复杂度枚举前 \(n-k\) 项，然后用 dp 处理后 \(k\) 项，因为后 \(k\) 项总是能贡献到后 \(k\) 项，因此后一段 dp 时只需记录前缀长度以及前缀中有多少个 \(1\)。容易做到 \(O(2^{\frac{n}{2}}(\frac{n}{2})^2m)\)。这启发我们，一些总能贡献的段可以只记录 \(1\) 的数量。

仍然考虑 \(k\) 比较大（\(k\ge\frac{n}{2}\)）的情况。由于任意一个长度不超过 \(k\) 的区间内部显然总是能贡献到，因此先把序列划分为 \(k\) 和 \(n-k\) 两部分；尝试用更低的时间复杂度处理两区间之间的贡献。发现对于左边的一个点 \(i\)，恰好有右边区间的一个长度为 \(i\) 的前缀能贡献到它，因此考虑同时对两个区间进行 dp，设 dp 状态表示考虑了左边区间的前 \(i\) 个点和右边区间的前 \(i\) 个点，什么什么的。发现这样只需要记录两个前缀各包含多少个 \(1\)，因此可以做到 \(O\bigl(poly(n)\big)\)。

由于 \(k\) 接近但不超过 \(\frac{n}{2}\) 时，暴力状压 dp 还是会爆，因此尝试优化上面的算法，用它来处理一些 \(k<\frac{n}{2}\) 但不很小（\(<10\)）的情况。将区间划分为若干长度为 \(k\) 的区间，最后面的那个区间长度为 \(n\bmod k\)。然后还是设 dp 状态表示考虑了每个区间长度为 \(i\) 的前缀，什么什么的。从左到右依次为每个区间添加一个点，将前缀长度扩展 \(1\) 位。考虑在中间某一个区间扩展的过程中，左边的区间已经考虑的部分恰好不能贡献到当前位置；右边的区间的第 \(i\) 位还没有被考虑到，因此恰好可以全部贡献到当前点。按照这样的转移顺序，我们只记录每个区间内部的 \(1\) 的数量即可。时间复杂度 \(O(k^{\frac{n}{k}}nm)\)，和状压拼起来，阈值差不多设为 \(k=13\)，这样只分四段区间就行。

实现别写太烂，我是对着 std 写的，不然感觉真卡不过去。用一维数组+位运算寻址比二维数组快很多，内存密集 Cache 也很好。

代码

#include<iostream>
#include<vector>
#define ll long long
using namespace std;

int n, m, k, MOD;
inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

int bcnt;
int dp[2][(int)4e7];
int ans[1250];
int base[10], sz[10], cur[10];
char s[55];

template<bool o0, bool o1>
inline void trans1(int *f, int *g) {
    int B = k - 1, S = 1 << B;
    for(int x = 0; x <= m; x++) {
        for(int i = 0; i < S; i++) {
            int &val = f[x << B | i];
            if(!val) continue;
            if constexpr (o0) {
                add(g[x << B | (i << 1 & S - 1)], val);
            }
            if constexpr (o1) {
                int x1 = x + __builtin_popcount(i);
                if(x1 <= m) add(g[x1 << B | ((i << 1 | 1) & S - 1)], val);
            }
            val = 0;
        }
    }
}

template<bool o0, bool o1>
void dfs(int i, int s, int p, int *f, int *g) {
    static int cnt[10];
    if(i == bcnt) {
        for(int S = s + m; s <= S; s++) {
            int &val = f[s];
            if(!val) continue;
            if constexpr (o0) {
                add(g[s], val);
            }
            if constexpr (o1) {
                int s1 = s + cnt[p] + cnt[p + 1];
                if(s1 <= S) add(g[s1 + base[p]], val);
            }
            val = 0;
        }
        return;
    } else {
        for(int &c = cnt[i] = 0; c <= cur[i]; c++, s += base[i]) {
            dfs<o0, o1>(i + 1, s, p, f, g);
        }
    }
}

template<bool o0, bool o1>
inline void trans2(int *f, int *g, int p) {
    dfs<o0, o1>(0, 0, p, f, g);
}

int main() {

    freopen("network.in", "r", stdin);
    freopen("network.out", "w", stdout);

    cin >> n >> m >> k >> MOD;

    if(k <= 13) {
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            char c; cin >> c;
            int *f = dp[(i & 1) ^ 1], *g = dp[i & 1];
            if(c == '0') trans1<true, false>(f, g);
            else if(c == '1') trans1<false, true>(f, g);
            else trans1<true, true>(f, g);
        }
        for(int x = 0; x <= m; x++) {
            for(int i = 0, S = (1 << k - 1); i < S; i++) {
                add(ans[x], dp[n & 1][x << (k - 1) | i]);
            }
        }
        for(int x = 0; x <= m; x++) cout << ans[x] << ' '; cout << '\n';
    } else {
        bcnt = (n + k - 1) / k;
        base[0] = m + 1;
        for(int i = 0; i < bcnt; i++) sz[i] = min(n, (i + 1) * k) - i * k;
        for(int i = 1; i <= bcnt; i++) base[i] = base[i - 1] * (sz[i - 1] + 1);
        for(int i = 1; i <= n; i++) cin >> s[i];
        dp[0][0] = 1;
        for(int r = 1, i = 1; r <= k; r++) {
            for(int p = 0; p < bcnt; p++) {
                if(p * k + r > n) continue;
                char c = s[p * k + r];
                int *f = dp[i ^ 1], *g = dp[i];
                if(c == '0') trans2<true, false>(f, g, p);
                else if(c == '1') trans2<false, true>(f, g, p);
                else trans2<true, true>(f, g, p);
                i ^= 1;
                cur[p]++;
            }
        }
        for(int i = 0; i < base[bcnt]; i++) add(ans[i % (m + 1)], dp[n & 1][i]);
        for(int i = 0; i <= m; i++) cout << ans[i] << ' '; cout << '\n';
    }

    return 0;
}