专栏文章

题解：CF1698G Long Binary String

PPetit_Souris
CF1698G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip1cu0g
此快照首次捕获于
2025/12/03 04:33
3 个月前
此快照最后确认于
2025/12/03 04:33
3 个月前
查看原文
very cool problem
将问题表示成  mod 2\bmod 2 意义下形式幂级数的形式。
首先把前导零删掉，最后答案平移一下。设 F(x)F(x) 为输入串对应的多项式，那么我们要求的就是选择一些 F(x)xtF(x)x^t 加起来，得到形如 1+xk1 + x ^ k 的结果，那么答案就是 (0,k)(0, k)。
显然最后式子可以表示成 F(x)G(x)F(x)G(x) 的形式，G(x)G(x) 为任意多项式。即求 F(x)G(x)=1+xkF(x)G(x) = 1 + x ^ k。
两边对 F(x)F(x) 取模，得到 xk≡1(modF(x))x ^ k \equiv 1 \pmod {F(x)}（这是因为在  mod 2\bmod 2 意义下）。
看起来很像一个 BSGS 问题，而由于 deg⁡F(x)<n\deg F(x) < n，因此根据抽屉原理，k≤2n−1k\le 2^{n - 1}。（ mod F(x)\bmod F(x) 后只有 0∼n−20\sim n - 2 次项，每个系数两种方法，因此 2n−1+12^{n - 1} + 1 个 kk 中至少有两个相同的）
因此我们设 k=uB−vk = uB - v，其中 B=O(2n/2)B = \mathcal O(2^{n / 2})。那么即求 xuB≡xv(modF(x))x ^ {uB} \equiv x ^ v \pmod {F(x)}。预处理出 [0,B][0, B] 内的 xvx ^ v 和 xuBx ^ {uB}，枚举 uu 找到对应的 vv 即可。
 mod 2\bmod 2 多项式乘法取模可以压位，因此单次乘法 / 取模是 O(n)\mathcal O(n) 的。总时间复杂度为 O(2n/2n)\mathcal O(2^{n/2}n)。
代码我觉得我写的很帅。
CPP
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll B = 4e5 + 9;
ll n;
ull f, pw1[B + 5], pw2[B + 5];
char s[40];
ull Mul(ull F, ull G) {
    __uint128_t H = 0;
    rep(i, 0, n - 1) {
        if((F >> i) & 1) H ^= ((__uint128_t)G << i);
    }
    per(i, 2 * (n - 1), n - 1) {
        if((H >> i) & 1) H ^= ((__uint128_t)f << (i - n + 1));
    }
    return H;
}
map<ull, ll> mp;
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    scanf("%s", s), n = strlen(s);
    reverse(s, s + n);
    ll pre = 0;
    while(n && s[n - 1] == '0') --n, ++pre;
    if(!n) return puts("-1"), 0;
    reverse(s, s + n);
    while(s[n - 1] == '0') --n;
    rep(i, 0, n - 1) {
        if(s[i] == '1') f |= (1ull << i);
    }
    pw1[0] = 1;
    rep(i, 1, B) pw1[i] = Mul(pw1[i - 1], 2);
    rep(i, 0, B - 1) mp[pw1[i]] = i;
    pw2[0] = 1;
    rep(i, 1, B) pw2[i] = Mul(pw2[i - 1], pw1[B]);
    rep(u, 1, B) {
        if(mp.count(pw2[u])) {
            ll v = mp[pw2[u]];
            write(pre + 1), putchar(' '), write(pre + 1 + u * B - v), putchar('\n');
            return 0;
        }
    }
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...