CF-1075-D2. Little String (Hard Version)（进行更加细致的分类讨论）（对于非 2 的幂次，不额外引入任何奇数素因子，总是最好的） · znzryb
## 题目大意
### 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)（把序列生成的过程看成不断插入数字的过程）（插入过程可以写为一个循环，应该多少范围就多少范围，特判写在循环里面）](/2026/01/24/20260124-99858749)
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$，注意逆序遍历。
```cpp
// 对于 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代码
AC
[https://codeforces.com/contest/2189/submission/360006878](https://codeforces.com/contest/2189/submission/360006878)
::: 源代码
```cpp
/**
* 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
*/
```
:::
## 心路历程（WA，TLE，MLE……）