Codeforces Educational Codeforces Round 56 (Rated for Div. 2) 1093F. Vasya and Array

有一个长度为n的的数列，ai​的值域只有k个元素。
一个数列有一些数字已经填上。现在要求数列连续的数字长度不能超过l,问所有不同的数列的个数有多少个。
1.考虑所有的数字都没填上。设dp[i][j][s]为第i个位置填入第j种颜色且已经有连续的s个数字的方案数。显然:
那么:
dp[i][j][s]=dp[i−1][j][s−1]−[s⩾l−1](p=1∑∞​(t=1∑k​dp[i−l+1][t][p]−dp[i−l+1][j][p])),2⩽s⩽l−1,dp[i][j][s]=1⩽t⩽k,j̸​=t∑​p=1∑∞​dp[i−1][t][p],s=1dp[i][j][s]=0,s⩾l.
求和得:
p=1∑s​dp[i][j][p]=p=1∑∞​t=1∑k​dp[i−1][j][p]−[s⩾l−1](p=1∑∞​t=1∑k​dp[i−l+1][t][p]−p=1∑∞​dp[i−l+1][j][p])
因为具有规整性，并且考虑到dp[i][j][s]=dp[i−1][j][s−1]，
所以令ava[i][j]=p=1∑∞​dp[i][j][p],sum[i]=i=1∑k​ava[i][j],得:
ava[i][j]=sum[i−1]−[maxavalenj​⩾l−1](sum[i−l+1]−ava[i−l+1]),i=1,2,…,n
其中maxavalenj​是指当前可能达到的最大连续后缀长度。
2.考虑有的数字已经填上。显然这时候，如果j=a[i]，则可以继续转移，但是只有一种可能。如果j̸​=a[i]，也可以继续转移，但是maxavalenj​被隔断，所以重新计算。

#include <cstdio>
#include <iostream>
const int N=100005,K=105;
const long long mod=998244353LL;
int a[N];
long long dp[N],ava[N][K],len[K],bad[K];
int main(){
    int n,k,l;
    scanf(\"%d%d%d\",&n,&k,&l);l--;
    if(!l){
        puts(\"0\");
        return 0;
    }
    for(int i=1;i<=n;i++){
        scanf(\"%d\",&a[i]);
    }
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(a[i]==j||a[i]==-1){
                ava[i][j]=(dp[i-1]+mod-bad[j])%mod;
                len[j]++;
                if(len[j]>=l){
                    bad[j]=(dp[i-l]+mod-ava[i-l][j])%mod;
                }
                dp[i]+=ava[i][j];
                if(dp[i]>=mod)dp

					

						
继续阅读与本文标签相同的文章
						

														无标签