QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#196584 | #6522. Digit Mode | ucup-team870# | AC ✓ | 394ms | 7668kb | C++14 | 2.2kb | 2023-10-01 19:49:20 | 2023-10-01 19:49:21 |
Judging History
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"