题解：P16125 [USTCPC 2026] Melody

· · 题解

题意简述

长度为 n 的序列中，每个元素取 1\sim k，其中 m 个位置已经确定。相邻元素之差模 k 称为进行，大小为 i 的进行出现 c_i 次时，贡献为 h_i^{c_i}。

求所有合法序列的 \sum_{i=0}^{k-1}h_i^{c_i} 之和，对 20120923 取模。约定 0^0=1。

解题思路

交换两层求和的顺序。枚举一种进行 i，先求所有合法序列的 h_i^{c_i} 之和，最后再累加各个 i 的结果。

固定 i 后，将每条相邻转移的权值设为：进行等于 i 时为 h_i，其余情况为 1。一个完整序列的转移权值之积恰好为 h_i^{c_i}，问题变成求所有合法序列的权值之和。

记 c=h_i-1。这里的 c 是当前枚举的和谐度减一，与题意中的出现次数 c_i 无关。每条转移的权值都可以写成「基础权值 1，若进行等于 i，再加上 c」。

将固定位置按下标排序，记为 (x_1,y_1),\dots,(x_m,y_m)。固定音符切断了相邻区间之间的依赖：每个区间的内部音符可以独立选择，所有区间的权值之和相乘，即为完整序列的权值之和。

先考虑两个固定音符之间的一段。设相邻固定位置的距离为 d，右端音符与左端音符之差模 k 为 \Delta。这一段包含 d 次转移。

展开这 d 条转移权值的乘积，相当于选出若干条转移使用附加项 c，其余转移使用基础项 1。选中一条转移，就强制它的进行为 i；未选中的转移可以使用任意进行，包括 i，因此展开没有漏掉原来的权值。

若选中 t<d 条转移，则剩余 d-t 条转移的进行不受单独限制，仅要求所有进行之和模 k 等于 \Delta。任意选择其中 d-t-1 条后，最后一条被端点差唯一确定，故有 k^{d-t-1} 种方案。选中的位置有 \binom{d}{t} 种，每种贡献 c^t。

若全部 d 条都被选中，则所有进行都为 i。这一项仅在 di\bmod k=\Delta 时存在，贡献为 c^d。

记条件成立时 e=1，否则 e=0。这一段的总贡献为：

\sum_{t=0}^{d-1}\binom{d}{t}c^tk^{d-t-1}+ec^d=\frac{(k+c)^d-c^d}{k}+ec^d

这正是代码中的 val。其中 u 为 c^d，v 为 (k+c)^d，判断 d*i%k 是否等于端点差后，再决定是否加上 u。必须保留这项判断：全部转移被限制时，已经没有自由转移可以补足端点差。

再考虑首个固定位置之前和末个固定位置之后的两段。已知其中一端，每向外增加一个音符，都有一种选择的转移权值为 h_i，其余 k-1 种权值为 1，权值之和为 k+c。两端一共有 x_1-1+n-x_m 次转移，因此共同贡献为 (k+c)^{x_1-1+n-x_m}。

若 m=0，没有固定位置。第一个音符有 k 种选择，其余 n-1 次转移各贡献一个 k+c，故当前进行的答案为 k(k+c)^{n-1}。若 m=1，仅存在两端的自由部分，中间区间的乘积为空，按 1 处理。

模数 20120923 是质数，且 1\le k\le 10^6<20120923，可以预处理 k 的逆元，将公式中的除法改为乘法。h_i=0 时，将 c=-1 归一化为模数减一；快速幂的零次幂返回 1，也覆盖题目规定的 0^0=1。当 n=1 时，没有转移，上述公式同样成立。

排序需要 O(m\log m)，随后每种进行处理至多 m-1 个固定区间，快速幂需要 O(\log n)。每组数据的总时间复杂度为 O(m\log m+k(m+1)\log n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<int,int>;
const int N=1000005;
const int mod=20120923;
int h[N];
pii a[N];
ll Pow(ll x,ll y)
{
    x%=mod;
    ll res=1;
    while(y)
    {
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n,m,k;
        cin>>n>>m>>k;
        for(int i=0;i<k;i++)cin>>h[i];
        for(int i=1;i<=m;i++)cin>>a[i].first>>a[i].second;
        sort(a+1,a+m+1);
        ll inv=Pow(k,mod-2),ans=0;
        for(int i=0;i<k;i++)
        {
            ll c=(h[i]+mod-1)%mod;
            ll res=Pow(c+k,m?n-1-a[m].first+a[1].first:n-1);
            if(!m)res=res*k%mod;
            for(int j=2;j<=m;j++)
            {
                int d=a[j].first-a[j-1].first;
                ll u=Pow(c,d),v=Pow(c+k,d);
                ll val=(v-u+mod)*inv%mod;
                if(1LL*d*i%k==(a[j].second-a[j-1].second+k)%k)val=(val+u)%mod;
                res=res*val%mod;
            }
            ans=(ans+res)%mod;
        }
        cout<<ans<<'\n';
    }
    return 0;
}