CF855E题解

Ginger_he · 2022-01-25 21:05:37 · 题解

本文同步更新于博客园

题目描述

求 l\le x\le r 中所有满足 x_{(b)} 中各个数码均出现偶数次的 x 的个数。

题解

由于最多只有 10 个不同的数字，因此我们可以对每个数字出现的个数进行二进制状态压缩，0 表示出现偶数次，1 表示出现奇数次。下面说一下状态如何转移，因为我们每次要将某一位上的 0 变为 1，1 变为 0，因此我们将 sta 与 2^i 按位异或即可（i 表示填入的数）。
接下来就是的数位 dp 了，我们传四个参数 k,sta,p,q 进入 dfs，分别表示枚举到第 k 位，当前每个数字出现次数的状态，是否为前导 0，以及这一位填的数有没有限制，用 f 数组记忆化即可。

注意

• 我们不用计算 sta 中 1 的个数，因为当且仅当 sta=0 时所有数码出现的次数均为偶数
• 只有将 f 数组添加一维表示当前的数是 b 进制才能只初始化一遍，我第一次就是因为这个 WA 了。

Code

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