TopCoder SRM 771 : Div1 Easy Div2 Hard AllEven

Mediumは割とサクサク解けたかと思ったら落としてしまい1完。
https://community.topcoder.com/stat?c=problem_statement&pm=15832

問題

正整数の区間[L,R]が与えられる。
この区間内で、(leading zeroを除き)各桁に現れる数字が偶数回ずつであるのは何通りか。

解法

f(x) := x以下の整数で各桁に現れる数字が偶数回のものの数
が求められれば、f(R)-f(L-1)で解が得られる。

f(x)は典型的な桁DPで求められる。上の桁から以下の情報を持ってメモ化再帰していこう。

• 現在見ている桁数
• 上の桁に1以上の値があるか(0を置いてもleading zeroにならないか)
• 上の桁の時点でx未満が確定しているか
• 0～9の各数字の登場回数の偶奇を10bitのbitmaskで持つ

ll p10[20];
ll memo[2][2][20][1<<10];

class AllEven {
	public:
	ll hoge(ll v,int lead,int le,int d,int mask) {
		if(d==-1) return lead==0 && mask==0;
		if(memo[lead][le][d][mask]>=0) return memo[lead][le][d][mask];
		
		ll ret=0;
		int i;
		if(le==1) {
			FOR(i,10) {
				if(i==0 && lead) ret+=hoge(v,lead,le,d-1,mask);
				else ret+=hoge(v,0,le,d-1,mask^(1<<i));
			}
		}
		else {
			ll a=v/p10[d]%10;
			if(lead==0) {
				FOR(i,a) ret+=hoge(v,lead,1,d-1,mask^(1<<i));
				ret+=hoge(v,lead,0,d-1,mask^(1<<a));
			}
			else {
				FOR(i,a) {
					if(i==0 && lead==1) ret+=hoge(v,1,1,d-1,mask);
					else ret+=hoge(v,0,1,d-1,mask^(1<<i));
				}
				if(a==0 && lead==1) ret+=hoge(v,1,0,d-1,mask);
				else ret+=hoge(v,0,0,d-1,mask^(1<<a));
				
			}
		}
		
		return memo[lead][le][d][mask]=ret;
	}
	
	long long countInRange(long long lo, long long hi) {
		int i;
		p10[0]=1;
		FOR(i,18) p10[i+1]=p10[i]*10;
		MINUS(memo);
		ll ret=0;
		if(hi>=10) ret+=hoge(hi,1,0,17,0);
		MINUS(memo);
		if(lo>=10) ret-=hoge(lo-1,1,0,17,0);
		return ret;
		
		
	}
}

まとめ

なんかCodeforcesで出そうな問題。