QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301493 | #7996. 报数 IV | 111445# | AC ✓ | 184ms | 4012kb | C++23 | 1.3kb | 2024-01-09 23:16:33 | 2024-01-09 23:16:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 1000000007
int i,j,k,n,m,t,li,tot;
int f[2][10005],g[2][10005],f1[10005],g1[10005],mp[10005];
int su(int a,int b){a+=b;return (a>=M)?a-M:a;}
string s;
int fuck(int t,int li){
t--;
int i,j,k;
for(i=1;i<=10000;i++){
f1[i]=su(f[0][i],f[1][i]);
}
while(t--){
memset(g1,0,sizeof(g1));
for(i=1;i<=10000;i++){
g1[mp[i]]=su(g1[mp[i]],f1[i]);
}
memcpy(f1,g1,sizeof(g1));
int mx=0;
for(i=1;i<=10000;i++)if(f1[i])mx=i;
if(mx<10)break;
}
return f1[li];
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
for(i=1;i<=10000;i++){
for(auto c:to_string(i)){
mp[i]+=c-'0';
}
}
int T;cin>>T;
while(T--){
cin>>s>>t>>li;
if(li>10000){
cout<<"0\n"; continue;
}
memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
f[1][0]=1; tot=0;
for(auto c:s){
tot+=9;
memset(g[0],0,tot*4+50);
memset(g[1],0,tot*4+50);
c-='0';
for(i=0;i<=tot;i++){
if(f[0][i])for(j=0;j<=9;j++){
g[0][i+j]=su(g[0][i+j],f[0][i]);
}
if(f[1][i])for(j=0;j<=c;j++){
g[j==c][i+j]=su(g[j==c][i+j],f[1][i]);
}
}
memcpy(f[0],g[0],tot*4+50);
memcpy(f[1],g[1],tot*4+50);
}
cout<<fuck(t,li)<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3952kb
input:
2 114 1 5 514 2 10
output:
8 10
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
5 114 1 5 514 2 10 114514 3 7 1919810 2 13 1145141919810114514191981011451419198101145141919810114514191981011451419198101145141919810114514191981011451419198101145141919810 1 79
output:
8 10 12724 504 481046284
result:
ok 5 lines
Test #3:
score: 0
Accepted
time: 146ms
memory: 3948kb
input:
5 3134666912140933323880320519044791121794814671711104987304374190280064994554822259889216567113228716903875026053927191961850586115167336109747673868148288830282192461669674173201533887392623483710043038941036243583011049049915834937139438028987629569618561762595613799223807979488245056374812076511...
output:
0 613343513 0 500149787 932367667
result:
ok 5 lines
Test #4:
score: 0
Accepted
time: 146ms
memory: 3908kb
input:
5 1139519997005658838804233882542131329603951012645222504700958241682545257324091070752720569220022637054777343187779232016568942045167801853025395316038491270541841827939668031807503056209394655628349207403327386083909984082879989255237547274110143051980886947606735206241362546384481120301780245959...
output:
0 0 983106233 842410978 351127737
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 146ms
memory: 3964kb
input:
5 8638076091316635855641492966551052879887835736093039980247820372626975300011595185556660107638347885877620156412525017113706895612406460047827904025826640853053762221239009476530804397983925491363476392003741370633988524528072186299564325622601218035310613510134479162974878452692502169127286160440...
output:
0 151494485 491996396 951216080 735591005
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 142ms
memory: 3964kb
input:
5 4594403190887655851098979323885347301970260472182981436563110607463337770897498592230279433635011809482497666151819612860549852933087582131069399973150048275594755688227873941703801791577493672811179138154635173296855021815570777969295164438906410283251071005981539590431740858876880832337309525533...
output:
452162993 993032288 529250142 0 0
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 109ms
memory: 3848kb
input:
5 7106329661074460076851813089444392472728206874451143771638786962963099120130351553150316525985245033972323999641553983578568333846746709032264525531367915930983812069660457027974526824268427908058438462283103774963889147187903776098321357665707620452891363086885353145154955480116362167820560099473...
output:
0 42143665 0 0 266635325
result:
ok 5 lines
Test #8:
score: 0
Accepted
time: 144ms
memory: 3924kb
input:
5 3197096843267069616758413776891049764649182364659681310636123435063129351340319661216252795154685419993835505771367978692486745621757064307866143997529010856187698866761085397967488612326286182291301655780420802213700700872824442868225191222911023750488609973480926167606063152176688092948837104972...
output:
447917122 738150576 134709012 571675718 0
result:
ok 5 lines
Test #9:
score: 0
Accepted
time: 145ms
memory: 4012kb
input:
5 7612942550467855237767978070830743429305395120370014044416141696259440200835613011108477499855450341979327882148431400498007877975643997499046007388707405687392636406520850657394581417406913024784851871291661719356877660941151602720564069428677800545614776632869404791295787921432277016643912651129...
output:
0 264129072 541216127 357954287 0
result:
ok 5 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
0 0 0 0 0
result:
ok 5 lines
Test #11:
score: 0
Accepted
time: 184ms
memory: 3940kb
input:
5 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
910755804 259808709 937821856 357970005 357970004
result:
ok 5 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0 0 0 0 0
result:
ok 5 lines
Test #13:
score: 0
Accepted
time: 145ms
memory: 4012kb
input:
5 5493600942860040477621631776833866796633825984175588516360787148451695869301784861251377693592220895430016092915864584070561727072786074401876239679966435830840108325415158767012889770532442098922126012279790947926699687673153716303479935588263453954268774120993175103389470374955885050132475090943...
output:
0 300754613 527108222 803186040 892721871
result:
ok 5 lines
Test #14:
score: 0
Accepted
time: 184ms
memory: 3908kb
input:
5 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
320215386 716889023 567624008 357970005 357970006
result:
ok 5 lines
Test #15:
score: 0
Accepted
time: 109ms
memory: 3968kb
input:
5 9812761167325920856130376846862436937947447230654673184010669691739766031552475237221268849030438467080297886603870858917934654394088222131015941324484064243169674411393827605062172844413306867153409653032875875932730337155928621241642891239404177544951325020506663647342309917196598863243062161544...
output:
0 469928597 497418961 0 391423761
result:
ok 5 lines
Test #16:
score: 0
Accepted
time: 105ms
memory: 3916kb
input:
5 9013501952727330363984611655757069529140061668352243348131242141715906906114807898855698384965618856928927417081394644166161162830825179502161401400642096135223979387761058683717466953382929504725324258978052930668420706866257850069631732579721803675116406468720025921542594305209295461027074284529...
output:
385295755 0 826010110 468568966 0
result:
ok 5 lines
Test #17:
score: 0
Accepted
time: 109ms
memory: 3916kb
input:
5 8299276307146554536050575918961724216373725603114732403143797725790612708959386530057274467495195402828666463169527607000394687018773329311746262289704318815996536046048237937697238691975566621555830914989783566285006290394230091450543627201211538144590398957372070315341068147825604925011592907516...
output:
0 510867977 0 343376120 214886107
result:
ok 5 lines
Test #18:
score: 0
Accepted
time: 181ms
memory: 3956kb
input:
5 5978386495534656451410085599244329473463314859713321863671010880820574367293215984254435511977274737538376669406905970846704986107233076928078383576465358933281714235428695844731759396130287355362520342786149980212289046796827813545285558877894772706667916112882424152831253823242761178245591040551...
output:
200381997 248732590 659988610 728803841 281731921
result:
ok 5 lines
Test #19:
score: 0
Accepted
time: 146ms
memory: 3928kb
input:
5 3653745784886652871154357862309923857817567252560725002381570519161248252147392315049190794174402649782040388482129025970204654043850249370372033244471538178164319261755776547097203201498608147530621634820597155316537832780268365695458704201328436275425247055333335893078213722495376788491166394840...
output:
0 827622189 909406252 224192882 472231991
result:
ok 5 lines
Test #20:
score: 0
Accepted
time: 177ms
memory: 3984kb
input:
5 8033033272391208112504025738196814953295344818136472894597554051040020955286362518341894063333412258812817219386808976514037940329057156352396807896773931916676875163079204283714827821854630201268421360605246824369120510639882686009186217462096143084170888173631995492474470043432451899005431488434...
output:
210535726 822079653 985955681 540372548 893241037
result:
ok 5 lines
Test #21:
score: 0
Accepted
time: 74ms
memory: 3960kb
input:
5 5567143473825105413062640204906776053975645715210961093621242820515284746059383788299405075430487954445602098969989027355660374546878999126847721403752212660945084700687121976823655410921184811436776882931203119629438066770465897899783553110960619700314302907304525788754873835497787674395031347966...
output:
0 0 358266018 0 50998365
result:
ok 5 lines