Codeforces #877 : Div2 E. Count Supersequences

悪くはなかった回。
https://codeforces.com/contest/1838/problem/E

問題

整数列Aが与えられる。[1,k]の範囲の値を持つM要素の整数列Bを考える。
Bのうち、部分列としてAを含むものは何通りか。

解法

Aを含まないものを数えることを考えよう。
仮にAのうち先頭n要素まで含んでいたとすると、そのn箇所の位置と残りの要素の決め方を考えるとC(M,n)*(K-1)^(M-n)通りのパターンがある。
これをnごとに足し合わせればよい。

int T;
int N,M,K;
int A[202020];
const ll mo=1000000007;

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;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>K;
		FOR(i,N) cin>>A[i];
		ll ret=modpow(K,M);
		ll p=1;
		for(i=0;i<N;i++) {
			(ret-=p*modpow(K-1,M-i))%=mo;
			p=p*(M-i)%mo*modpow(i+1)%mo;
		}
		cout<<(ret%mo+mo)%mo<<endl;
	}
}

まとめ

こちらは割とすんなり。