Znzryb's Blog

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——B. DJ Nicholas（get_range_cnt，可以变为 get_pref_cnt(r)-get_pref_cnt(l - 1)，是一个非常经典的套路）

Posted on 2026-03-07 Edited on 2026-03-23

题目大意

题目设定
给定一个包含 $k$ （ $1 \le k \le 26$ ）首短歌的曲库，分别用前 $k$ 个大写英文字母表示。
由这 $k$ 首歌可以生成一个无限长的母带（master track） $t$ 。生成方式为：不断重复这 $k$ 首歌，但在每一次重复整个曲库时，都会将当前序列的第一首歌移动到序列的末尾。
例如，当 $k = 4$ 时，曲库初始为 ABCD，那么母带 $t$ 就是无限长的字符串 ABCD BCDA CDAB DABC ABCD ...。

有一个长度为 $n$ 的播放列表，初始时全部为空白。在此问题中，播放列表和母带均从 1 开始索引。

操作要求
需要对播放列表执行 $q$ 次操作，操作分为以下两种：

+ i a b：将播放列表中从位置 $a$ 到 $b$ （包含两端）的片段，替换为母带 $t$ 中从位置 $i$ 开始、长度为 $b - a + 1$ 的子串。
? a b：查询播放列表中从位置 $a$ 到 $b$ （包含两端）的片段。输出 $k$ 个整数，其中第 $j$ 个整数表示该片段中第 $j$ 个英文字母（即第 $j$ 首歌）的出现次数。

输入格式
第一行包含三个空格分隔的整数 $k$ 、 $n$ 和 $q$ 。
接下来 $q$ 行，每行描述一个操作，格式为 + i a b 或 ? a b。

输出格式
对于每一个 ? a b 操作，输出一行包含 $k$ 个空格分隔的整数，表示查询的结果。

数据范围
$1 \le k \le 26$
$1 \le n \le 10^9$
$1 \le q \le 10^5$
每次操作中： $1 \le i \le 10^9$ ， $1 \le a \le b \le n$

样例输入

样例输出

1 2 1 1

样例解释
在此样例中， $k = 4$ 且 $n = 10$ 。母带 $t$ 为 ABCDBCDACDABDABC...。
播放列表初始为空，我们用星号代表空白部分：**********。

执行 + 7 2 6：
我们需要一个长度为 $6 - 2 + 1 = 5$ 的子串。
母带 $t$ 中从位置 7 开始、长度为 5 的子串是 DACDA。
将播放列表中第 2 到第 6 首歌替换为该子串，此时播放列表变为：DACDA****。
执行 + 2 8 10：
播放列表第 8 到 10 的位置被替换后变为：DACDA*BCD。
执行 + 9 1 4：
覆盖掉前 4 个位置的歌曲，播放列表最终变为：CDABDA*BCD。
执行 ? 4 9：
查看当前播放列表中第 4 到第 9 首歌，对应片段为 BDA*BC。
需要输出 A、B、C、D 四个字母在此片段内分别出现的次数。因此，输出 1 2 1 1。

思路讲解

其实还是很明显的动态开点线段树。我说白了是个动态开点线段树的云玩家，我都看出来是动态开点线段树了。

P13825 【模板】线段树 1.5（指针式动态开点线段树）

既然是这个动态开点线段树，我们想一想，我们的 apply 函数如何书写吧。

其实最重要的是，在知道母带上 l，r 的情况下，求出母带上的 cnt 数组。

get_range_cnt，可以变为 get_pref_cnt®-get_pref_cnt(l - 1)，是一个非常经典的套路。

array<int, 26> get_range_cnt(ll l, ll r) {
    auto R = get_pref_cnt(r);
    auto L = get_pref_cnt(l - 1);
    for (int i = 0; i < k; ++i) {
        R[i] -= L[i];
    }
    return R;
}

AC代码

AC
https://codeforces.com/gym/106262/submission/365836934

源代码

/**
 * Problem: B. DJ Nicholas
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/B
 * Created: 2026-03-04 17:34:48
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

ll K;
/*
 *
 */
using arr=array<unsigned int,27>;
bool is_init=false;
vector<vector<ll>> next_ch_rem_pos(28,vector<ll>(28));
arr get_pref(ll r) {
    arr res{};
    if (r==0) {
        return res;
    }

    if (!is_init) {
        vector<ll> str(K*K+2);
        for (int i=1;i<=K;++i) {
            for (int j=1;j<=K;++j) {
                str[K*(i-1)+j]=j;
            }
        }
        for (int i=1;i<=K;++i) {
            rotate(str.begin()+K*(i-1)+1,str.begin()+K*(i-1)+i,str.begin()+K*(i-1)+K+1);
        }
        // 怕这个遍历影响常数？直接存下来不就行了？
        for (int ch=1;ch<=K;++ch) {
            for (int i=1;i<=K*K;++i) {
                if (str[i]==ch) {
                    next_ch_rem_pos[ch][((i-1)/K)]=i;
                }
            }
        }
        is_init=true;
    }

    for (int i=1;i<=K;++i) {
        res[i]+=r/K;
        ll rot=((r/K*K+1-1)/K)%K;
        ll next_pos=next_ch_rem_pos[i][rot]+r/(K*K)*(K*K);
        if (next_pos<=r) {
            ++res[i];
        }
    }
    return res;
}
arr operator-(arr a, arr b) {
    for (int i=1;i<=K;++i) {
        a[i]-=b[i];
    }
    return a;
}
arr get_range(ll l,ll r) {
    // st 是 1-based，我们先切换成 0-based
    return get_pref(r)-get_pref(l-1);
}
struct Tag {
    // 在母串中的这个位置
    ll base=0;
    bool need_apply=false;
    void apply(const Tag &t,ll offset) {
        base=t.base+offset;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    arr cnt{};
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        for (int i=1;i<=26;++i) {
            res.cnt[i]+=b.cnt[i];
        }
        return res;
    }
    void apply(const Tag&t,ll offset) {
        if (!t.need_apply) return;
        cnt=get_range(t.base+offset,t.base+offset+r-l);
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
// template<class I=Info,class T=Tag>
struct SEG {
    // 如果不需要泛型，可以用下面的来替代
    using I=Info;
    using T=Tag;
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag,0);
            u->rs->info.apply(u->tag,u->rs->info.l - u->info.l);
            u->ls->tag.apply(u->tag,0);
            u->rs->tag.apply(u->tag,u->rs->info.l - u->info.l);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,T t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t,u->info.l-l);
            u->tag.apply(t,u->info.l-l);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

void Solve() {
    ll N,Q;
    cin >> K >> N >> Q;
    SEG seg(N);
    for (int i=1;i<=Q;++i) {
        char op;
        cin>>op;
        if (op=='+') {
            ll base,l,r;
            cin>>base>>l>>r;
            seg.modify(seg.root,l,r,{base,true});
        }else {
            ll l,r;
            cin>>l>>r;
            Info res=seg.query(seg.root,l,r);
            for (int j=1;j<=K;++j) {
                cout<<res.cnt[j]<<" ";
            }
            cout<<"\n";
        }
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106262/submission/365836934

*/

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

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——D. Drinking Culture（把概率，转化为可行域面积占总面积的比重，这一点对两参数随意取的概率问题特别有用，三参数随意取的就是算体积占比？我猜）

Posted on 2026-03-07 Edited on 2026-03-23

题目大意

题目总结

Bob 有 $n$ 瓶酒精饮料，标号为 $1$ 到 $n$ 。已知第 $i$ 瓶饮料包含 $v_i$ 单位的液体体积，其中有 $a_i$ 单位是纯酒精（ $0 \le a_i \le v_i$ ）。因此，第 $i$ 瓶饮料的酒精浓度为 $a_i / v_i$ 。每瓶饮料是完全均匀的，从中取出任意体积的液体，其酒精浓度均保持不变。

Bob 可以从这些瓶子中选择任意组合，并从每瓶中取出任意体积（不必须为整数）的液体进行混合。

现在提出一个挑战：
令 $V = \sum_{i=1}^n v_i$ 为所有瓶子中液体的总体积。
在 $[0, V]$ 区间内均匀随机生成一个实数 $s$ （目标总体积）；
在 $[0, 1]$ 区间内均匀随机生成一个实数 $f$ （目标酒精浓度）。

请计算：Bob 能够成功调配出总体积恰好为 $s$ 、且酒精浓度恰好为 $f$ 的饮品的概率是多少？（输出结果与标准答案的绝对或相对误差需不超过 $10^{-8}$ ）。

输入格式
第一行包含一个整数 $n$ （ $2 \le n \le 2 \times 10^5$ ）。
第二行包含 $n$ 个整数，依次为 $v_1, v_2, \dots, v_n$ （ $1 \le v_i \le 10^9$ ）。
第三行包含 $n$ 个整数，依次为 $a_1, a_2, \dots, a_n$ （ $0 \le a_i \le v_i$ ）。

样例输入

1
2
3

3
350 750 330
140 131 16

样例输出

1	0.19356182654786474591

样例解释
在这个样例中，所有液体的总体积 $V = 350 + 750 + 330 = 1430$ 。

我们可以考虑两种具体的情况：
第一种情况：假设生成的 $s = 500$ 且 $f = \frac{3}{13}$ 。此时 Bob 是可以成功调配的。例如，他可以从第 $1$ 瓶中取出 $\frac{97750}{377}$ 单位的液体，从第 $3$ 瓶中取出 $\frac{90750}{377}$ 单位的液体。
调配出的总体积为 $\frac{97750}{377} + \frac{90750}{377} = \frac{188500}{377} = 500$ 。
调配出的酒精浓度为：

\frac{\frac{97750}{377} \times \frac{140}{350} + \frac{90750}{377} \times \frac{16}{330}}{500} = \frac{3}{13}

第二种情况：假设生成的 $s = 814$ 且 $f = 0.1234567$ 。此时 Bob 是无法完成调配的，因为利用他现有的饮料集合无法混合出该体积和浓度的饮品。

综合考虑所有可能在给定范围内均匀生成的 $s$ 和 $f$ 的数值对 $(s, f)$ ，Bob 能够成功调配的概率约为 $0.19356182654786474591$ 。

思路讲解

把概率，转化为可行域面积占总面积的比重，这一点对两参数随意取的概率问题特别有用。

具体而言，我们的这个分段函数应该长这样：

其不定积分是长这样的，带进去值，算一下定积分即可。

AC代码

AC
https://qoj.ac/submission/2106344
AC
https://codeforces.com/gym/106262/submission/365722146

源代码

/**
 * Problem: D. Drinking Culture
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/D
 * Created: 2026-03-07 17:50:25
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 = 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,testcase;

/*
 *
 */
struct V_A {
    ll v,a;
    // concentration
    DB c;
};
DB calVal(ll A,ll V,DB c,ll x) {
    if (x<=0) {
        return 0;
    }
    DB res=A*log(x)+c*x-c*V*log(x);
    return res;
}
void Solve() {
    ll N;
    cin >> N;
    // vector<ll> A(N+2),V(N+2);
    vector<V_A> wine_inc(N+2);
    ll sumv=0;
    for (int i=1;i<=N;++i) {
        cin>>wine_inc[i].v;
        sumv+=wine_inc[i].v;
    }
    for (int i=1;i<=N;++i) {
        cin>>wine_inc[i].a;
        wine_inc[i].c=DB(wine_inc[i].a)/wine_inc[i].v;
    }
    vector<V_A> wine_dec=wine_inc;
    sort(wine_inc.begin()+1,wine_inc.begin()+N+1,[](const V_A &a,const V_A &b) {
        return a.c<b.c;
    });
    sort(wine_dec.begin()+1,wine_dec.begin()+N+1,[](const V_A &a,const V_A &b) {
        return a.c>b.c;
    });
    DB mn_area=0;
    do {
        ll upA=0;
        ll upV=0;
        for (int i=1;i<=N;++i) {
            ll curV=upV+wine_inc[i].v;
            mn_area+=calVal(upA,upV,wine_inc[i].c,curV)-calVal(upA,upV,wine_inc[i].c,upV);
            upA=upA+wine_inc[i].a;
            upV=upV+wine_inc[i].v;
        }
    }while (false);
    DB mx_area=0;
    do {
        ll upA=0;
        ll upV=0;
        for (int i=1;i<=N;++i) {
            ll curV=upV+wine_dec[i].v;
            mx_area+=calVal(upA,upV,wine_dec[i].c,curV)-calVal(upA,upV,wine_dec[i].c,upV);
            upA=upA+wine_dec[i].a;
            upV=upV+wine_dec[i].v;
        }
    }while (false);
    DB area=mx_area-mn_area;
    DB ans=area/sumv;
    cout<<fsp(15)<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2106344
AC
https://codeforces.com/gym/106262/submission/365722146

*/

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

注意，分段函数不是线性的，而是一个分段反比例函数。

不要一会用 x，一会用 v，但是代表同一个意思。

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——I. Stone Steps（在解决样例中出现的问题的时候，处理问题的方式尽量的这个能够和原来的方式有所关联，或者说，样例中出现的问题是提示我们思路中的漏洞，我们最好进行重新推导）

Posted on 2026-03-07 Edited on 2026-03-09

题目大意

题目名称： Stone Steps

题目描述：
给定一个仅包含非零十进制数字的字符串 $s$ （长度 $1 \le |s| \le 5 \times 10^5$ ）。

对于任意不包含数字 0 的正整数 $n$ ，定义 $H(n)$ 为将 $n$ 的所有数位按非降序（从小到大）重新排序后得到的新整数。例如： $H(1971) = 1179$ ， $H(3) = 3$ 。

你的任务是计算字符串 $s$ 的所有非空连续子串所代表的十进制整数的 $H$ 函数值之和。即对于所有满足 $1 \le i \le j \le |s|$ 的子串 $s[i...j]$ ，求出 $H(s[i...j])$ 并求和。最终的结果需要对 1000696967 取模后输出。

输入格式：
单行输入一个字符串 $s$ 。

输出格式：
输出一个整数，表示所有非空连续子串的 $H$ 函数值之和对 1000696967 取模的结果。

样例 1：

输入：
3141

输出：
1432

样例 1 解释：
当 $s$ 为 3141 时，共有 10 个非空连续子串，计算过程如下：

$s[1...1]$ 为 3， $H(3) = 3$
$s[2...2]$ 为 1， $H(1) = 1$
$s[3...3]$ 为 4， $H(4) = 4$
$s[4...4]$ 为 1， $H(1) = 1$
$s[1...2]$ 为 31， $H(31) = 13$
$s[2...3]$ 为 14， $H(14) = 14$
$s[3...4]$ 为 41， $H(41) = 14$
$s[1...3]$ 为 314， $H(314) = 134$
$s[2...4]$ 为 141， $H(141) = 114$
$s[1...4]$ 为 3141， $H(3141) = 1134$

将其相加得： $3 + 1 + 4 + 1 + 13 + 14 + 14 + 134 + 114 + 1134 = 1432$ 。

样例 2：

输入：
1

输出：
1

样例 3：

输入：
11234567891234567891

输出：
43138332

思路讲解

还是要使用拆分算贡献的思想。

我们还需要利用一个东西，就是数位，其实只有 9 个，所以我们不用想着一次遍历去解决，可以遍历 9 次。

不过，我认为最有用的，还是把这个所有的东西，贡献，全部写下来。然后看看有什么规律。全部都写下来以后，我们发现这个规律非常的简单。

然后就跟着上面的这个公式求就完了。

以样例一具体而言就是：

推这种式子就是要细心。

AC代码

https://codeforces.com/gym/106262/submission/365694725

源代码

/**
 * Problem: I. Stone Steps
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/I
 * Created: 2026-03-07 12:15:37
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10/*, INF = (1ll<<61)-1*/;
static constexpr ll mod = 1000696967;
// static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
ll pow10[MAXN];
void Solve() {
    string s;
    cin>>s;
    ll N=SZ(s);
    s.insert(s.begin(),'#');
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        A[i]=s[i]-'0';
    }
    ll ans=0;
    // set<ll> st_pos;
    for (int d=1;d<=9;++d) {
        vector<ll> suf_sum_diff_gt_d(N+2)/*,suf_cnt_gt_d(N+2)*/;
        vector<ll> suf_pos(N+2);
        suf_pos[N+1]=N+1;
        do {
            vector<ll> i_vec;
            i_vec.push_back(N+1);
            for (ll i=N;i>=1;--i) {
                suf_sum_diff_gt_d[i]=suf_sum_diff_gt_d[i+1];
                suf_pos[i]=suf_pos[i+1];
                // suf_cnt_gt_d[i]=suf_cnt_gt_d[i+1];
                if (A[i]>=d) {
                    suf_sum_diff_gt_d[i]+=i_vec.back()-i;
                    suf_sum_diff_gt_d[i]*=10;
                    suf_sum_diff_gt_d[i]%=mod;
                    suf_pos[i]=i;
                    i_vec.push_back(i);
                    // suf_cnt_gt_d[i]++;
                }
            }
        }while (false);

        vector<ll> i_pos;
        // 哨兵节点
        i_pos.push_back(0);
        ll glo_sum=0;
        for (int i=1;i<=N;++i) {
             if (A[i]>d) {
                 glo_sum*=10;
                 glo_sum%=mod;
                 glo_sum+=i-i_pos.back();
                 i_pos.push_back(i);
             }else if (A[i]==d) {
                 ll sum=glo_sum;
                 sum*=10;
                 sum%=mod;
                 sum+=i-i_pos.back();
                 // lsum 是在前面的，所有的值的条件下，的贡献
                 ll lsum=A[i]*sum%mod;
                 // lans 是算的是后面的
                 ll lans=sum*suf_sum_diff_gt_d[i+1]%mod;
                 lans+=sum*(suf_pos[i+1]-(i+1))%mod;
                 lans%=mod;
                 lans*=A[i];
                 lans%=mod;
                 ans+=lans;
                 ans+=lsum;
                 ans%=mod;
                 ans%=mod;
             }
        }
    }
    ans%=mod;
    if (ans<0) {
        ans+=mod;
    }
    cout<<ans<<"\n";
    // mod 1000696967
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    pow10[0]=1;
    for (int i=1;i<=MAXN-5;++i) {
        pow10[i]=pow10[i-1]*10;
        pow10[i]%=mod;
    }
    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

_______________[ Stress test, testcase 14 INPUT ]_______________
832

_______________[ Stress test, testcase 14 OUTPUT]_______________
282

expected：312

*/

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

在处理 lans，也就是背后的时候，忘记处理了不含 i7 的情况，即什么都不含，只含 i5 的背后情况。

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——J. Tic-Tac-Toe on a Graph（遇到图上问题，没有特殊结构，那么基本就是分类讨论，按度数进行分类讨论）

Posted on 2026-03-06 Edited on 2026-03-07

题目大意

题目描述
Alice 和 Bob 在一个无向简单图上玩改进版的井字棋游戏。这个图有 $n$ 个顶点（代表方格）和 $m$ 条边。
游戏规则如下：

初始时，所有顶点都是空的。
两人轮流行动，Alice 先手。
在 Alice 的回合，她选择一个空的顶点并画上 X。
在 Bob 的回合，他选择一个空的顶点并画上 O。
游戏总共进行 5 个回合，也就是说 Alice 总是行动 3 次，Bob 总是行动 2 次。
如果 Alice 能够将她画了 X 的 3 个顶点连成一条长度为 3 的路径（注意：这 3 个顶点在路径中的顺序不一定与她落子的顺序相同），那么 Alice 获胜。如果 Bob 能阻止这一切发生，则 Bob 获胜。

假设双方在第一步之后都采取完美策略。请计算：Alice 有多少种可能的第一步选择，使得无论 Bob 随后如何应对，她都必胜？

输入格式
第一行包含两个由空格分隔的整数 $n$ 和 $m$ （ $5 \le n \le 2 \times 10^5, 0 \le m \le \min(2 \times 10^5, n(n - 1)/2)$ ），分别表示图的顶点数和边数。
接下来 $m$ 行，每行包含两个由空格分隔的整数 $u$ 和 $v$ （ $1 \le u, v \le n$ ），表示顶点 $u$ 和 $v$ 之间有一条边。
保证图中没有自环和重边。

输出格式
输出一个整数，表示能让 Alice 必胜的初始落子位置的数量。

样例输入

样例输出

样例解释

对于该图，如果 Alice 第一步下在顶点 1、2、3、4 或 5，那么在双方完美发挥的情况下，她必定能获胜。
以第一步下在顶点 1 为例，其中一种可能的游戏进程是：

Alice 在 1 画 X
Bob 在 4 画 O
Alice 在 2 画 X
Bob 在 3 画 O
Alice 在 7 画 X
此时 Alice 在 1、2、7 画了 X，它们构成了一条长度为 3 的路径（1-2-7），因此 Alice 获胜。
如果她第一步下在 6、7 或 8，那么在 Bob 完美应对的情况下，她注定会输。
必胜的起始点有 5 个，因此输出 5。

思路讲解

遇到图上问题，没有特殊结构以及这个数据比较大，那么基本上就可以排除 dp 的可能性了。

那说白了，我们还有其他工具吗？

我们回归原始，对度数进行分类讨论。

首先，度数 ≥ 4，一定是必胜起始点。

度数为 3 的时候，不难得出：⚠️ 注意：需要两个，否则你刚走一步，他就把你唯一一条生路给堵死了，你不就死了吗。

度数为 2 的情况：

度数为 1 自然是不可能的。

然后好像就做完了？绷不住了

AC代码

AC
https://codeforces.com/gym/106262/submission/365635347

源代码

/**
 * Problem: J. Tic-Tac-Toe on a Graph
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/J
 * Created: 2026-03-06 11:12:30
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<ll>> g(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll ans=0;
    for (int u=1;u<=N;++u) {
        if (SZ(g[u])>=4) {
            ans++;
            continue;
        }
        if (SZ(g[u])==3) {
            set<ll> st(all(g[u]));
            st.insert(u);
            ll cnt=0;
            for (auto to:g[u]) {
                for (auto toto:g[to]) {
                    if (!st.contains(toto)) {
                        ++cnt;
                        break;
                    }
                }
            }
            if (cnt>=2) {
                ++ans;
            }
        }else if (SZ(g[u])==2) {
            set<ll> st(all(g[u]));
            st.insert(u);
            ll cnt=0;
            for (auto to:g[u]) {
                ll not_in_st=0;
                for (auto toto:g[to]) {
                    if (!st.contains(toto)) {
                        ++not_in_st;
                    }
                    if (not_in_st>=2) {
                        ++cnt;
                        break;
                    }
                }

            }
            if (cnt>=2) {
                ++ans;
            }
        }
    }
    cout<<ans<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106262/submission/365635347

*/

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

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——M. Web Delivery（采用 naive if else方法，应用不同状态压缩方法，解决该问题）（枚举一个 S 的子集的子集方法）（利用乘积约束）

Posted on 2026-03-05 Edited on 2026-03-07

题目大意

题目描述
Gagamboy 需要购买 $r$ 种不同的化学物质，每种需要 1kg。电商平台上共有 $c$ 个卖家。
给定一个 $r \times c$ 的价格矩阵 $A$ ，其中 $a_{i,j}$ 表示从卖家 $j$ 处购买 1kg 化学物质 $i$ 的价格。
此外，对于每个卖家 $j$ ，只要从该卖家处购买了任何数量的化学物质（哪怕只有一种），都需要额外支付一笔固定的配送费 $d_j$ 。
请计算购买到所有 $r$ 种化学物质（每种至少 1kg）所需的最小总花费。本题包含多组独立测试数据。

输入格式
第一行包含一个整数 $T$ （ $1 \le T \le 10$ ），表示测试数据的组数。
对于每组测试数据：
第一行包含两个由空格分隔的整数 $r$ 和 $c$ （ $1 \le r, c$ ，且 $r \times c \le 250$ ）。
接下来 $r$ 行，每行包含 $c$ 个由空格分隔的整数，第 $i$ 行的第 $j$ 个数为 $a_{i,j}$ （ $1 \le a_{i,j} \le 10^{15}$ ）。
最后一行包含 $c$ 个由空格分隔的整数 $d_1, d_2, \dots, d_c$ （ $1 \le d_j \le 10^{15}$ ），表示每个卖家的配送费。

输出格式
对于每组测试数据，输出一行一个整数，表示完成购买所需的最小总花费。

样例输入

样例输出

1
2

11
11

样例解释
对于第一组样例：
一种最优的购买方案如下：

向卖家 2 购买化学物质 1 和 3。它们的价格分别为 $a_{1,2} = 3$ 和 $a_{3,2} = 1$ 。支付这笔订单所需的配送费为 $d_2 = 3$ 。
向卖家 4 购买化学物质 2。它的价格为 $a_{2,4} = 1$ 。支付这笔订单所需的配送费为 $d_4 = 3$ 。
总花费为： $((3 + 1) + 3) + (1 + 3) = 11$ 。

对于第二组样例：
最优方案能达到的最小花费同样为 11。

思路讲解

这道题目的做法，首先，需要想到：绷不住了，这道题目，观察到 chem * sell <= 250，那么，chem，sell 理论上来说，应该不会同时超过 16，因为 16*16=256，这样子，chem 小，就对 chem 进行状态压缩，sell 小，就对 sell 进行状态压缩。

确实是感觉到，如果不进行状态压缩，那么这道题目非常难做。

如果进行状态压缩的话，状态压缩 seller 非常好做。枚举的是给哪些 seller 付了这个运费。

给哪些 seller 付了这个运费，就只能从这些 seller 这里购买化学品。

ll ans=INF;
// 枚举的是给哪些 seller 付了这个运费
for (int s=1;s<(1<<M_j_sell);++s) {
    vector<ll> mn_price(N_i_chem+2,INF);
    ll offset_j=1;
    ll price=0;
    // 给哪些 seller 付了这个运费，就只能从这些 seller 这里购买化学品
    for (int j=0;j<M_j_sell;++j) {
        if (s>>j&1) {
            price+=D_j_sell[j+offset_j];
            for (int i=1;i<=N_i_chem;++i) {
                mn_price[i]=min(mn_price[i],A[i][offset_j+j]);
            }
        }
    }
    for (int i=1;i<=N_i_chem;++i) {
        price+=mn_price[i];
    }
    ans=min(ans,price);
    // dp[s]=price;
}
cout<<ans<<"\n";

我们来看，状态压缩 chem，我们怎么做？这个会难一点。

我们不难观察到，一个子集 S 的最优解，一定是这样的：把一部分子集交给一个买家，把另一部分子集交给一个买家，把又一部分子集交给又一买家……。

在状态压缩化学品的时候，我们需要学习一种写法，即枚举 mask 的子集。

for (int S = 0; S < (1 << r); S++) {
    for (int T = S; T > 0; T = (T - 1) & S) {
        // T 是 S 的非空子集
        dp[S] = min(dp[S], dp[S ^ T] + best[T]);
    }
}

枚举 mask 的所有子集，是 $O(3^n)$ 。

如果说枚举 seller，允许你去这个枚举子集，是不是会简单一点？

预处理：对每个非空子集 $T$ ，预先算好从所有卖家中买 $T$ 的最小花费：best（T）的意思就是在包括这个运费的情况下，该 chem 子集 T，从哪一个买家那里采购，所需花费最低？

\text{best}(T) = \min_{j=1}^{c} \left(d_j + \sum_{i \in T} a_{i,j}\right)

具体而言就是：

ll offset_i=1;
vector<ll> best((1<<N_i_chem)+2);
for (int s=1;s<(1<<N_i_chem);++s) {
    ll lans=INF;
    for (int j=1;j<=M_j_sell;++j) {
        ll price=D_j_sell[j];
        for (int i=0;i<N_i_chem;++i) {
            if (s>>i&1) {
                price+=A[offset_i+i][j];
            }
        }
        lans=min(lans,price);
    }
    best[s]=lans;
}

转移方程如下，容易写出：

dp[S] = \min_{\emptyset \neq T \subseteq S} \left(dp[S \setminus T] + \text{best}(T)\right)

你可能会有疑问，这个运费会不会重复算？答案是是的，但是我们肯定不会采用运费重复算的组合。

vector<ll> dp((1<<N_i_chem)+2);
// for (int j=1;j<=M_j_sell;++j) {
//     dp[0][j]=0;
// }
// for (int s=1;s<(1<<N_i_chem);++s) {}
ll offset_i=1;
vector<ll> best((1<<N_i_chem)+2);
for (int s=1;s<(1<<N_i_chem);++s) {
    ll lans=INF;
    for (int j=1;j<=M_j_sell;++j) {
        ll price=D_j_sell[j];
        for (int i=0;i<N_i_chem;++i) {
            if (s>>i&1) {
                price+=A[offset_i+i][j];
            }
        }
        lans=min(lans,price);
    }
    best[s]=lans;
}
for (int s=1;s<(1<<N_i_chem);++s) {
    ll lans=INF;
    for (int t=s;t>0;t=(t-1)&s) {
        lans=min(lans,dp[s^t]+best[t]);
    }
    dp[s]=lans;
}
cout<<dp[(1<<N_i_chem)-1]<<"\n";

AC代码

AC
https://codeforces.com/gym/106262/submission/365538444

源代码

/**
 * Problem: M. Web Delivery
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/M
 * Created: 2026-03-05 14:02:59
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#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 debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\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 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,testcase;

/*
 *
 */

void Solve() {
    ll N_i_chem,M_j_sell;
    cin >> N_i_chem >> M_j_sell;
    vector<vector<ll>> A(N_i_chem+2,vector<ll>(M_j_sell+2));
    for (int i=1;i<=N_i_chem;++i) {
        for (int j=1;j<=M_j_sell;++j) {
            cin>>A[i][j];
        }
    }
    vector<ll> D_j_sell(M_j_sell+2);
    for (int j=1;j<=M_j_sell;++j) {
        cin>>D_j_sell[j];
    }
    // 绷不住了，这道题目，观察到 chem * sell <= 250
    // 那么，chem，sell 理论上来说，应该不会同时超过 16，因为 16*16=256
    // 这样子，chem 小，就对 chem 进行状态压缩
    // sell 小，就对 sell 进行状态压缩

    if (N_i_chem<=M_j_sell) {
        vector<ll> dp((1<<N_i_chem)+2);
        // for (int j=1;j<=M_j_sell;++j) {
        //     dp[0][j]=0;
        // }
        // for (int s=1;s<(1<<N_i_chem);++s) {}
        ll offset_i=1;
        vector<ll> best((1<<N_i_chem)+2);
        for (int s=1;s<(1<<N_i_chem);++s) {
            ll lans=INF;
            for (int j=1;j<=M_j_sell;++j) {
                ll price=D_j_sell[j];
                for (int i=0;i<N_i_chem;++i) {
                    if (s>>i&1) {
                        price+=A[offset_i+i][j];
                    }
                }
                lans=min(lans,price);
            }
            best[s]=lans;
        }
        for (int s=1;s<(1<<N_i_chem);++s) {
            ll lans=INF;
            for (int t=s;t>0;t=(t-1)&s) {
                lans=min(lans,dp[s^t]+best[t]);
            }
            dp[s]=lans;
        }
        cout<<dp[(1<<N_i_chem)-1]<<"\n";
    }else {
        // vector<ll> dp((1<<M_j_sell)+2);
        ll ans=INF;
        for (int s=1;s<(1<<M_j_sell);++s) {
            vector<ll> mn_price(N_i_chem+2,INF);
            ll offset_j=1;
            ll price=0;
            for (int j=0;j<M_j_sell;++j) {
                if (s>>j&1) {
                    price+=D_j_sell[j+offset_j];
                    for (int i=1;i<=N_i_chem;++i) {
                        mn_price[i]=min(mn_price[i],A[i][offset_j+j]);
                    }
                }
            }
            for (int i=1;i<=N_i_chem;++i) {
                price+=mn_price[i];
            }
            ans=min(ans,price);
            // dp[s]=price;
        }
        cout<<ans<<"\n";
    }

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106262/submission/365538444

*/