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

题目大意

题目总结：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$ 的两段。

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

源代码

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