Znzryb's Blog

Hello 2026——E. LCM is Legendary Counting Master

Posted on 2026-01-28 Edited on 2026-02-19

题目大意

给定长度为 $n$ 的序列 $a$ 和正整数 $m$ 。 $a$ 的每个元素都是范围在 $[0, m]$ 内的整数。

如果且仅当以下两个条件满足时，序列 $a$ 被认为是好的：

$a_1<a_2<a_3<\ldots<a_n$ ，并且
$\frac{1} {\operatorname{lcm}(a_1,a_2)}+\frac{1} {\operatorname{lcm}(a_2,a_3)}+\ldots+\frac{1} {\operatorname{lcm}(a_{n-1},a_n)}+\color{red} {\frac{1} {\operatorname{lcm}(a_n,a_1)}}\ge1$ . $^{\text{∗}}$

你需要用范围在 $[1, m]$ 内的整数替换 $a$ 中的所有零。计算替换零的不同方式的数量，使得得到的序列 $a$ 是好的。

以 $998\,244\,353$ 取模后输出答案。

$^{\text{∗}}$ 两个正整数的最小公倍数( $\operatorname{lcm}$ )是能同时整除它们的最小正整数。例如， $\operatorname{lcm}(2,3)=6, \operatorname{lcm}(4,6)=12$ 。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）

CF-1075-E. Majority Wins?

Posted on 2026-01-27 Edited on 2026-03-07

题目大意

题目总结：Majority Wins?

1. 目标

给定一个长度为 $n$ 的二进制字符串 $s$ ，通过最少总代价的操作将其最终转化为一个只包含字符 1 的字符串（即长度为 1 且内容为 1）。

2. 操作定义

在当前字符串中选择一段连续的子串 $g[l \dots r]$ ，计算其中 0 和 1 出现的次数：

如果某个字符出现的次数 不少于 另一个字符（即出现次数 $\ge$ 另一方），则可以用该字符替换掉整个子串。
操作代价：等于该子串的长度，即 $r - l + 1$ 。
你可以进行多次操作，每次操作后的字符串长度会缩短。

例如，字符串010010可以通过用成本为 $4$ 的操作将子串1001替换为1来在一次操作中转换为010；字符串1111可以通过在整个字符串上执行成本为 $4$ 的操作转换为1；字符串0100可以通过取子串100转换为00。

3. 输出要求

输出将字符串转化为 1 的最小总代价。
如果无法转化，则输出 1。

样例解释

样例 1 (0)：由于只有一个 0，无法通过任何操作产生 1。输出 1。
样例 2 (1)：已经是 1，无需操作。输出 0。
样例 4 (10)：选择子串 10（长度 2），其中 1 的数量（1个）不少于 0 的数量（1个），可替换为 1。代价为 2。
样例 5 (010)：
1. 选择子串 01 替换为 1，字符串变为 10，代价为 $2$ 。
2. 选择子串 10 替换为 1，代价为 $2$ 。
3. 总代价 $2 + 2 = 4$ 。
样例 6 (00111000)：
1. 选择子串 00111（1 占多数）替换为 1，字符串变为 1000，代价 $5$ 。
2. 选择子串 10（1 不少于 0）替换为 1，字符串变为 100，代价 $2$ 。
3. 再次对 10 进行操作变为 1，字符串变为 1，代价 $2$ 。
4. 总代价 $5 + 2 + 2 = 9$ 。

思路讲解

~~其实这道题目就是一个分类讨论，感觉放在 C 也没什么问题。~~

E was proposed as C, and C as B

不难发现，答案再大，不会超过 $n+3$ 。

然后直接输出 $n$ 的情况就是 1 的数量大于等于 0 的数量的时候。

输出 $n+1$ 是什么情况呢？首先 01 串首部或者尾部为 1 时，输出这个 $n+1$ 。

还有就是当存在一个位置，使得 $\text{suf}(1)≥\text{suf}(0)+1$ 数量的时候（这个是因为多容纳一个 0 也没事）（ $\text{suf}(x)$ 代表该位置后缀 $x$ 数量）。

同理可得 $\text{pre}(1)≥\text{pre}(0)+1$ 。

那么什么时候输出这个 $n+2$ 呢？当存在一个位置，使得 $\text{suf}(1)≥\text{suf}(0)$ 数量的时候（表示肯定有 0 嘛，那么我们不妨消掉一个，就可以回到上面一种情况）。

同理可得 $\text{pre}(1)≥\text{pre}(0)$ 。

其他情况，就输出 $n+3$ 。

然后，你忐忑地提交了，发现 WA 了，为什么呢？对拍！

1
2
3

1
10
0000110000

该样例也应该输出这个 $n+2$ ，但是我们输出了 $n+3$ ，这个是因为什么呢？

我们发现 ‘11' 这个东西非常特殊，可以压制两边的 0，你会发现，‘101’ 就不可以压制两边的 0 了。

因此，只要找到 ‘11' 那么答案不会大于 $n+2$ 。

1
2
3

if (s.find("11")!=string::npos) {
    ans=min(ans,N+2);
}

再次忐忑地提交，你发现竟然过了？

AC代码

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

源代码

/**
 * Problem: E. Majority Wins?
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/E
 * Created: 2026-01-27 23:48:36
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#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 = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    string s;
    cin>>s;
    if (s=="1") {
        cout<<0<<"\n";
        return;
    }
    ll cnt1=count(all(s),'1'),cnt0=count(all(s),'0');
    if (cnt1==0) {
        cout<<-1<<"\n";
        return;
    }
    if (cnt1>=cnt0) {
        cout<<N<<"\n";
        return;
    }
    if (s.front()=='1') {
        cout<<N+1<<"\n";
        return;
    }
    if (s.back()=='1') {
        cout<<N+1<<"\n";
        return;
    }
    s.insert(s.begin(),'#');
    vector<ll> pre_sum_1(N+2),suf_sum_1(N+2),pre_sum_0(N+2),suf_sum_0(N+2);
    for (int i=1;i<=N;++i) {
        pre_sum_1[i]=pre_sum_1[i-1]+(s[i]=='1');
        pre_sum_0[i]=pre_sum_0[i-1]+(s[i]=='0');
    }
    for (int i=N;i>=1;--i) {
        suf_sum_1[i]=suf_sum_1[i+1]+(s[i]=='1');
        suf_sum_0[i]=suf_sum_0[i+1]+(s[i]=='0');
    }
    if (suf_sum_1[2]>=suf_sum_0[2]) {
        cout<<N+1<<"\n";
        return;
    }
    if (pre_sum_1[N-1]>=pre_sum_0[N-1]) {
        cout<<N+1<<"\n";
        return;
    }
    ll ans=N+3;
    for (int i=1;i<=N;++i) {
        if (suf_sum_1[i]>=suf_sum_0[i]+1) {
            ans=min(ans,N+1);
        }
        if (pre_sum_1[i]>=pre_sum_0[i]+1) {
            ans=min(ans,N+1);
        }
        if (pre_sum_1[i]>=pre_sum_0[i]) {
            ans=min(ans,N+2);
        }
        if (suf_sum_1[i]>=suf_sum_0[i]) {
            ans=min(ans,N+2);
        }
    }
    if (s.find("11")!=string::npos) {
        ans=min(ans,N+2);
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

暴力程序

/**
 * Problem: E. Majority Wins?
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/E
 * Created: 2026-01-28 14:48:13
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#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 = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    string s;
    cin>>s;
    if (count(all(s),'1')==0) {
        cout<<-1<<"\n";
        return;
    }
    ll ans=N+3;
    auto dfs=[&](auto && self,string str,ll consume,ll phase) {
        if (phase>=5) {
            return;
        }
        if (consume>=ans) {
            return;
        }
        if (str=="1") {
            ans=min(ans,consume);
            return;
        }
        if (str.size()<=1) {
            return;
        }
        for (int i=0;i<str.size();++i) {
            for (int j=i;j<str.size();++j) {
                ll cnt1=count(str.begin()+i,str.begin()+j+1,'1');
                ll cnt0=count(str.begin()+i,str.begin()+j+1,'0');
                ll len=j-i+1;
                if (cnt1>=cnt0) {
                    string to_str=string(str.begin(),str.begin()+i)+"1"+string(str.begin()+j+1,str.end());
                    self(self,to_str,consume+len,phase+1);
                }
                if (cnt0>=cnt1) {
                    string to_str=string(str.begin(),str.begin()+i)+"0"+string(str.begin()+j+1,str.end());
                    self(self,to_str,consume+len,phase+1);
                }
            }
        }
    };
    dfs(dfs,s,0,1);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
1
2
10

*/

数据生成器

/**
 * Problem: E. Majority Wins?
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/E
 * Created: 2026-01-28 15:06:38
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#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 = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Solve() {
    // ll N;
    // cin >> N;
    ll N=uniform_int_distribution<ll>(3,10)(rng);
    cout<<1<<"\n";
    cout<<N<<"\n";
    for (int i=1;i<=N;++i) {
        if (bernoulli_distribution(0.7)(rng)) {
            cout<<0;
        }else {
            cout<<1;
        }
        // cout<<uniform_int_distribution<ll>(0,1)(rng);
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // cin >> lT;
    // while(lT--)
        Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）

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

Posted on 2026-01-25 Edited on 2026-03-07

题目大意

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

*/

心路历程（WA，TLE，MLE……）

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

Posted on 2026-01-24 Edited on 2026-02-19

题目大意

题目总结：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代码

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

CF-1075-B. The Curse of the Frog（遇到一个值，可以直接减掉的话最好，避免后续处理）

Posted on 2026-01-24 Edited on 2026-02-19

题目大意：B. The Curse of the Frog

一只青蛙位于数轴的 $0$ 点，目标是到达坐标 $x$ 。青蛙掌握 $n$ 种跳跃技能，每种技能 $i$ 包含三个参数：

$a_i$ ：最大跳跃距离。单次跳跃可从 $k$ 移动到 $[k, k + a_i]$ 范围内的任意整数点。
$b_i$ ：回滚周期。每当第 $b_i, 2b_i, 3b_i \dots$ 次使用该技能时，会触发诅咒。
$c_i$ ：回滚距离。触发诅咒时，青蛙会先从当前位置 $k$ 后退到 $k - c_i$ ，然后再进行跳跃，最终落点范围为 $[k - c_i, k - c_i + a_i]$ 。

目标： 计算到达 $x$ 点所需经历的最小回滚总次数。如果无法到达，则输出 $-1$ 。

样例解释

样例 1

输入： $x=1$ , 技能： $a=3, b=3, c=3$ 。
过程： 第一次使用技能，不触发回滚（因为 $1 < b=3$ ）。直接从 $0$ 跳到 $1$ 。
结果： $0$ 次回滚。

样例 4

输入： $x=8$ , 拥有 $5$ 种技能。其中包含 $(12, 1, 11)$ 和 $(10, 1, 4)$ 等。
过程：
1. 使用第 $1$ 种技能（ $b=1$ ）：触发回滚，从 $0$ 退到 $-11$ ，跳到 $1$ 。
2. 使用第 $4$ 种技能（ $b=2$ ）：这是该技能第 $1$ 次使用，不回滚，从 $1$ 跳到 $2$ 。
3. 使用第 $2$ 种技能（ $b=1$ ）：触发回滚，从 $2$ 退到 $-2$ ，跳到 $8$ 。
结果： 总计 $2$ 次回滚。

样例 6

输入： $x=10$ , 技能： $a=2, b=2, c=1$ 。
过程：
- 第 $1$ 次跳：不回滚， $0 \to 2$ 。
- 第 $2$ 次跳：回滚（第 $b=2$ 次）， $2 \to 1 \to 3$ 。
- 第 $3$ 次跳：不回滚， $3 \to 5$ 。
- 第 $4$ 次跳：回滚（第 $2b=4$ 次）， $5 \to 4 \to 6$ 。
- 以此类推，通过交替回滚逐步前进。
结果： 总计 $3$ 次回滚。

思路讲解

starsilk 的代码。不需要的值，我们其实可以减掉。会清爽一些。

然后最后的这个向上取整除法，可以这样子想，没消耗一个回滚，可以前行多少距离？ $w\gets a\times b-c$ 。这个可以这么看，你先回滚 $-c$ （因为前面的免费步已经用完了），然后可以走 $b$ 步，每步 $a$ 的长度。

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T;
	long long n,x,i,a,b,c,w;
	for(cin>>T;T>0;T--)
	{
		cin>>n>>x;
		w=0;
		for(i=0;i<n;i++)
		{
			cin>>a>>b>>c;
			x-=(b-1)*a;
			w=max(w,a*b-c);
		}
		if(x<=0)cout<<"0\n";
		else if(w==0)cout<<"-1\n";
		else cout<<(x+w-1)/w<<'\n';
	}
	return 0;
}

AC代码

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

源代码

/**
 * Problem: B. The Curse of the Frog
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/B
 * Created: 2026-01-23 22:41:09
 * 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 = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
struct Abc {
    ll a,b,c;
};
void Solve() {
    ll N,X;
    cin >> N >> X;
    vector<Abc> abc_vec(N);
    ll mx_w=0;
    for (int i=0;i<N;++i) {
        ll a,b,c;
        cin>>a>>b>>c;
        abc_vec[i]={a,b,c};
        X-=a*(b-1);
        ll w=a*b-c;
        mx_w=max(mx_w,w);
    }
    if (X<=0) {
        cout<<0<<"\n";
        return;
    }
    if (mx_w==0)  {
        cout << -1 << "\n";
        return;
    }
    cout<<(X+mx_w-1)/mx_w<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2189/submission/359582687

*/