欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

CF1073E Segment Sum

程序员文章站 2022-09-17 08:35:03
一、题目点此看题二、解法很显然的数位dpdpdp,首先可以把答案转化成差分的形式(两个前缀相减)。设dp[i][s]dp[i][s]dp[i][s]为考虑到第iii位,已选的数状态为sss的方案数和方案的和(所以实现中用了pairpairpair),这里注意一下数位dpdpdp的写法,我们是需要考虑是否达到上界和前导000的,这时我们特判一下......

一、题目

点此看题

二、解法

很显然的数位dpdp,首先可以把答案转化成差分的形式(两个前缀相减)。设dp[i][s]dp[i][s]为考虑到第ii位,已选的数状态为ss的方案数和方案的和(所以实现中用了pairpair),这里注意一下数位dpdp的写法,我们是需要考虑是否达到上界和前导00的,在需要考虑这两种情况的时候就暴力算,不记忆化了。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define int long long
#define pii pair<int,int>
const int p = 998244353;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[20],l,r,k,pw[20];pii dp[20][1024];
pii dfs(int x,int s,int up,int zero)
{
    if(!x) return make_pair(__builtin_popcount(s)<=k,0);
    if(!up && !zero && ~dp[x][s].first) return dp[x][s];
    pii ans=pii(0,0);
    for(int i=0;i<=9;i++)
    {
        if(up && i>a[x]) break;
        int to=(zero && i==0)?s:(s|(1<<i));
        pii t=dfs(x-1,to,up&&i==a[x],zero&&i==0);
        ans=make_pair((ans.first+t.first)%p,(ans.second+t.second+i*pw[x-1]%p*t.first)%p);
    }
    if(!up && !zero) dp[x][s]=ans;
    return ans;
}
int cal(int x)
{
    n=0;
    while(x) a[++n]=x%10,x/=10;
    return dfs(n,0,1,1).second;
}
signed main()
{
    memset(dp,-1,sizeof dp);
    pw[0]=1;
    for(int i=1;i<=18;i++)
        pw[i]=pw[i-1]*10%p;
    l=read();r=read();k=read();
    printf("%lld\n",(cal(r)-cal(l-1)+p)%p);
}

本文地址:https://blog.csdn.net/C202044zxy/article/details/107879545

相关标签: 状压dp 数位dp