QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137852 | #6522. Digit Mode | PetroTarnavskyi# | AC ✓ | 130ms | 3572kb | C++17 | 2.8kb | 2023-08-10 18:23:03 | 2023-08-10 18:23:28 |
Judging History
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"