[Codeforces] E. Salazar Slytherin's Locket

題目連結:http://codeforces.com/contest/855/problem/E

---

早上才學完數位統計DP晚上就寫不出來，我還真垃圾...
這題我的狀態是定成$dp[i][j][k]$代表在$i$進位下，算到第$j$位，而且有$k$個奇數次時的方法數，這狀態的轉移很簡單，就是枚舉多一位奇數或少一位奇數($dp[i][j][k]=dp[i][j-1][k-1] \cdot k + dp[i][j-1][k+1] \cdot (i-k)$)。那這樣的話，對於每一個範圍，我們就只要枚舉他在哪一位開始可以任意選之類的就可以回答了。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 65;

int dig[N];

lld dp[11][N][11];
bool dped[11][N][11];
void init();
lld go(int,int,bool,int,bool);
lld calc(int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	init();
	int q; cin>>q;
	while(q--){
		int b; cin>>b;
		long long l, r;cin>>l>>r;
		l--;
		int cnt;
		for(cnt=0;l>0;cnt++){
			dig[cnt]=l%b;
			l/=b;
		}
		dig[cnt]=0;
		lld L = go(b, cnt, 0, 0, 1);
		for(cnt=0;r>0;cnt++){
			dig[cnt]=r%b;
			r/=b;
		}
		dig[cnt]=0;
		lld R = go(b, cnt, 0, 0, 1);
		cout<<R-L<<'\n';
	}
	return 0;
}

void init(){
	for(int base=2;base<=10;base++){
		for(int pos=0;pos<N;pos++){
			for(int cnt=0;cnt<=10;cnt++){
				calc(base, pos, cnt);
			}
		}
	}
}

lld calc(int base, int pos, int cnt){
	if(cnt > base or cnt < 0) return 0;
	if(pos < 0) return cnt==0;
	if(dped[base][pos][cnt]) return dp[base][pos][cnt];
	dped[base][pos][cnt] = 1;
	dp[base][pos][cnt] = calc(base, pos-1, cnt+1)*(base-cnt) + calc(base, pos-1, cnt-1)*cnt;
	return dp[base][pos][cnt];
}

lld go(int base, int pos, bool any, int wei, bool pre){
	int cnt = __builtin_popcount(wei);
	if(cnt > pos+1) return 0;
	if(pos < 0) return wei==0;
	if(any and !pre) return dp[base][pos][cnt];
	lld ret = 0;
	for(int i=0;i<base;i++){
		if(!any and i>dig[pos]) break;
		if(pre and i==0) ret += go(base, pos-1, any or i<dig[pos], wei, 1);
		else ret += go(base, pos-1, any or i<dig[pos], wei^(1<<i), 0);
	}
	return ret;
}