AtCoder ARC #186 (AtCoder Japan Open -予選-) : E - Missing Subsequence

実装は軽め。
https://atcoder.jp/contests/arc186/tasks/arc186_e

問題

1～Kの整数からなるM要素の整数列Xが与えられる。
1～Kの整数からなるN要素の整数列Aのうち、M要素の部分列を取るとX以外のすべてのパターンが取れるようなAは何通りか。

解法

f(m,n) := n要素の整数列のうち、(M-m)要素の整数列を取ると(X[m],...,X[M-1])以外の全パターンが取れるようなものの組み合わせ
g(n):= n要素の整数列のうち、1回以上登場する整数がちょうどK-1種である組み合わせ
とする。

Aを後ろから定めて行き、f(m,n)から、f(m-1,n+x)を構築することを考える。
まず、f(M-1,n) = g(n)となる。

• X[m-1]=X[m]の場合
  • f(m-1,n)の手前にX[m-1]を置き、その前にX[m-1]以外のK-1通りの整数が1回以上現れればよい
  • よって、f(m,n+x) += f(m-1,n)*g(x)
• X[m-1]!=X[m]の場合
  • f(m-1,n)の手前にB,X[m],C,X[m-1]の順で要素を置く。Bは、X[m]以外のK-1通りの整数が1回以上現れればよい。
  • Cは、X[ｍ],X[m-1]以外のK-2通りの値を何個でも置くことができる。
  • |B|+|C|=x-2となるようなB,Cの組み合わせh(x)は事前に計算しておくと、f(m,n+x) += f(m-1,n)*h(x)として計算できる。

int N,M,K;
ll dp[404][404];  // dp[n][k] := n要素中にユニークなのがk個
ll dp2[404][404];
int A[404];

const ll mo=998244353;
const int NUM_=2000003;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll single[404];
ll single2[404];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	dp[0][0]=1;
	FOR(x,402) {
		FOR(y,402) {
			(dp[x+1][y]+=dp[x][y]*y)%=mo; //既出
			(dp[x+1][y+1]+=dp[x][y])%=mo; //追加
		}
	}
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>A[i];
	}
	//K-1要素の並び
	FOR(i,N+1) {
		single[i]=dp[i][K-1]*fact[K-1]%mo;
		dp2[M-1][i]=single[i];
	}
	FOR(x,N) FOR(y,N) if(x+y<=N) (single2[x+y]+=single[x]*modpow(K-2,y))%=mo;
	
	for(i=M-2;i>=0;i--) {
		FOR(y,N) if(dp2[i+1][y]) {
			if(A[i]==A[i+1]) {
				for(x=K-1;x+1+y<=N;x++) (dp2[i][x+1+y]+=dp2[i+1][y]*single[x])%=mo;
			}
			else {
				for(x=K-1;x+2+y<=N;x++) (dp2[i][x+2+y]+=dp2[i+1][y]*single2[x])%=mo;
			}
		}
	}
	cout<<dp2[0][N]<<endl;
	
	
}

まとめ

状態遷移の数が意外に少ない。