Submission #788695

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788695	2023-07-20T13:35:43 Z	vjudge1	Trol (COCI19_trol)	C++17	50 / 50	2 ms	636 KB

trol

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int N = 2e5+25, lg=18;
ll Mod = 1e9+7;
//ll Mod = 998244353;

ll MOD(ll a, ll mod=Mod)                   {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}
inline ll poww(ll a, ll b) {
    ll ans = 1;
    a=MOD(a);
    while (b) {
        if (b & 1) ans = MOD(ans*a);
        b >>= 1;
        a = MOD(a*a);
    }
    return ans;
}

ll q, dp[20][11][200]; // dp[len][last digit][sum]

ll helper(ll v, int k=0) {
	ll res=0;
	while(v) {
		res += (v%10);
		v/=10;
	}
	if(res<10 || k==1) return res;
	return helper(res);
}


void INITDP() {
	for(int i=0; i<10; i++) dp[1][i][i] = 1;
	for(int len=2; len<=18; len++) {
		for(int d=0; d<10; d++) {
			for(int s=d; s<200; s++) {
				for(int h=0; h<10; h++) dp[len][d][s] += dp[len-1][h][s-d];
			}
		}
	}
}

ll cnt[2][200];
ll query(ll x, int ind) {
	vector<ll> dig;
	fill(cnt[ind], cnt[ind]+200, 0);
	while(x) {
		dig.pb(MOD(x, 10));
		x/=10;
	}
	reverse(all(dig));
	ll ans = 0, now = 0;
	for(int len=0; len<size(dig); len++) {
		for(int d=0; d<dig[len]; d++) {
			for(int sz=now; sz<200; sz++) {
				cnt[ind][sz] += dp[size(dig)-len][d][sz-now];
			}
		}
		now += helper(dig[len], 1);
	}
	for(ll i=1; i<200; i++) {
		if(cnt[ind][i] == 0) continue;
		//cout<<i<<' '<<cnt[ind][i]<<endl;
		ans += (helper(i)*cnt[ind][i]);
	}
	return ans;
}

int main () {
	ios;

	INITDP();
		
	cin>>q;
	while(q--) {
		ll l, r;
		cin>>l>>r;
		cout<<query(r+1, 1)-query(l, 0)<<endl;
		for(int i=0; i<200; i++) {
			if(cnt[1][i]-cnt[0][i]==0) continue;
			//cout<<i<<' '<<cnt[1][i]-cnt[0][i]<<endl;
		}
	}

	return 0;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	2 ms	596 KB	Output is correct
4	Correct	2 ms	636 KB	Output is correct
5	Correct	2 ms	596 KB	Output is correct