AtCoder ABC #194 : F - Digits Paradise in Hexadecimal

まぁまぁ手間取ったと思ったけど、最上位陣が速かっただけで自分が遅すぎたわけでもないらしい。
https://atcoder.jp/contests/abc194/tasks/abc194_f

問題

16進数で200000桁以下の正整数Nが与えられる。
N以下の正整数のうち、16進数表記で(leading zeroを除き)各桁に出てくる数字の種類がK種類であるのは何通りか。

解法

典型の桁DP。
f(n,k) := 上からn桁目までを決めたとき、すでにN未満であることが確定していて、現在k種類の数字を使っている組み合わせ
とする。解はf(N,K)に、NがちょうどK種類の数字で構成されるなら1足す。

f(n,k)がわかっているとき、f(n+1,*)は以下のように遷移する。

• n>1の時、n桁目までは0でn+1桁目に1以上の数字が来るケースf(n+1,1)=15通り。
• n+1桁目に、既出のk通りの数字を再び使うケースf(n+1,k) += f(n,k)*k
• n+1桁目に、未出の(16-k)通りの数字を使うケースf(n+1,k+1) += f(n,k)*(16-k)
• n桁目まではNと同じだが、n+1桁目ではNより小さい数字を使うケース (ただし先頭桁のみ0は不可)

string N;
int K;

ll pat[202020][18];
const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>K;
	int mask=0;
	
	FOR(i,N.size()) {
		char c=N[i];
		if(c>='A'&&c<='F') y=10+c-'A';
		else y=(c-'0');
		
		//first
		if(i) pat[i+1][1]+=15;
		//less
		FOR(j,y) {
			if(i==0&&j==0) continue;
			x=__builtin_popcount(mask|(1<<j));
			pat[i+1][x]++;
		}
		//any
		FOR(x,17) {
			(pat[i+1][x]+=pat[i][x]*x)%=mo;
			(pat[i+1][x+1]+=pat[i][x]*(16-x))%=mo;
		}
		
		mask|=(1<<y);
	}
	
	ll ret=pat[N.size()][K];
	if(__builtin_popcount(mask)==K) ret++;
	
	cout<<ret%mo<<endl;
}

まとめ

Aでミスしてしまった。