题解：CF2189D2 Little String (Hard Version)

znzryb · 2026-01-26 23:02:28 · 题解

思路讲解

那么是这样子的，这道题目如果把这个序列生成的这个过程看成从 0\sim n-1 不断插入的过程，那么如果 w_i=0，那么 i 就插入在原来 0\sim i-1 之间的空当中。w_i=1，只能插入在 0\sim i-1 的两段。

D1 当中，我们采用如上方法得到答案。

这道题目，其实想让我们求的是在不被 c 整除的前提下，能够得到的最小值。

那其实说白了，想让值比较小，那就除了首位，结尾，全部填 1 就完了（遇到？），不过现在就是这个不能被 c 整除比较烦。

当然，除了首位，当 i-1 为偶数的时候，也应该填写这个 ‘1’，因为反正都要引入 2，那不如就引入一个 2。

不过这道题目，其实就是一个分类讨论：

对于非 2 的幂次，不额外引入任何奇数素因子，总是最好的。因此，采用这个我们之前说的策略：

那就除了首位，结尾，全部填 1 就完了（遇到？时）

那么对于 2 的幂次，先不断填 2 进去，发现不行了，我们就回退，乘以 i-1，注意逆序遍历。

        // 对于 2 的幂次来说，能不引入 2 自然最好
        for (int i=N-1;i>=1;--i) {
            if (W[i]=='?') {
                ll ans_c_backup=ans_c,ans_backup=ans;
                ans_c*=2;
                ans_c%=C;
                ans*=2;
                ans%=mod;
                if (ans_c==0) {  // 发现不对，回退乘以 2，乘以 i-1
                    ans_c=ans_c_backup;
                    ans=ans_backup;
                    ans*=(i-1);
                    ans%=mod;
                    ans_c*=i-1;
                    ans_c%=C;
                }
            }
        }

不过是对于什么进行分类讨论呢？

我们上面有一些地方，加上原本的串，都已经确定了一些，把这一部分的值计算出来，我们记作 ans。那么我们知道，ans 与 C 的因子的交集就是 \gcd(ans,C)（可以用该式子计算： \gcd(ans,C)= \gcd(ans\mod C,C)）。那么 C 当中还没有被消掉的因子的集合就是：

\frac{C}{\gcd(ans,C)}

我们就是对还未被消掉的因子集合进行分类讨论。

AC代码

https://codeforces.com/contest/2189/submission/360006878

::::info[源代码]

/**
 * Problem: D2. Little String (Hard Version)
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/D2
 * Created: 2026-01-25 14:54:48
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ull N,C;
    cin >> N >> C;
    string W;
    cin>>W;
    W.insert(W.begin(),'#');
    if (W[1]=='?') {
        W[1]='1';
    }
    if (W[N]=='?') {
        W[N]='1';
    }
    if (W[1]!='1' || W[N]!='1') {
        cout<<-1<<"\n";
        return;
    }
    if (W[2]=='?') {
        W[2]='0';
    }
    for (int i=1;i<=N-1;++i) {
        if (W[i]=='?') {
            if ((i-1)%2==0) {
                W[i]='1';
            }
        }
    }
    ll ans=1,ans_c=1;
    for (int i=1;i<=N-1;++i) {
        if (W[i]=='?') {
            continue;
        }
        // 尝试往这个序列中插入 i
        if (W[i]=='1') {
            ans*=2;
            ans%=mod;
            ans_c*=2;
            ans_c%=C;
        }else {
            // 要破坏这个计划
            ans*=(i-1);
            ans%=mod;
            ans_c*=i-1;
            ans_c%=C;
        }
    }
    if (ans_c==0) {
        cout<<-1<<"\n";
        return;
    }
    ull rem_C=C/gcd(ans_c,(ll)C);
    if (has_single_bit(rem_C)) {
        // 对于 2 的幂次来说，能不引入 2 自然最好
        for (int i=N-1;i>=1;--i) {
            if (W[i]=='?') {
                ll ans_c_backup=ans_c,ans_backup=ans;
                ans_c*=2;
                ans_c%=C;
                ans*=2;
                ans%=mod;
                if (ans_c==0) {
                    ans_c=ans_c_backup;
                    ans=ans_backup;
                    ans*=(i-1);
                    ans%=mod;
                    ans_c*=i-1;
                    ans_c%=C;
                }
            }
        }
        if (ans_c==0) {
            cout<<-1<<"\n";
            return;
        }
        cout<<ans<<"\n";
    }else {
        // 对于非 2 的幂次，不额外引入任何奇数素因子，总是最好的
        for (int i=1;i<=N-1;++i) {
            if (W[i]=='?') {
                ans*=2;
                ans%=mod;
                ans_c*=2;
                ans_c%=C;
            }
        }
        if (ans_c==0) {
            cout<<-1<<"\n";
            return;
        }
        cout<<ans<<"\n";
    }

}

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

    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
1
3 3
???

1
20 253034496
10001100011000??????

AC
https://codeforces.com/contest/2189/submission/360006878

*/

::::