yukicoder : No.2772 Appearing Even Times

これは典型か。
https://yukicoder.me/problems/no/2772

問題

正整数Nが与えられる。
N以下の正整数のうち、同じ数字が偶数回ずつ現れるものは何通りか。

解法

桁DPで上の桁から0～9を決めていく。
その際の状態として

• 0～9の登場回数の偶奇
• N未満であることが確定したかどうか
• 上桁に非0の数字があるか(0を置くことができるか)

を持てばよい。

string S;
ll from[1<<10][2][2];
ll to[1<<10][2][2];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	from[0][1][0]=1;
	FORR(c,S) {
		c-='0';
		ZERO(to);
		int mask,lead,le,d;
		FOR(mask,1<<10) FOR(lead,2) FOR(le,2) {
			FOR(d,10) {
				if(le==0&&d>c) continue;
				
				if(lead==1&&d==0) {
					(to[0][lead][le|(d<c)]+=from[mask][lead][le])%=mo;
				}
				else {
					(to[mask^(1<<d)][0][le|(d<c)]+=from[mask][lead][le])%=mo;
				}
				
			}
		}
		
		swap(from,to);
	}
	ll ret=from[0][0][0]+from[0][0][1];
	cout<<ret%mo<<endl;
}

まとめ

桁DPの良い練習。