2022 Jiangsu Collegiate Programming Contest H Super Gray Pony

题目描述

https://codeforces.com/gym/103743/problem/H

简要题意：给定一个长度为 $n$ 的 $01$ 序列 $a_i$，现在要执行 $k$ 次操作，每次操作将所有 $a_i$ 异或上 $a_{i-1}$ 得到 $a’_i$，求最终的序列

$n\le 3\times 10^6,k\le 10^9$

Solution

简单分析容易得到 $a_i=\sum_{j=0}^i\binom{k}{i-j}a_j\bmod 2$，注意到模 $2$，那么组合数 $\binom{k}{x}$ 不等于 $0$ 当且仅当 $x$ 是 $k$ 的子集

那么如果我们取 $k=2^t$，那么 $\binom{k}{x}$ 只有当 $x$ 等于 $k$ 和 $0$ 是才为 $1$，那么我们可以将 $k$ 二进制拆分，每次做 $2$ 的次幂次操作，操作可以用 $bitset$ 加速

时间复杂度 $O(\frac{n\log k}{64})$

#include <iostream>
#include <bitset>
#define maxn 3000010
using namespace std;

int n, m;
char s[maxn];

bitset<maxn> f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> s + 1; 
    for (int i = 1; i <= n; ++i) f[i] = s[i] == '1';
    for (int o = 0; o < 30; ++o) {
        if (!(m >> o & 1)) continue;
        f ^= f << (1 << o);
    }
    for (int i = 1; i <= n; ++i) cout << f[i]; cout << "\n";
    return 0;
}