数位dp:Educational Codeforces Round 53 (Rated for Div. 2) E. Segment Sum

摘要:
跟普通的数位dp相比,这道题的不同在于是求总和,不是求数字的个数,但我们可以在求数字个数的基础上再进行求和,以下可以看代码注释。gcd:a;}inlinelllcm{returna/gcd(a,b)*b;}intmonth[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};intdir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{1,-1},{-1,1}};constintMAXN=2e5+5;constintINF=1˂˂30;constlonglongmod=998244353;constdoubleeps=1e-8;constllinff=0x3f3f3f3f3f3f3f3f;lldp[25][1030][12];/*记录答案总和的数组*/lld[25][1030];/*记录答案个数的数组*/llt[25];/*10的幂次方,节省时间*/inta[25];/*记录每一位数字*/intf[25];/*2的幂次方,节省时间*/intk[1030];/*状态压缩,记录某个状态有多少个不同的数字*/intp;/*题目问的最大不同数量*/structnum{lla,b;/*a对应d数组,b对应dp数组*/}s;numdfs{if{return{1,now};}if(!a[pos]:9,g;llans=0,cnt=0;FOR{if/*前导0的特殊判断*/{s=dfs;cnt+=s.a;/*答案个数*/ans+=s.b;/*答案总和*/cnt%=mod;ans%=mod;}else{g=sta|f[i];if{s=dfs;cnt+=s.a;/*答案个数*/ans+=s.b;/*答案总和*/cnt%=mod;ans%=mod;}}}ans=%mod;if(!

给出上下界,让你求出其中满足条件:不同的数字的数量不超过k个的数字的总和,答案模998244353,比如123里不同的数字个数为3,113里不同的数字个数为2,111里不同的数字个数为1。

跟普通的数位dp相比,这道题的不同在于是求总和,不是求数字的个数,但我们可以在求数字个数的基础上再进行求和,以下可以看代码注释。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<iomanip>
#include<cctype> 
#include<ctime>
using namespace std;
typedef long long ll;
#define edl putchar('
')
#define sscc ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define FORLL(i,a,b) for(ll i=a;i<=b;i++)
#define ROFLL(i,a,b) for(ll i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
#define zero(x)(((x)>0?(x):-(x))<eps)
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int month[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{1,-1},{-1,1}};
const int MAXN=2e5+5;
const int INF=1<<30;
const long long mod=998244353;
const double eps=1e-8;
const ll inff=0x3f3f3f3f3f3f3f3f;
ll dp[25][1030][12];/*记录答案总和的数组*/
ll d[25][1030];/*记录答案个数的数组*/
ll t[25];/*10的幂次方,节省时间*/
int a[25];/*记录每一位数字*/
int f[25];/*2的幂次方,节省时间*/
int k[1030];/*状态压缩,记录某个状态有多少个不同的数字*/
int p;/*题目问的最大不同数量*/
struct num
{
	ll a,b;/*a对应d数组,b对应dp数组*/
}s;
num dfs(int pos,int now,int sta,int limit)
{
	if(pos==0)
	{
		return (num){1,now};
	}	
	if(!limit&&dp[pos][sta][now]!=-1)
	{
		return (num){d[pos][sta],dp[pos][sta][now]};
	}
	int up=limit?a[pos]:9,g;
	ll ans=0,cnt=0;
	FOR(i,0,up)
	{
		if(sta==0&&i==0)/*前导0的特殊判断*/ 
		{
			s=dfs(pos-1,i,sta,limit&&i==up);
			cnt+=s.a;/*答案个数*/
			ans+=s.b;/*答案总和*/
			cnt%=mod;
			ans%=mod;
		}
		else
		{
			g=sta|f[i];
			if(k[g]<=p)
			{
				s=dfs(pos-1,i,g,limit&&i==up);
				cnt+=s.a;/*答案个数*/
				ans+=s.b;/*答案总和*/
				cnt%=mod;
				ans%=mod;
			}
		}	
	}
	ans=(ans+cnt*t[pos]%mod*(ll)now%mod)%mod;
	if(!limit)
		d[pos][sta]=cnt,dp[pos][sta][now]=ans;
	return (num){cnt,ans};
}
ll solve(ll x)
{
	if(x==0) return 0;
    int pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    a[pos+1]=0;
    return dfs(pos,0,0,1).b;
}
int main()
{
    ll n,m;
    f[0]=1,t[0]=1;
    FOR(i,1,18)
    f[i]=f[i-1]*2,t[i]=t[i-1]*10,t[i]%=mod;
    FOR(i,0,1024)
    {
    	int j=i,cnt=0;
    	while(j)
    	{
    		cnt+=j%2;
    		j/=2;
		}
		k[i]=cnt;
	}
    FOR(i,0,20)
    FOR(j,0,1024)
    {
    	d[i][j]=-1;
	    FOR(I,0,9)
	    dp[i][j][I]=-1;
	}
    //scanf("%d",&T);
    //while(1)
    {
    	scanf("%lld%lld%d",&n,&m,&p);
        n=solve(n-1);
        m=solve(m);
		printf("%lld
",(m-n+mod)%mod);
    }
    return 0;
}

免责声明:文章转载自《数位dp:Educational Codeforces Round 53 (Rated for Div. 2) E. Segment Sum》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Core Animation 文档翻译 (第二篇)—核心动画基础要素Java-数据类型(八种基本数据类型)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

LCA问题【RMQ+Tarjan】

LCA-求树上两点最近公共祖先问题 lrj的紫书上提供了一种将LCA问题转化为RMQ问题的方法,即dfs一次处理出一个序列,first(u)代表u第一次出现的下标,则对于u,v的最近公共祖先的下标即为RMQ(first(u), first(v))。 LCA->RMQ(在线处理): 1 #include<bits/stdc++.h> 2...

员工管理系统(完整版)

转载请注明出处:http://blog.csdn.net/u012860063 #include <stdio.h> #include <windows.h> #include <string.h> struct worker { int num; char name[20]; char zhiche...

CSP/NOIP c++常用模板

蒟蒻目前还是提高组选手,模板将会持续更新!目录: 线段树 对拍 exgcd st 树状数组 树剖 dijsktra spfa tarjan 匈牙利 埃筛 差分树状数组 dinic 快速幂取余 Exgcd #include<bits/stdc++.h> using namespace std; int exgcd(int a,int b,int...

scanf函数的使用

函数原型编辑 1 intscanf( constchar*format, ... ); scanf()函数是格式化输入函数,它从标准输入设备(键盘) 读取输入的信息。 其调用格式为: scanf("<格式化字符串>",<地址表>); 函数 scanf() 是从标准输入流 stdio 中读内容的通用子程序,可以读入全部固...

动态规划——线性dp

我们在解决一些线性区间上的最优化问题的时候,往往也能够利用到动态规划的思想,这种问题可以叫做线性dp。在这篇文章中,我们将讨论有关线性dp的一些问题。 在有关线性dp问题中,有着几个比较经典而基础的模型,例如最长上升子序列(LIS)、最长公共子序列(LCS)、最大子序列和等,那么首先我们从这几个经典的问题出发开始对线性dp的探索。 首先我们来看最长上升子序...

Linux时间操作(time、gettimeofday)

http://blog.chinaunix.net/uid/24148050.html  http://blog.csdn.net/scottgly/article/details/6568513 一、time函数    #include <time.h> time_t time(time_t *calptr); 返回距计算机元年的秒...