SP20848 IGAME - Interesting Game 题解

分析

数位 DP 一眼题。

对于一个 \(k\) 位的数 \(s\)，我们不妨将其看做由数字 \(s_1,s_2,s_3,\dots,s_k\) 这 \(k\) 个数字拼接起来的。而题意是每个人可以将 \(s_1,s_2,s_3,\dots,s_k\) 中的任意一个减去任意数字，保证不减去 \(0\) 且结果 \(\ge 0\)。显然，在我们将这 \(k\) 个数看成 \(k\) 堆石头之后，这就是一个取石子游戏。根据博弈结论，若 \(s_1\oplus s_2 \oplus s_3 \oplus \dots \oplus s_k=0\)，则后手存在必胜策略，反之先手存在必胜策略。

对于该题，我们可以用数位 DP 求出区间 \(l,r\) 中各位异或之后结果为 \(0\) 的个数，也就是小 B 必赢的数的个数。而在所有数中，不是小 B 必赢就是小 A 必赢，所以该区间剩下的数的个数就是小 A 必赢的数量。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,l,r;
int a[20],len;
int f[20][50];
int dfs(int now,int if_le,int sum){
	if(!now){
		return !sum;
	}
	else if(f[now][sum]!=-1&&!if_le){
		return f[now][sum];
	}
	else{
		int ans=0,up=if_le?a[now]:9;
		for(int i=0;i<=up;i++){
			ans+=dfs(now-1,if_le&&i==up,sum^i);
		}
		return if_le?ans:f[now][sum]=ans;
	}
}
int check(int x){
	len=0,memset(f,-1,sizeof(f));
	while(x){
		a[++len]=x%10,x/=10;
	}
	return dfs(len,1,0);
}
signed main(){
	cin>>t;
	while(t--){
		cin>>l>>r;
		int ans=check(r)-check(l-1);
		cout<<(r-l+1-ans)<<" "<<ans<<"\n";
	}
	return 0;
}