spoj Interesting Game (数位dp+nim博弈)

题意：

有一个long long 大小的数，alice和bob轮流将其中每一位的数减小任意数量到0为止，将所有位置为0的人赢，每次alice都是先手，问[l,r]区间内有多少个数是alice必赢，多少个数是bob必赢。

解题思路：

队友cyk推荐的题目，确实蛮有意思的233.

减数字游戏其实就是取石子游戏，然后问你l，r区间的话用一下数位dp去求有多少个数每位数^为0就行了。

原来数位dp和博弈还能放一起玩？呵呵

代码：

#include <bits/stdc++.h>
using namespace std;
long long  dp[22][50];
int num[22];
int cal(long long x)
{
    int i=0;
    while(x>0)
    {
        num[i++]=x%10;
        x/=10;
    }
    return i;
}
long long dfs(int pos, bool ismax, int x)
{
    if(pos<0)
    {
        if(x>0)return 1;
        else return 0;
    }
    if(!ismax && dp[pos][x]>-1)return dp[pos][x];
    int bound=ismax?num[pos]:9;
    long long res=0;
    for(int i=0; i<=bound; i++)
    {
        res+=dfs(pos-1, ismax && i==bound, x^i);
    }
    if(!ismax)dp[pos][x]=res;
    return res;
}
int main()
{
    int t, len;
    cin>>t;
    long long a, b, l, r;
    memset(dp, -1, sizeof dp);
    while(t--)
    {
        scanf("%lld%lld", &l, &r);
        len=cal(l-1);
        a=dfs(len-1, 1, 0);
        len=cal(r);
        b=dfs(len-1, 1, 0);
        printf("%lld %lld\n", b-a, r-l+1LL-b+a);
    }
}