CF-1075-D1. Little String (Easy Version)（把序列生成的过程看成不断插入数字的过程）（插入过程可以写为一个循环，应该多少范围就多少范围，特判写在循环里面） · znzryb
## 题目大意
### 题目总结：Little String (Easy Version)
---
### **核心定义**
对于一个长度为 $n$ 的 01 字符串 $w$ 和集合 $\{0, 1, \dots, n-1\}$ 的全排列 $p$，定义 $f(w)$ 为满足以下所有条件的排列 $p$ 的总数：
- **若** $w_i = 1$**：** 排列 $p$ 中必须存在至少一个连续子段 $[p_l, \dots, p_r]$，使得该子段的 **MEX** 等于 $i$。
- **若** $w_i = 0$**：** 排列 $p$ 中不存在任何连续子段的 **MEX** 等于 $i$。
- **MEX 定义：** 集合中未出现的最小非负整数。例如 $\text{mex}([0, 1, 3]) = 2$，$\text{mex}([1, 2]) = 0$。
---
### **任务要求**
- **输入：** 长度为 $n$ 的字符串 $s$（在本简单版本中**不含问号**，即 $w = s$）和一个正整数 $c$。
- **目标：** 计算 $f(s)$。
- 如果 $f(s)$ **不能被** $c$ **整除**，输出 $f(s) \pmod{10^9 + 7}$。
- 如果 $f(s)$ **能被** $c$ **整除**，或者不存在满足条件的字符串（针对含问号版本），则输出 $-1$。
---
### **样例解释对照**
| **样例输入** | **n** | **s** | **c** | **f(s) 计算与结果** | **解释** |
| --- | --- | --- | --- | --- | --- |
| **样例 3** | 4 | `1001` | 100 | **输出：4** | 满足条件的排列有 $[0,2,3,1], [0,3,2,1], \\ [1,2,3,0], [1,3,2,0]$。$f(s)=4$ 不被 100 整除。 |
| **样例 6** | 5 | `10001` | 8 | **输出：12** | $f(s)=12$。其中一个合法排列为 $[0,4,3,2,1]$。$12$ 不被 8 整除。 |
| **样例 9** | 3 | `101` | 4 | **输出：2** | 合法排列为 $[0,2,1], [1,2,0]$。$f(s)=2$ 不被 4 整除。 |
| **样例 2** | 3 | `111` | 1 | **输出：-1** | 无论 $f(s)$ 为多少，任何整数都能被 $c=1$ 整除，故输出 $-1$。 |
## 思路讲解
题目中的条件，具体来说就是如上图所示，$w_i=0$，就是 $i$ 把 $0～i-1$ 分隔开，$w_i=1$，就是 $i$ 位于 $0～i-1$ 的左边或者右边。
那么是这样子的，这道题目如果**把这个序列生成的这个过程看成从** $0～n-1$ **不断插入的过程**，那么如果 $w_i=0$，那么 $i$ 就插入在原来 $0～i-1$ 之间的空当中。$w_i=1$，只能插入在 $0～i-1$ 的两段。
```cpp
for (int i=1;i<=N-1;++i) {
// 尝试往这个序列中插入 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;
}
}
```
然后这道题目就解决了。
## AC代码
AC
[https://codeforces.com/contest/2189/submission/359662289](https://codeforces.com/contest/2189/submission/359662289)
::: 源代码
```cpp
/**
* Problem: D1. Little String (Easy Version)
* Contest: Codeforces Round 1075 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2189/problem/D1
* Created: 2026-01-25 10:37:10
* 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)2e5+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() {
ll N,C;
cin >> N >> C;
string W;
cin>>W;
W.insert(W.begin(),'#');
if (W[1]!='1' || W[N]!='1') {
cout<<-1<<"\n";
return;
}
ll ans=1,ans_c=1;
// auto divide_c=[&](ll x) {
// while (x!=minp[x]) {
// x/=minp[x];
// if (opC%minp[x]==0) {
// opC/=minp[x];
// }
// }
// if (opC%minp[x]==0) {
// opC/=minp[x];
// }
// };
for (int i=1;i<=N-1;++i) {
// 尝试往这个序列中插入 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;
}
ans%=mod;
if (ans<0) ans+=mod;
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 1
111
*/
```
:::
## 心路历程（WA，TLE，MLE……）