QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137852#6522. Digit ModePetroTarnavskyi#AC ✓130ms3572kbC++172.8kb2023-08-10 18:23:032023-08-10 18:23:28

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 18:23:28]
  • 评测
  • 测评结果:AC
  • 用时:130ms
  • 内存:3572kb
  • [2023-08-10 18:23:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int mod = 1e9 + 7;
int add(int a, int b){
	return (a + b < mod) ? (a + b) : (a + b - mod);
}
void ADD(int &a, int b){
	a = add(a, b);
}
int mult(int a, int b){
	return 1LL * a * b % mod;
}
int binpow(int a, int n){
	int res = 1;
	while(n){
		if(n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

const int N = 50 + 2;
const int A = 10 + 1;
int res0[N] = {0, 45, 570, 5955, 57087, 533943, 5092230, 50327850, 508658835, 141577340, 346748073, 63605721, 691146974, 747499077, 538394750, 265137024, 856024632, 427621971, 516162438, 440472972, 712880662, 791425298, 982743029, 438780983, 383079911, 230599376, 905706960, 197714458, 341824438, 954125005, 98726828, 948875929, 829350644, 341637655, 685873588, 261300047, 133758564, 474399230, 421324133, 863646999, 790696542, 382317337, 207636000, 134734713, 4883420, 322312711, 935473927, 97027071, 538107255, 825526842, 189695037, 799178340};
int fact[N], ober[N];
int dp[A][N];

int DP(int len, VI cnts, int digit, int mx){
	FOR(i, 0, digit)
		cnts[i] = mx - cnts[i];
	
	int ml = mult(fact[len], ober[mx - cnts[digit]]);
	len -= (mx - cnts[digit]);	
	cnts[digit] = 0;
	
	FOR(i, digit + 1, 10)
		cnts[i] = mx - 1 - cnts[i];
	FOR(i, 0, 10)
		if(cnts[i] < 0)
			return 0;
	
	FOR(i, 0, 11)
	FOR(j, 0, len + 1)
		dp[i][j] = 0;

	dp[0][len] = 1;
	FOR(i, 0, 10){
		FOR(j, 0, len + 1){
			if(dp[i][j] == 0)
				continue;
			mx = min(j, cnts[i]);
			FOR(cur, 0, mx + 1)
				ADD(dp[i + 1][j - cur], mult(dp[i][j], ober[cur]));
		}
	}

	return mult(dp[10][0], ml);
}

int solve(int len, VI cnts){		
	int res = 0;
	FOR(bit, 0, 10){
		FOR(mx, 0, len + 1)
			res = add(res, mult(DP(len, cnts, bit, mx + cnts[bit]), bit));
	}
	return res;
}

void solve(){
	string n;
	cin >> n;
	
	VI cnts(10);
	int ans = 0;
	FOR(i, 0, SZ(n)){
		FOR(j, (i == 0), n[i] - '0'){
			cnts[j]++;
			ADD(ans, solve(SZ(n) - 1 - i, cnts));
			cnts[j]--;
		}
		cnts[n[i] - '0']++;
		ans = add(ans, res0[i]);		
	}
	ADD(ans, solve(0, cnts));
	cout << ans << "\n";
}

void prec(){
	fact[0] = 1;
	FOR(i, 1, N)
		fact[i] = mult(fact[i - 1], i);
	ober[N - 1] = binpow(fact[N - 1], mod - 2);
	RFOR(i, N, 1)
		ober[i - 1] = mult(ober[i], i);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	prec();


	int t;
	cin >> t;
	while(t--)
		solve();
		
	//cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
	
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3520kb

input:

5
9
99
999
99999
999999

output:

45
615
6570
597600
5689830

result:

ok 5 number(s): "45 615 6570 597600 5689830"

Test #2:

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

input:

34
7
48
8
76
1
97
7
5
7
7
2
89
9
4
84
46
6
73
86
78
5
3
8
9
31
24
78
7
11
45
2
65
88
6

output:

28
236
36
420
1
597
28
15
28
28
3
525
45
10
484
221
21
399
500
435
15
6
36
45
145
104
435
28
47
215
3
341
516
21

result:

ok 34 numbers

Test #3:

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

input:

16
935
888
429
370
499
881
285
162
178
948
205
858
573
249
773
615

output:

6009
5618
2456
2078
2905
5562
1603
887
993
6121
1174
5378
3333
1374
4724
3631

result:

ok 16 numbers

Test #4:

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

input:

12
1242
9985
6469
9310
4191
9497
3166
3495
9711
9698
4137
2257

output:

7292
63531
37910
58047
23987
59479
18076
19675
61184
61086
23672
12913

result:

ok 12 numbers

Test #5:

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

input:

10
61195
72739
10164
79164
57851
12326
29132
55992
67377
13873

output:

337575
408170
63792
450686
316513
70493
157773
305011
374163
77954

result:

ok 10 numbers

Test #6:

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

input:

8
529983
127270
421121
291729
461233
695056
365028
271160

output:

2744573
687141
2160067
1500426
2359204
3705475
1851172
1381981

result:

ok 8 numbers

Test #7:

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

input:

7
7934351
8474057
1287369
5845624
7796773
5805755
7349121

output:

42465725
45668947
6716401
30094426
41554096
29861098
38756757

result:

ok 7 numbers

Test #8:

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

input:

3
5014252832385738
8762796162648653
919997886706385

output:

892033338
297722019
462512414

result:

ok 3 number(s): "892033338 297722019 462512414"

Test #9:

score: 0
Accepted
time: 15ms
memory: 3564kb

input:

2
775701797726112292362823101
75927988177061355614

output:

371275551
566830847

result:

ok 2 number(s): "371275551 566830847"

Test #10:

score: 0
Accepted
time: 94ms
memory: 3456kb

input:

1
65760982925996012426370962570581226245366145016666

output:

661063035

result:

ok 1 number(s): "661063035"

Test #11:

score: 0
Accepted
time: 105ms
memory: 3520kb

input:

1
62597468169905757754175023836706426691470692832490

output:

9983261

result:

ok 1 number(s): "9983261"

Test #12:

score: 0
Accepted
time: 106ms
memory: 3524kb

input:

1
78912847369504885593964702297317051208901751786824

output:

817123221

result:

ok 1 number(s): "817123221"

Test #13:

score: 0
Accepted
time: 125ms
memory: 3520kb

input:

1
99999999999999999999999999999999999999999999999999

output:

25251932

result:

ok 1 number(s): "25251932"

Test #14:

score: 0
Accepted
time: 90ms
memory: 3524kb

input:

1
999999999999999999999999999999999999999999999

output:

439421821

result:

ok 1 number(s): "439421821"

Test #15:

score: 0
Accepted
time: 55ms
memory: 3564kb

input:

1
9999999999999999999999999999999999999999

output:

387537647

result:

ok 1 number(s): "387537647"

Test #16:

score: 0
Accepted
time: 130ms
memory: 3456kb

input:

1
99999999999999999999999998889999898988888889998888

output:

909431898

result:

ok 1 number(s): "909431898"

Test #17:

score: 0
Accepted
time: 130ms
memory: 3492kb

input:

1
99999999999999999999999998989899988889989889999888

output:

289727470

result:

ok 1 number(s): "289727470"

Test #18:

score: 0
Accepted
time: 130ms
memory: 3464kb

input:

1
99999999999999999999999998998988898888898889898999

output:

962896416

result:

ok 1 number(s): "962896416"

Test #19:

score: 0
Accepted
time: 54ms
memory: 3524kb

input:

1
9999999999999999999989988898888989888899

output:

995903330

result:

ok 1 number(s): "995903330"

Test #20:

score: 0
Accepted
time: 58ms
memory: 3448kb

input:

1
9999999999999999999989999889889998998898

output:

385460258

result:

ok 1 number(s): "385460258"

Test #21:

score: 0
Accepted
time: 126ms
memory: 3492kb

input:

1
99999999999999999999999999999999999999999999999999

output:

25251932

result:

ok 1 number(s): "25251932"