General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
44875373 Practice:
zyfzyf
1073E - 9 GNU C++11 Wrong answer on test 7 31 ms 740 KB 2018-10-25 19:56:41 2018-10-25 19:56:41
 
 
→ Source
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
#define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
#define maxn (1050)
#define mod (998244353)
#define ll long long
#define inf 1000000000
using namespace std;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
inline bool is_down(char x) { return ('a' <= x && x <= 'z'); }
inline bool is_upper(char x) { return ('A' <= x && x <= 'Z'); }
inline bool is_digit(char x) { return ('0' <= x && x <= '9'); }
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
    return x*f;
}
inline ll readll()
{
	ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
    return x*f;
}
long long gcd(long long x,long long y){return y?gcd(y,x%y):x;}
long long power(long long x,long long y)
{
	long long t=1;
	for(;y;y>>=1,x=x*x%mod)
		if(y&1)t=t*x%mod;
	return t;
}
/*
struct edge
{
	int go,next;
}e[2*maxn];
void insert(int x,int y)
{
	e[++tot]=(edge){y,head[x]};head[x]=tot;
	e[++tot]=(edge){x,head[y]};head[y]=tot;
}
*/
int kk;
int sum[maxn];
ll dp[22][maxn][2];
ll s[22][maxn][2];
ll work(ll w)
{
	if(!w)return 0;
	vector<int>a;
	a.clear();
	while(w)a.push_back(w%10),w/=10;
	reverse(a.begin(),a.end());
	int n=a.size();
	memset(dp,0,sizeof(dp));
	memset(s,0,sizeof(s));
	rep(i,1,a[0]-1)dp[0][1<<i][0]=i,s[0][1<<i][0]=1;
	s[0][0][0]=1;
	dp[0][1<<a[0]][1]=a[0];
	s[0][1<<a[0]][1]=1;
	rep(i,0,n-2)rep(j,0,1023)
	{
		rep(k,0,9)
		{
			(dp[i+1][j|(1<<k)][0]+=dp[i][j][0]*10%mod+s[i][j][0]*k%mod)%=mod;
			(s[i+1][j|(1<<k)][0]+=s[i][j][0])%=mod;
		}
		rep(k,0,a[i+1]-1)
		{
			(dp[i+1][j|(1<<k)][0]+=dp[i][j][1]*10%mod+s[i][j][1]*k%mod)%=mod;
			(s[i+1][j|(1<<k)][0]+=s[i][j][1])%=mod;
		}
		rep(k,a[i+1],a[i+1])
		{
			(dp[i+1][j|(1<<k)][1]+=dp[i][j][1]*10%mod+s[i][j][1]*k%mod)%=mod;
			(s[i+1][j|(1<<k)][1]+=s[i][j][1])%=mod;
		}
		//cout<<i<<' '<<j<<' '<<dp[i][j][0]<<' '<<dp[i][j][1]<<endl;
	}
	ll ans=0;
	rep(i,0,1023)rep(j,0,1)if(sum[i]<=kk) 
	{
		if(dp[n-1][i][j])
		{
			//cout<<n-1<<' '<<i<<' '<<j<<' '<<dp[n-1][i][j]<<endl;
		}
		(ans+=dp[n-1][i][j])%=mod;
	}
	return ans;
}
int main()
{
	ll l=readll(),r=readll();kk=read();
	rep(i,0,1023)
	{
		int j=i;
		while(j)sum[i]++,j-=j&(-j);
	}
//	cout<<r<<' '<<work(r)<<endl;
//	cout<<(l-1)<<' '<<work(l-1)<<endl;
	ll ans=work(r)-work(l-1);
	cout<<(ans%mod+mod)%mod<<endl; 
	return 0;
}


 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details