跳到主要内容

川剧复演

· 阅读需 4 分钟

题解​

题意​

有 m 种剧目，编号为 1, 2, …, m。需要安排 n 场演出，每场选择一个剧目，同一剧目可以重复选择。

一个安排是合法的，当且仅当：对于所有满足 1 ≤ l ≤ n-m+1 的整数 l，区间 l 到 l+m-1 这连续 m 场演出中，至少有一种剧目出现两次（即这 m 场不能两两不同）。

特别地，当 n < m 时，不存在长度为 m 的连续区间，因此所有安排均合法。

求合法安排的总数，对 998244353 取模。

数据范围

  • 1 ≤ T ≤ 5
  • 1 ≤ n ≤ 10⁹
  • 1 ≤ m ≤ 200

解法​

很容易想到要进行dpdp计数。

但是如何计数呢？

考虑设计一个很符合直觉的状态，令fi,jf_{i,j}表示安排前ii场演出，当前选择编号为jj的剧目的合法安排方式的数量。

但是这样我们如何设计转移呢？

我们发现这是困难的，因为我们仅仅知道末尾的剧目编号，我们并不知道上一个同样是这个编号的剧目在什么位置，也不知道这个后缀中是否存在重复的剧目。所以我们难以只通过知道末尾的剧目编号来构造合法的演出安排方案。

那我们需要一些什么信息才能构造演出安排方案呢？

我们还是从刚才设计的状态出发，我们的卡点在于，即使我们枚举某一个位置于当前位置剧目相同，我们也无法判断中间这一段后缀的状况，所以我们难以让构造出的序列合法，且不重不漏。

我们可以考虑怎样一个序列是不合法的，根据题意，是它存在一个长度≥m\geq m的连续不相同子段。那么当我们从左往右枚举当前剧目的时候，这个子段一定是一段后缀。

然后我们发现，我们真正关心的东西，不是后缀具体的情况，仅仅只是后缀中连续互不相同的剧目的长度。

判断合法性我们只需要保证这个长度在任意时刻都小于mm即可。

所以我们考虑将这个长度记入状态里面，令fi,jf_{i,j}表示前ii场演出，最后连续互不相同的剧目的后缀长度为jj的方案数。

显然j<mj<m

考虑进行转移，假设我们安排当前演出，有两种情况

  • 1.这场演出的剧目与后缀的都互不相同，那么这个后缀的长度会+1+1

  • 2.这场演出的剧目与后缀的某个剧目相同，那么这个后缀长度会减小

那么转移方程就很好写了

fi,j=fi−1,j−1⋅(m−(j−1))+∑k=jm−1fi−1,kf_{i,j}=f_{i-1,j-1}\cdot (m-(j-1))+\sum_{k=j}^{m-1}f_{i-1,k}

初始化f1,1=mf_{1,1}=m

然后ans=∑j=1m−1fn,jans=\sum_{j=1}^{m-1} f_{n,j}

但是我们发现n≤109n \leq 10^9于是我们把第一维干掉，然后矩阵快速幂计算即可。

代码​

code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=220+10;
const ll mod=998244353;
ll sum[N][N];
ll ans[N];
int n,m;
ll a[N];
inline void mul1()
{
    for(int i=1,j;i<m;i++)
    {
        for(j=1;j<m;j++)
        {
            a[i]=(a[i]+ans[j]*sum[j][i]%mod)%mod;
        }
    }
    for(int i=1;i<m;i++) ans[i]=a[i],a[i]=0;
    return ;
}
ll b[N][N];
inline void mul2()
{
    for(int i=1,j,k;i<m;i++)
    {
        for(j=1;j<m;j++)
        {
            for(k=1;k<m;k++)
            {
                b[i][j]=(b[i][j]+sum[i][k]*sum[k][j]%mod)%mod;
            }
        }
    }
    for(int i=1;i<m;i++) 
    {
        for(int j=1;j<m;j++) sum[i][j]=b[i][j],b[i][j]=0;
    }
}
inline void power(int k)
{
    while(k)
    {
        if(k&1) mul1();
        mul2();
        k>>=1;
    }
    return ;
}
inline void solve()
{
    cin>>n>>m;
    for(int i=1,j;i<m;i++)
    {
        for(j=1;j<m;j++)
        {
            if(i==(j-1)) sum[i][j]=m-i;
            else if(i>=j) sum[i][j]=1;
            else sum[i][j]=0; 
        }
        if(i==1) ans[i]=m;
        else ans[i]=0;
    }
    power(n-1);
    ll anss=0;
    for(int i=1;i<m;i++) anss=(anss+ans[i])%mod;
    cout<<anss<<'\n';
}
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}