CF-1075-D2. Little String (Hard Version)（进行更加细致的分类讨论）（对于非 2 的幂次，不额外引入任何奇数素因子，总是最好的）

题目大意

1. 题目定义

给定一个长度为 $n$ 的字符串 $s$ （由 0、1、? 组成）和一个正整数 $c$ 。

函数 $f(w)$ 的定义：

对于一个仅含 0 和 1 的字符串 $w$ ，其值 $f(w)$ 表示满足以下条件的 $[0, 1, \dots, n-1]$ 全排列 $p$ 的总数：

对于 $1 \le i \le n$ ，如果 $w_i = 1$ ，则排列 $p$ 中必须存在至少一个连续子段，其 MEX 值为 $i$ 。
对于 $1 \le i \le n$ ，如果 $w_i = 0$ ，则排列 $p$ 中不得存在任何连续子段的 MEX 值为 $i$ 。

注：MEX（Minimum Excluded）指集合中未出现的最小非负整数。

2. 目标任务

通过将 $s$ 中的所有 ? 替换为 0 或 1 来构造字符串 $w$ 。在所有满足 $f(w)$ 不能被 $c$ 整除的字符串 $w$ 中，计算 $f(w)$ 的最小值。

3. 输出要求

输出该最小值对 $10^9 + 7$ 取模的结果。
若不存在满足条件的 $w$ ，则输出 $-1$ 。

4. 样例解释辅助理解

样例 3 ( $n=4, c=100, s=1001$ )：
字符串固定为 $1001$ 。此时 $f(1001) = 4$ ，满足条件的排列包括 $[0,2,3,1], [0,3,2,1], [1,2,3,0], [1,3,2,0]$ 。由于 $4$ 不能被 $100$ 整除，答案为 $4$ 。
样例 7 ( $n=5, c=8, s=100?1$ )：
若将 ? 替换为 0 得到 $w=10001$ ，经计算 $f(w) = 12$ 。由于 $12$ 不能被 $8$ 整除，且经比较这是所有可能替换中的最小值，故输出 $12$ 。
样例 2 ( $n=3, c=1, s=???$ )：
无论如何替换 ?，任何整数 $f(w)$ 都能被 $1$ 整除。因此不存在满足 “不能被 $c$ 整除” 条件的 $w$ ，输出 $-1$ 。

CF-1075-D1. Little String (Easy Version)（把序列生成的过程看成不断插入数字的过程）（插入过程可以写为一个循环，应该多少范围就多少范围，特判写在循环里面）

Untitled

思路讲解

那么是这样子的，这道题目如果把这个序列生成的这个过程看成从 $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

源代码

/**
 * 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

*/

Znzryb's Blog