Educational Codeforces Round 53 E. Segment Sum(数位DP)

时间：2021-08-13 23:34:08

Educational Codeforces Round 53 E. Segment Sum

题意：

问[L,R]区间内有多少个数满足:其由不超过k种数字构成。

思路:

数位DP裸题，也比较好想。由于没考虑到前导０，卡了很久。但最惨的是，由于每次求和的时候需要用到10的pos次幂，我是用提前算好的10的最高次幂，然后每次除以10往下传参。但我手贱取模了，导致每次除以10之后答案就不同余了，这个NC细节错误卡了我一小时才发现。

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<map>

#include<queue>

#include<string>

#include<vector>

#include<cmath>

#include<climits>

#include<functional>

#include<set>

#define dd(x) cout<<#x<<" = "<<x<<" "

#define de(x) cout<<#x<<" = "<<x<<endl

#define fi first

#define se second

#define mp make_pair

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<ll,ll> P;

typedef vector<int> V;

typedef map<int,int> M;

typedef queue<int> Q;

typedef priority_queue<int> BQ;

typedef priority_queue<int,vector<int>,greater<int> > SQ;

const int maxn=2e5+10,INF=0x3f3f3f3f,mod=998244353;

int k,dig[30];

P dp[30][2000];

inline ll add(ll a,ll b)

{

  a+=b;

  return a>=mod?a-mod:a;

}

inline ll mul(ll a,ll b)

{

  return a*b%mod;

}

bool check(int sta)

{

  int cnt=0;

  for (int i=0;i<=9;++i)

  	if (sta&(1<<i))

  	  cnt++;

  return cnt<=k;

}

P dfs(int pos,int sta,ll v,int lead,int lit)

{

  if (pos==-1)

  	return mp(0,1);

  if (!lit&&dp[pos][sta].fi!=-1)

  	return dp[pos][sta];

  int up=lit?dig[pos]:9;

  ll sum=0,cnt=0;

  for (int i=0;i<=up;++i)

  {

  	int ns=(lead&&i==0)?sta:(sta|(1<<i));

	if (!check(ns))

	  continue;

	P tmp=dfs(pos-1,ns,v/10,lead&&i==0,lit&&i==dig[pos]);

	cnt=add(cnt,tmp.se);

	sum=add(sum,add(tmp.fi,mul(tmp.se,mul(i,v))));

  }

  if (!lit)

	dp[pos][sta]=mp(sum,cnt);

  return mp(sum,cnt);

}

ll count(ll n)

{

  int pos=0;

  while (n)

  {

  	dig[pos++]=n%10;

  	n/=10;

  }

  ll v=1;

  for (int i=0;i<pos-1;++i)

  	v*=10;

  return dfs(pos-1,0,v,1,1).fi;

}

int main()

{

  memset(dp,-1,sizeof(dp));

  ll l,r;

  cin>>l>>r>>k;

  cout<<add(count(r)-count(l-1),mod);

  return 0;

}

相关文章