SP10606题解

Ginger_he · 2022-01-26 11:02:43 · 题解

本文同步更新于博客园

题目描述

一个数被称为是平衡的数，当且仅当对于所有出现过的数位，每个偶数出现奇数次，每个奇数出现偶数次。给定 A,B 请统计出 [A,B] 内所有平衡数的个数。

题解

平衡数与数的大小无关，并且我们要统计一个区间内符合条件的数的个数，不难想到用数位 dp。又因为我们要统计数字出现的次数，所以需要状态压缩。
我们用 x 来表示数字出现的次数，0 表示出现偶数次，1 表示出现奇数次。现在问题来了，0 也可以表示该数字没出现过，因此需要再用一个变量 y 表示有没有出现过，0 表示没出现过，1 表示出现过。根据定义不难知道，转移的时候，x 用的是异或，y 用的是或。
接下来，我们传五个参数 k,x,y,p,q 进入 dfs，分别表示枚举到第 k 位，当前每个数字出现次数的状态，当前每个数字是否出现的状态，当前位是否为前导 0，以及这一位填的数有没有限制，用 f 数组记忆化即可。
注意到本题的内存限制是 1.46\mathrm{GB}，所以我们可以直接开 20\times1024\times1024 的数组，没有必要用其他题解说的 map，当然想用也行。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t,len,a[20];
ll l,r,f[20][1024][1024];
ll check(int x,int y)
{
    for(int i=0;i<=9;i++)
    {
        if(y&(1<<i))
        {
            if((i&1)^(x&(1<<i))==0)
                return 0; 
        }
    }
    return 1;
}
ll dfs(int k,int x,int y,int p,int q)
{
    if(!k)
        return check(x,y);
    if(!p&&!q&&f[k][x][y]!=-1)
        return f[k][x][y];
    int z=q?a[k]:9,w;
    ll res=0;
    for(int i=0;i<=z;i++)
    {
        w=p&&!i;
        res+=dfs(k-1,w?0:x^(1<<i),w?0:y|(1<<i),w,q&&(i==z));
    }
    if(!p&&!q)
        f[k][x][y]=res;
    return res;
}
ll divide(ll x)
{
    len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1,1);
}
int main()
{
    memset(f,-1,sizeof(f));
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",divide(r)-divide(l-1));
    }
    return 0;
}