Codeforces1073 E 数位dp

Posted on | In , ,

给一个区间 $[l,r]$ ，问满足 $l\leq x\leq r$ 并且 $x$ 每一位数字种类不超过 $k$ 的方案数 $\rm mod$ $998244353$。
$(l,r\leq 10^{18}，k\leq 10)$

题目链接

题解

  • 自己想到了考虑每一位算贡献，但要控制每个数$l\leq x\leq r$，没想到怎么处理。
  • 实际上还是自己不想动脑子
  • 将 $k$ 的限制状态压缩为二进制即可。
  • 考虑从高位向低位枚举数字，需要考虑两个方面。1.数字大小限制 。2.前导零限制。
  • 状压搜索dp即可
  • 转移是低位向高位转移，贡献是：低位的方案数 $\times$ 当前位为贡献 $+$ 低位的贡献和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+110;
const long long mod = 998244353;
typedef long long ll;
typedef pair<ll,ll> pll;

ll l, r, k;
ll fac[30];
int num[5024], a[30];
pll dp[30][2048];
bool vis[30][2028];

pll dfs(int pos, int state, int limt, int zero)
{
    if(pos==-1) return (num[state]<=k) ? make_pair(1,0):make_pair(0,0);
    if(vis[pos][state] && (!limt) && (!zero)) return dp[pos][state];
    int dig= limt ? a[pos] : 9;
    pll res={0ll, 0ll};
    for(int i=0;i<=dig;i++)
    {
        int nstate=state;
        if(zero && i==0) nstate=0;
        else nstate=state|(1<<i);
        pll ans=dfs(pos-1, nstate, limt&&(i==a[pos]), zero && i==0);
        ll pre=(1ll * i * fac[pos])%mod;
        res.first = (res.first+ans.first)%mod;
        res.second = (res.second + (pre* ans.first %mod + ans.second)%mod)%mod;
    }
    if(!limt && !zero){
         dp[pos][state]=res;
         vis[pos][state]=1;
    }
    return res;


}

ll solve(ll x)
{
    int cnt=0;
    while(x){
        a[cnt++]=x%10;
        x/=10;
    }
    cnt-=1;
    return dfs(cnt, 0, 1, 1).second;
}

int main()
{
    fac[0]=1;
    for(int i=1;i<=20;i++)
       fac[i]=(10*fac[i-1])%mod;
    for(int i=0;i<2000;i++)
        num[i]=__builtin_popcount(i);
    scanf("%lld%lld%lld", &l, &r, &k);

    ll ans=solve(r)-solve(l-1)+mod;
    printf("%lld\n", ans%mod);
    return 0;
}