QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#196584#6522. Digit Modeucup-team870#AC ✓394ms7668kbC++142.2kb2023-10-01 19:49:202023-10-01 19:49:21

Judging History

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

  • [2023-10-01 19:49:21]
  • 评测
  • 测评结果:AC
  • 用时:394ms
  • 内存:7668kb
  • [2023-10-01 19:49:20]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,l,r) for(int i=l; i<=r; i++)
#define per(i,l,r) for(int i=l;i>=r;i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
const int mo=1e9+7;
int a[11]; ll dp[13][53][13][53];
ll c[53][53];
void init(){
    For(i,0,50) c[i][0]=1;
    For(i,1,50) For(j,1,i) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
}
ll cal(int n){
    int ma=-1,ii;
    For(i,0,9) if (a[i]>=ma) ma=a[i],ii=i;
    if (!n) return ii;
    memset(dp,0,sizeof(dp));
    //For(i,0,9) For(j,0,n) memset(dp[i][j],0,sizeof(dp[i][j]));
    For(i,0,n) dp[0][i][0][i+a[0]]=c[n][i];
    For(i,0,8) For(j,0,n) For(k,0,i) For(l,0,n+ma) if (dp[i][j][k][l]){
        //if (n==1) cout<<i<<' '<<j<<' '<<k<<' '<<l<<' '<<dp[i][j][k][l]<<endl;
        ll tmp=dp[i][j][k][l];
        For(d,0,n-j){
            int now=a[i+1]+d;
            if (l>now) dp[i+1][d+j][k][l]=(dp[i+1][d+j][k][l]+c[n-j][d]*tmp)%mo;
            else dp[i+1][d+j][i+1][d+a[i+1]]=(dp[i+1][d+j][i+1][d+a[i+1]]+c[n-j][d]*tmp)%mo;
        }
    }
    ll ans=0;
    For(k,0,9) For(l,1,n+ma){
        //if (n==1) cout<<' '<<k<<' '<<l<<' '<<dp[9][n][k][l]<<endl;
        ans=(ans+dp[9][n][k][l]*k)%mo;
    }
    return ans%mo;
}
ll ani[53];
char ch[53];
ll work(int n){
    ll ans=0;
    For(i,1,n){
        int mi=0; if (i==1) mi=1;
        int ma=ch[i]-1; if (i==n) ma=ch[i];
        For(j,mi,ma){
            ++a[j]; ans+=cal(n-i); --a[j];
        }
        ++a[ch[i]];
    }
    return ans%mo;
}
int main(){
    init();
    For(i,1,49){
        For(j,1,9){
            memset(a,0,40);
            a[j]=1;
            ani[i]+=cal(i-1);
            //cout<<endl;
        }
        ani[i]%=mo;
    }
    /*
    int ss=0;
    For(i,1,6){
        ss+=ani[i];
        cout<<' '<<ss<<endl;
    }*/
    int _; cin>>_;
    while(_--){
        scanf("%s",ch+1);
        //For(i,1,50) ch[i]='9';
        int n=strlen(ch+1);
        memset(a,0,40);
        ll ans=0;
        For(i,1,n-1) ans+=ani[i];
        For(i,1,n) ch[i]-=48;
        ans+=work(n);
        printf("%lld\n",ans%mo);
    }
    return 0;
    //cerr<<clock()<<endl;
}
/*
9
98
998
99998
999998
*/

详细

Test #1:

score: 100
Accepted
time: 201ms
memory: 7520kb

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: 202ms
memory: 7644kb

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: 207ms
memory: 7668kb

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: 213ms
memory: 7644kb

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: 210ms
memory: 7516kb

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: 211ms
memory: 7668kb

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: 215ms
memory: 7648kb

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: 224ms
memory: 7564kb

input:

3
5014252832385738
8762796162648653
919997886706385

output:

892033338
297722019
462512414

result:

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

Test #9:

score: 0
Accepted
time: 230ms
memory: 7656kb

input:

2
775701797726112292362823101
75927988177061355614

output:

371275551
566830847

result:

ok 2 number(s): "371275551 566830847"

Test #10:

score: 0
Accepted
time: 301ms
memory: 7504kb

input:

1
65760982925996012426370962570581226245366145016666

output:

661063035

result:

ok 1 number(s): "661063035"

Test #11:

score: 0
Accepted
time: 310ms
memory: 7656kb

input:

1
62597468169905757754175023836706426691470692832490

output:

9983261

result:

ok 1 number(s): "9983261"

Test #12:

score: 0
Accepted
time: 307ms
memory: 7644kb

input:

1
78912847369504885593964702297317051208901751786824

output:

817123221

result:

ok 1 number(s): "817123221"

Test #13:

score: 0
Accepted
time: 389ms
memory: 7596kb

input:

1
99999999999999999999999999999999999999999999999999

output:

25251932

result:

ok 1 number(s): "25251932"

Test #14:

score: 0
Accepted
time: 339ms
memory: 7576kb

input:

1
999999999999999999999999999999999999999999999

output:

439421821

result:

ok 1 number(s): "439421821"

Test #15:

score: 0
Accepted
time: 296ms
memory: 7608kb

input:

1
9999999999999999999999999999999999999999

output:

387537647

result:

ok 1 number(s): "387537647"

Test #16:

score: 0
Accepted
time: 390ms
memory: 7528kb

input:

1
99999999999999999999999998889999898988888889998888

output:

909431898

result:

ok 1 number(s): "909431898"

Test #17:

score: 0
Accepted
time: 394ms
memory: 7660kb

input:

1
99999999999999999999999998989899988889989889999888

output:

289727470

result:

ok 1 number(s): "289727470"

Test #18:

score: 0
Accepted
time: 389ms
memory: 7644kb

input:

1
99999999999999999999999998998988898888898889898999

output:

962896416

result:

ok 1 number(s): "962896416"

Test #19:

score: 0
Accepted
time: 301ms
memory: 7580kb

input:

1
9999999999999999999989988898888989888899

output:

995903330

result:

ok 1 number(s): "995903330"

Test #20:

score: 0
Accepted
time: 299ms
memory: 7648kb

input:

1
9999999999999999999989999889889998998898

output:

385460258

result:

ok 1 number(s): "385460258"

Test #21:

score: 0
Accepted
time: 393ms
memory: 7640kb

input:

1
99999999999999999999999999999999999999999999999999

output:

25251932

result:

ok 1 number(s): "25251932"