QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302112#7954. Special Numbersmariowong#AC ✓7ms40440kbC++174.3kb2024-01-10 16:33:142024-01-10 16:33:14

Judging History

This is the latest submission verdict.

  • [2024-01-10 16:33:14]
  • Judged
  • Verdict: AC
  • Time: 7ms
  • Memory: 40440kb
Show
  • [2024-01-10 16:33:14]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;

int primes[] = {2, 3, 5, 7};
// no of ptimes for 1 to 9, starts from 1
int dip[9][4] = {{0, 0, 0, 0},
			   {1, 0, 0, 0},
			   {0, 1, 0, 0},
			   {2, 0, 0, 0},
			   {0, 0, 1, 0},
			   {1, 1, 0, 0},
			   {0, 0, 0, 1},
			   {3, 0, 0, 0},
			   {0, 2, 0, 0}};
int cnt[4], digit[25];
ll f[2][2][57][41][21][25];

ll calc(string n) {
	if (n == "0") return 0;
	int m = n.size();
	for (int i = 0; i < m; i++) {
		digit[i] = n[i] - '0';
	}
	for (int w = 0; w <= cnt[0]; w++) {
		for (int x = 0; x <= cnt[1]; x++) {
			for (int y = 0; y <= cnt[2]; y++) {
				for (int z = 0; z <= cnt[3]; z++) {
					f[0][0][w][x][y][z] = f[0][1][w][x][y][z] = 0;
				}
			}
		}
	}
	f[0][1][0][0][0][0] = 1;
	for (int i = 0; i < m; i++) {
		int cur = i & 1, nxt = cur ^ 1;
		for (int w = 0; w <= cnt[0]; w++) {
			for (int x = 0; x <= cnt[1]; x++) {
				for (int y = 0; y <= cnt[2]; y++) {
					for (int z = 0; z <= cnt[3]; z++) {
						f[nxt][0][w][x][y][z] = f[nxt][1][w][x][y][z] = 0;
					}
				}
			}
		}
		for (int w = 0; w <= cnt[0]; w++) {
			for (int x = 0; x <= cnt[1]; x++) {
				for (int y = 0; y <= cnt[2]; y++) {
					for (int z = 0; z <= cnt[3]; z++) {
						//transition for not cur max
						for (int tt = 0; tt < 9; tt++) {
							int tw = min(w + dip[tt][0], cnt[0]);
							int tx = min(x + dip[tt][1], cnt[1]);
							int ty = min(y + dip[tt][2], cnt[2]);
							int tz = min(z + dip[tt][3], cnt[3]);
							f[nxt][0][tw][tx][ty][tz] = (f[nxt][0][tw][tx][ty][tz] + f[cur][0][w][x][y][z]) % MOD;
						}
						if (i) f[nxt][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] = (f[nxt][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] + f[cur][0][w][x][y][z]) % MOD;
						
						//transition for current is max
						for (int tt = 0; tt < digit[i] - 1; tt++) {
							int tw = min(w + dip[tt][0], cnt[0]);
							int tx = min(x + dip[tt][1], cnt[1]);
							int ty = min(y + dip[tt][2], cnt[2]);
							int tz = min(z + dip[tt][3], cnt[3]);
							f[nxt][0][tw][tx][ty][tz] = (f[nxt][0][tw][tx][ty][tz] + f[cur][1][w][x][y][z]) % MOD;
						}
						if (digit[i] > 0) {
							if (i) f[nxt][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] = (f[nxt][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] + f[cur][1][w][x][y][z]) % MOD;
							int tw = min(w + dip[digit[i] - 1][0], cnt[0]);
							int tx = min(x + dip[digit[i] - 1][1], cnt[1]);
							int ty = min(y + dip[digit[i] - 1][2], cnt[2]);
							int tz = min(z + dip[digit[i] - 1][3], cnt[3]);
							f[nxt][1][tw][tx][ty][tz] = (f[nxt][1][tw][tx][ty][tz] + f[cur][1][w][x][y][z]) % MOD;
						}
						else
							f[nxt][1][cnt[0]][cnt[1]][cnt[2]][cnt[3]] = (f[nxt][1][cnt[0]][cnt[1]][cnt[2]][cnt[3]] + f[cur][1][w][x][y][z]) % MOD;
							
					}
				}
			}
		}
	
		// include number that start at this pos
		if (i) {
			for (int tt = 0; tt < 9; tt++) {
				int tw = min(dip[tt][0], cnt[0]);
				int tx = min(dip[tt][1], cnt[1]);
				int ty = min(dip[tt][2], cnt[2]);
				int tz = min(dip[tt][3], cnt[3]);
				f[nxt][0][tw][tx][ty][tz] = (f[nxt][0][tw][tx][ty][tz] + 1) % MOD;
			}
		}
		
//		cout << digit[i] << endl;
//		for (int w = 0; w <= cnt[0]; w++) {
//			for (int x = 0; x <= cnt[1]; x++) {
//				for (int y = 0; y <= cnt[2]; y++) {
//					for (int z = 0; z <= cnt[3]; z++) {
//						cout << i << ' ' << w << ' ' << x << ' ' << y << ' ' << z << ' ' << f[nxt][0][w][x][y][z] << ' ' << f[nxt][1][w][x][y][z] << endl;
//					}
//				}
//			}
//		}
	}
	return (f[m & 1][0][cnt[0]][cnt[1]][cnt[2]][cnt[3]] + f[m & 1][1][cnt[0]][cnt[1]][cnt[2]][cnt[3]]) % MOD;
}

ll f2[25][10][2];

string minusone(string s) {
	if (s == "1") return "0";
	string rt = s;
	int m = s.size();
	rt[m - 1]--;
	while (rt[m - 1] < '0') {
		rt[m - 1] += 10;
		m--;
		rt[m - 1]--;
	}
	if (rt[0] == '0') rt.erase(rt.begin());
	return rt;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	cout << minusone("100010") << endl;
//	return 0;
	ll k; cin >> k;
	string l, r; cin >> l >> r;
	ll tk = k;
	for (int i = 0; i < 4; i++) {
		cnt[i] = 0;
		while (tk % primes[i] == 0) {
			tk /= primes[i];
			cnt[i]++;
		}
	}
	if (tk != 1) {
		cnt[3] = 24;
	}
	ll tans = (calc(r) - calc(minusone(l)) + MOD) % MOD;
	cout << tans << endl;
	return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9688kb

input:

5 1 20

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 9708kb

input:

5 50 100

output:

19

result:

ok single line: '19'

Test #3:

score: 0
Accepted
time: 0ms
memory: 9708kb

input:

15 11 19

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 2ms
memory: 9924kb

input:

1 100 100000

output:

99901

result:

ok single line: '99901'

Test #5:

score: 0
Accepted
time: 0ms
memory: 9752kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 2ms
memory: 9964kb

input:

10 800 43021

output:

23570

result:

ok single line: '23570'

Test #7:

score: 0
Accepted
time: 0ms
memory: 40440kb

input:

1125899906842624 1 100000000000000000000

output:

555058180

result:

ok single line: '555058180'

Test #8:

score: 0
Accepted
time: 0ms
memory: 12024kb

input:

187500000 5941554024261918062 17356601866920567143

output:

679191360

result:

ok single line: '679191360'

Test #9:

score: 0
Accepted
time: 2ms
memory: 12100kb

input:

1555848 157165614890794026 49792374427566422833

output:

588832126

result:

ok single line: '588832126'

Test #10:

score: 0
Accepted
time: 2ms
memory: 16028kb

input:

53814924637488000 8378901287491856069 46225409092942057365

output:

964965504

result:

ok single line: '964965504'

Test #11:

score: 0
Accepted
time: 7ms
memory: 14352kb

input:

11814720750000000 8152927138245188051 35351923956338524619

output:

183963359

result:

ok single line: '183963359'

Test #12:

score: 0
Accepted
time: 5ms
memory: 20172kb

input:

6453888000000 4334845344448208535 35982793193772682339

output:

570114022

result:

ok single line: '570114022'

Test #13:

score: 0
Accepted
time: 4ms
memory: 13908kb

input:

90071357282285400 7893548167754114409 27099084703937108974

output:

869822186

result:

ok single line: '869822186'

Test #14:

score: 0
Accepted
time: 4ms
memory: 12232kb

input:

45571065750000 177160749596350425 98884377930460959454

output:

607698665

result:

ok single line: '607698665'

Test #15:

score: 0
Accepted
time: 0ms
memory: 22948kb

input:

1128443962982400 6338876482181492537 40931938533793596007

output:

881168270

result:

ok single line: '881168270'

Test #16:

score: 0
Accepted
time: 2ms
memory: 9968kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 3ms
memory: 11904kb

input:

1412793457031250 2410155470167050095 99063185266833009818

output:

399813226

result:

ok single line: '399813226'

Test #18:

score: 0
Accepted
time: 3ms
memory: 24296kb

input:

67722117120000 8909573534349989418 73129289758235281558

output:

898227227

result:

ok single line: '898227227'

Test #19:

score: 0
Accepted
time: 0ms
memory: 22060kb

input:

472055808000 6809917603531307093 27494416416722163137

output:

379198478

result:

ok single line: '379198478'

Test #20:

score: 0
Accepted
time: 5ms
memory: 22036kb

input:

19353600000 8687492345912514346 24058039408337150852

output:

250715555

result:

ok single line: '250715555'

Test #21:

score: 0
Accepted
time: 3ms
memory: 14056kb

input:

47855420020225440 6150828649270625443 84863934988301168136

output:

665186711

result:

ok single line: '665186711'

Test #22:

score: 0
Accepted
time: 0ms
memory: 20112kb

input:

1382400000 9545797804645162278 70441077437727026904

output:

278230087

result:

ok single line: '278230087'

Test #23:

score: 0
Accepted
time: 3ms
memory: 15840kb

input:

816293376 2952089614708276156 10939708785225040670

output:

120954190

result:

ok single line: '120954190'

Test #24:

score: 0
Accepted
time: 2ms
memory: 9960kb

input:

4185097875 1348426133484952253 56617823359794500344

output:

773995224

result:

ok single line: '773995224'

Test #25:

score: 0
Accepted
time: 5ms
memory: 22100kb

input:

5828945117184 7777082394971366991 63470232991138132969

output:

678496908

result:

ok single line: '678496908'

Test #26:

score: 0
Accepted
time: 4ms
memory: 22148kb

input:

16184770560 3869053219872876321 94590086601168840932

output:

168181821

result:

ok single line: '168181821'

Test #27:

score: 0
Accepted
time: 1ms
memory: 10000kb

input:

2 1 12

output:

6

result:

ok single line: '6'

Test #28:

score: 0
Accepted
time: 2ms
memory: 9900kb

input:

30146484375 290228705524339176 51853415145287716863

output:

229436627

result:

ok single line: '229436627'

Test #29:

score: 0
Accepted
time: 0ms
memory: 26452kb

input:

2072513819443200 3726664558969607832 42501102605103061370

output:

947952932

result:

ok single line: '947952932'

Test #30:

score: 0
Accepted
time: 3ms
memory: 18312kb

input:

9920232000000000 4602219263214498291 80783137037024823899

output:

846877519

result:

ok single line: '846877519'

Test #31:

score: 0
Accepted
time: 0ms
memory: 20264kb

input:

97200000000000000 9310820760839688870 35322929083473756214

output:

936587432

result:

ok single line: '936587432'

Test #32:

score: 0
Accepted
time: 0ms
memory: 9744kb

input:

45209390625 5752361069878044328 64635325028527078951

output:

578047592

result:

ok single line: '578047592'

Test #33:

score: 0
Accepted
time: 3ms
memory: 18584kb

input:

54442233216000 2452030574225118723 90982734056131320662

output:

417646585

result:

ok single line: '417646585'

Test #34:

score: 0
Accepted
time: 4ms
memory: 18412kb

input:

1530550080000 7431421026778839808 84825282227911272129

output:

600103842

result:

ok single line: '600103842'

Test #35:

score: 0
Accepted
time: 0ms
memory: 24152kb

input:

13765147361280 4924477486471254843 10002324705150566233

output:

951883713

result:

ok single line: '951883713'

Test #36:

score: 0
Accepted
time: 4ms
memory: 9808kb

input:

59825698242187500 6303744363677706767 91410210495502213963

output:

774734375

result:

ok single line: '774734375'

Test #37:

score: 0
Accepted
time: 2ms
memory: 18020kb

input:

110658879959040 2133591391458550040 48494371567095341228

output:

103505650

result:

ok single line: '103505650'

Test #38:

score: 0
Accepted
time: 1ms
memory: 9932kb

input:

1 3 100

output:

98

result:

ok single line: '98'

Test #39:

score: 0
Accepted
time: 0ms
memory: 20348kb

input:

3160365465600 8968721517098518892 78444481529635953131

output:

364620926

result:

ok single line: '364620926'

Test #40:

score: 0
Accepted
time: 2ms
memory: 9916kb

input:

54838448056132899 4242999884713464056 92948071680698209741

output:

922087167

result:

ok single line: '922087167'

Test #41:

score: 0
Accepted
time: 2ms
memory: 9772kb

input:

78183771565555182 7823307199080715671 93466469990450000599

output:

635073629

result:

ok single line: '635073629'

Test #42:

score: 0
Accepted
time: 0ms
memory: 9964kb

input:

56555532446322947 2952925229100796893 35926880503684324113

output:

663547216

result:

ok single line: '663547216'

Test #43:

score: 0
Accepted
time: 0ms
memory: 9752kb

input:

15701121272683095 8633703383009071570 55273589042372583668

output:

253996413

result:

ok single line: '253996413'

Test #44:

score: 0
Accepted
time: 2ms
memory: 14076kb

input:

11914467542453704 2857068399817941722 83230805830740136213

output:

956698341

result:

ok single line: '956698341'

Test #45:

score: 0
Accepted
time: 2ms
memory: 9752kb

input:

28181999963152819 7948365158338416594 87742700746768593189

output:

720016372

result:

ok single line: '720016372'

Test #46:

score: 0
Accepted
time: 0ms
memory: 9700kb

input:

85409868208332321 3921672860136397259 55474188860042435613

output:

622329181

result:

ok single line: '622329181'

Test #47:

score: 0
Accepted
time: 2ms
memory: 9936kb

input:

14748052718175068 9293071633738211123 85443373435217434149

output:

38392129

result:

ok single line: '38392129'

Test #48:

score: 0
Accepted
time: 2ms
memory: 11852kb

input:

41002058985303228 6141335647135876923 78910335860595680506

output:

665823537

result:

ok single line: '665823537'

Test #49:

score: 0
Accepted
time: 0ms
memory: 9764kb

input:

4 3 123

output:

62

result:

ok single line: '62'

Test #50:

score: 0
Accepted
time: 4ms
memory: 22060kb

input:

100000000000000000 3 100000000000000000000

output:

302574822

result:

ok single line: '302574822'

Test #51:

score: 0
Accepted
time: 2ms
memory: 11844kb

input:

6 7 12034

output:

9505

result:

ok single line: '9505'

Test #52:

score: 0
Accepted
time: 1ms
memory: 9696kb

input:

7 8 43021

output:

25028

result:

ok single line: '25028'

Test #53:

score: 0
Accepted
time: 0ms
memory: 11748kb

input:

8 8 43021

output:

32619

result:

ok single line: '32619'

Test #54:

score: 0
Accepted
time: 0ms
memory: 9972kb

input:

9 800 43021

output:

30930

result:

ok single line: '30930'
English 繁體中文 简体中文

Server Time: 2025-03-02 14:29:41 | OpenSource Project