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