Codeforces ECR #053 : E. Segment Sum

今回難しくない？
http://codeforces.com/contest/1073/problem/E

問題

整数区間[L,R]と整数Kが与えられる。
区間内の整数のうち、各桁に登場する数字の種類がK種類以下の物の総和を求めよ。

解法

定番として、R以下に対し条件を満たす数値の総和を求め、そこから(L-1)以下に対し条件を満たす数値の総和を引けばよい。
よって、あるN以下に対し条件を満たす数値の総和を求めることを考える。

f(d,f,mask) := 上からd桁目までの数を確定させたとき、fがN以下の値となる桁の有無を示す真偽値、maskに示す数字が登場するような数値であるような整数の候補数
g(d,f,mask) := 上からd桁目までの数を確定させたとき、fがN以下の値となる桁の有無を示す真偽値、maskに示す数字が登場するような数値であるような整数の総和

d+1桁目として、0～9が登場した場合を考え順次値を足しこんでいこう。
最後にmaskの立っているbitがK個以下の物の総和を取ろう。

ll L,R,K;
ll p10[20];
ll mo=998244353;

ll S[20][2][1<<10];
ll num[20][2][1<<10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>R>>K;
	
	p10[0]=1;
	FOR(i,19) p10[i+1]=p10[i]*10;
	ll ret=0;
	
	FOR(i,2) {
		ll N=(i==0)?R:L-1;
		ZERO(S);
		ZERO(num);
		num[19][1][0]=1;
		
		for(j=18;j>=0;j--) {
			for(int mask=0;mask<1<<10;mask++) {
				FOR(x,2) {
					FOR(y,10) {
						if(x&&y>N/p10[j]%10) continue;
						
						int nmask=mask | (1<<y);
						if(mask==0 && y==0) nmask=0;
						int ty=x;
						if(x==1 && y<N/p10[j]%10) ty=0;
						
						(num[j][ty][nmask] += num[j+1][x][mask])%=mo;
						(S[j][ty][nmask] += S[j+1][x][mask]+num[j+1][x][mask]*y%mo*p10[j])%=mo;
						
					}
				}
			}
		}
		for(int mask=0;mask<1<<10;mask++) if(__builtin_popcount(mask)<=K) {
			if(i==0) ret+=S[0][0][mask]+S[0][1][mask];
			else ret-=S[0][0][mask]+S[0][1][mask];
		}
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
	
}

まとめ

もう面倒な桁DPは飽きてきた…。