CF1073E Segment Sum 解题报告

时间：2023-03-10 06:30:26
CF1073E Segment Sum 解题报告

CF1073E Segment Sum

题意翻译

给定\(K,L,R\)，求\(L~R\)之间最多不包含超过\(K\)个数码的数的和。

\(K\le 10,L,R\le 10^{18}\)

数位dp

\(dp_{i,s}\)前\(i\)位出现集合\(s\)的贡献和和出现次数

然后记忆化的时候转移一下就行了

然而写的时候还是怪麻烦的

Code:

#include <cstdio>

#include <cstring>

#define ll long long

const int mod=998244353;

inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

#define mul(a,b) (1ll*(a)*(b)%mod)

int po[20],bit[20],len,k;

struct node

{

    int val,cnt;

    node(){}

    node(int v,int c){val=v,cnt=c;}

    node friend operator +(node a,node b){return node(add(a.val,b.val),add(a.cnt,b.cnt));}

}dp[20][1<<10];

node dfs(int pos,int sta,int lead,int lim)//前导0和最高位限制

{

    int cnt=0;

    for(int i=0;i<10;i++) cnt+=sta>>i&1;

    if(cnt>pos) return node(0,0);

    if(!pos) return node(0,1);

    if(!lim&&!lead&&~dp[pos][sta].val) return dp[pos][sta];

    node ret=node(0,0),bee;

    if(lead) ret=ret+dfs(pos-1,sta,lead,lim&&!bit[pos]);

    else if(sta&1) ret=ret+dfs(pos-1,sta,lead,lim&&!bit[pos])+dfs(pos-1,sta^1,lead,lim&&!bit[pos]);

    for(int i=1,up=lim?bit[pos]:9;i<=up;i++)

        if(sta>>i&1)

        {

            bee=dfs(pos-1,sta,0,lim&&i==up)+dfs(pos-1,sta^(1<<i),0,lim&&i==up);

            ret=ret+bee;

            ret.val=add(ret.val,mul(bee.cnt,mul(i,po[pos-1])));

        }

    return !lim&&!lead?dp[pos][sta]=ret:ret;

}

int cal(ll x)

{

    len=0;while(x) bit[++len]=x%10,x/=10;

    memset(dp,-1,sizeof dp);int ans=0;

    for(int s=0;s<1<<10;s++)

    {

        int cnt=0;

        for(int i=0;i<10;i++) cnt+=s>>i&1;

        if(cnt<=k) ans=add(ans,dfs(len,s,1,1).val);

    }

    return ans;

}

int main()

{

    ll l,r;

    scanf("%lld%lld%d",&l,&r,&k);

    po[0]=1;for(int i=1;i<=18;i++) po[i]=mul(po[i-1],10);

    printf("%d\n",add(cal(r),mod-cal(l-1)));

    return 0;

}

2019.2.9

相关文章