yukicoder : No.2388 At Least K-Characters

コーナーケースで手間取った…。
https://yukicoder.me/problems/no/2388

問題

N文字の文字列Sと、正整数K,Mが与えられる。
M文字以下の文字列Tで、K種類以上の文字が使われており、Sより辞書順で小さい文字列は何通りか。

解法

あらかじめ以下を求めておこう。
dp(n,k) := n文字の文字列を作るとき、ちょうどk種類の文字を使う組み合わせ
dpS(n,k) := n文字以下のの文字列を作るとき、ちょうどk種類の文字を使う組み合わせ

Tが何文字目でSより小さいことが確定するかを総当たりしよう。
n文字目でT[n]＜S[n]となる場合、T[n]の文字を総当たりする。
するとそこまでに使われた文字数がわかる。

残りの文字数の中で何文字新しい文字が登場するかを総当たりすると、dpSを使いそれらを高速に数え上げられる。
なお、TがSのprefixになるケースを漏らさないよう注意。

int N,M,K;
string S;
const ll mo=998244353;

ll from[28];
ll to[28];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K>>S;
	
	
	ll ret=0;
	int mask=0;
	from[0]=1;
	FOR(i,M) {
		ZERO(to);
		
		for(j=1;j<=26;j++) {
			(to[j]+=from[j]*j)%=mo;
			(to[j+1]+=from[j]*(26-j))%=mo;
		}
		if(i<N) {
			x=__builtin_popcount(mask);
			FOR(j,S[i]-'a') {
				if(mask&(1<<j)) {
					(to[x]+=from[0])%=mo;
				}
				else {
					(to[x+1]+=from[0])%=mo;
				}
			}
			mask|=1<<(S[i]-'a');
			to[0]=from[0];
		}
		
		swap(from,to);
		if(i<N-1&&__builtin_popcount(mask)>=K) ret++;
		for(j=K;j<=26;j++) (ret+=from[j])%=mo;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

見事に漏らした…。