QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482904 | #7223. The Jump Address | inksamurai | AC ✓ | 141ms | 254064kb | C++23 | 1.7kb | 2024-07-18 00:55:38 | 2024-07-18 00:55:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int) a.size()
#define all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
#define _3zlqvu8 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// snuke's mod int
template <ll mod>
struct modint{
ll x;
modint(ll x=0):x((x%mod+mod)%mod){}
modint operator-()const{return modint(-x);}
modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
modint operator+(const modint a)const{modint res(*this); return res+=a;}
modint operator-(const modint a)const{modint res(*this); return res-=a;}
modint operator*(const modint a)const{modint res(*this); return res*=a;}
modint pow(ll n)const{
modint res=1,x(*this);
while(n){
if(n&1)res*=x;
x*=x;
n>>=1;
}
return res;
}
modint inv()const{return pow(mod-2);}
};
using mint=modint<1000000007>;
void slv(){
int n,k;
cin>>n>>k;
vec(vec(mint)) dp(n+1,vec(mint)(k+1));
dp[1][0]=1;
dp[2][0]=1;
dp[2][1]=1;
rng(i,2,n){
vec(mint) ps(k+1);
rep(j,k+1){
if(j){
ps[j]+=ps[j-1];
}
ps[j]+=dp[i][j];
}
rep(j,k+1){
dp[i+1][j]+=ps[j];
if(j>=i+1){
dp[i+1][j]-=ps[j-(i+1)];
}
}
}
print(dp[n][k].x);
}
signed main(){
_3zlqvu8;
slv();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3864kb
input:
5 5
output:
22
result:
ok answer is '22'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
10 10
output:
21670
result:
ok answer is '21670'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
43 573
output:
151111947
result:
ok answer is '151111947'
Test #4:
score: 0
Accepted
time: 9ms
memory: 12384kb
input:
136 8441
output:
947744762
result:
ok answer is '947744762'
Test #5:
score: 0
Accepted
time: 27ms
memory: 52548kb
input:
250 24855
output:
267058586
result:
ok answer is '267058586'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
19 144
output:
829831149
result:
ok answer is '829831149'
Test #7:
score: 0
Accepted
time: 7ms
memory: 13404kb
input:
165 7898
output:
273298170
result:
ok answer is '273298170'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4772kb
input:
79 2284
output:
391434138
result:
ok answer is '391434138'
Test #9:
score: 0
Accepted
time: 15ms
memory: 33892kb
input:
210 18011
output:
229025031
result:
ok answer is '229025031'
Test #10:
score: 0
Accepted
time: 24ms
memory: 41692kb
input:
222 21624
output:
374536877
result:
ok answer is '374536877'
Test #11:
score: 0
Accepted
time: 43ms
memory: 75940kb
input:
323 28611
output:
322286021
result:
ok answer is '322286021'
Test #12:
score: 0
Accepted
time: 24ms
memory: 40432kb
input:
242 19194
output:
956859180
result:
ok answer is '956859180'
Test #13:
score: 0
Accepted
time: 55ms
memory: 106152kb
input:
301 43058
output:
112369944
result:
ok answer is '112369944'
Test #14:
score: 0
Accepted
time: 5ms
memory: 12848kb
input:
322 3814
output:
494916262
result:
ok answer is '494916262'
Test #15:
score: 0
Accepted
time: 92ms
memory: 150884kb
input:
375 50059
output:
907151160
result:
ok answer is '907151160'
Test #16:
score: 0
Accepted
time: 76ms
memory: 133932kb
input:
353 46837
output:
126652360
result:
ok answer is '126652360'
Test #17:
score: 0
Accepted
time: 4ms
memory: 12912kb
input:
151 8072
output:
625246122
result:
ok answer is '625246122'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
168 266
output:
106628027
result:
ok answer is '106628027'
Test #19:
score: 0
Accepted
time: 18ms
memory: 33936kb
input:
352 11138
output:
303194013
result:
ok answer is '303194013'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
66 1064
output:
667093543
result:
ok answer is '667093543'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
39 344
output:
160009829
result:
ok answer is '160009829'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
8 5
output:
343
result:
ok answer is '343'
Test #23:
score: 0
Accepted
time: 0ms
memory: 4712kb
input:
87 2167
output:
717772069
result:
ok answer is '717772069'
Test #24:
score: 0
Accepted
time: 43ms
memory: 76580kb
input:
280 33040
output:
241903514
result:
ok answer is '241903514'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
25 134
output:
130553510
result:
ok answer is '130553510'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
28 135
output:
309607374
result:
ok answer is '309607374'
Test #27:
score: 0
Accepted
time: 27ms
memory: 52216kb
input:
358 16978
output:
492851973
result:
ok answer is '492851973'
Test #28:
score: 0
Accepted
time: 0ms
memory: 4664kb
input:
158 1233
output:
625631137
result:
ok answer is '625631137'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
154 376
output:
698760105
result:
ok answer is '698760105'
Test #30:
score: 0
Accepted
time: 5ms
memory: 7628kb
input:
105 5266
output:
723203660
result:
ok answer is '723203660'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
16 95
output:
858025878
result:
ok answer is '858025878'
Test #32:
score: 0
Accepted
time: 3ms
memory: 14556kb
input:
360 3971
output:
253466237
result:
ok answer is '253466237'
Test #33:
score: 0
Accepted
time: 3ms
memory: 11660kb
input:
145 7318
output:
821457072
result:
ok answer is '821457072'
Test #34:
score: 0
Accepted
time: 5ms
memory: 13064kb
input:
142 8802
output:
42104268
result:
ok answer is '42104268'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
69 1115
output:
590589426
result:
ok answer is '590589426'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
45 875
output:
567474290
result:
ok answer is '567474290'
Test #37:
score: 0
Accepted
time: 32ms
memory: 64920kb
input:
334 23120
output:
917970258
result:
ok answer is '917970258'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
70 31
output:
102807792
result:
ok answer is '102807792'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
10 39
output:
2298
result:
ok answer is '2298'
Test #40:
score: 0
Accepted
time: 51ms
memory: 80692kb
input:
350 27845
output:
564312115
result:
ok answer is '564312115'
Test #41:
score: 0
Accepted
time: 28ms
memory: 48908kb
input:
226 25325
output:
596579436
result:
ok answer is '596579436'
Test #42:
score: 0
Accepted
time: 9ms
memory: 12100kb
input:
242 4690
output:
317585068
result:
ok answer is '317585068'
Test #43:
score: 0
Accepted
time: 10ms
memory: 24788kb
input:
251 10960
output:
314089256
result:
ok answer is '314089256'
Test #44:
score: 0
Accepted
time: 53ms
memory: 99480kb
input:
299 40557
output:
337066135
result:
ok answer is '337066135'
Test #45:
score: 0
Accepted
time: 15ms
memory: 29868kb
input:
250 13471
output:
575053689
result:
ok answer is '575053689'
Test #46:
score: 0
Accepted
time: 48ms
memory: 94496kb
input:
355 32531
output:
975021749
result:
ok answer is '975021749'
Test #47:
score: 0
Accepted
time: 3ms
memory: 11916kb
input:
211 5254
output:
197909
result:
ok answer is '197909'
Test #48:
score: 0
Accepted
time: 54ms
memory: 86632kb
input:
370 28334
output:
199601902
result:
ok answer is '199601902'
Test #49:
score: 0
Accepted
time: 69ms
memory: 119820kb
input:
362 40586
output:
965702618
result:
ok answer is '965702618'
Test #50:
score: 0
Accepted
time: 4ms
memory: 11832kb
input:
142 7765
output:
744224074
result:
ok answer is '744224074'
Test #51:
score: 0
Accepted
time: 18ms
memory: 25232kb
input:
256 10917
output:
880368585
result:
ok answer is '880368585'
Test #52:
score: 0
Accepted
time: 3ms
memory: 9460kb
input:
158 5041
output:
199261084
result:
ok answer is '199261084'
Test #53:
score: 0
Accepted
time: 9ms
memory: 16672kb
input:
323 5257
output:
648781556
result:
ok answer is '648781556'
Test #54:
score: 0
Accepted
time: 18ms
memory: 33204kb
input:
206 18139
output:
955697459
result:
ok answer is '955697459'
Test #55:
score: 0
Accepted
time: 3ms
memory: 5252kb
input:
93 2885
output:
523005422
result:
ok answer is '523005422'
Test #56:
score: 0
Accepted
time: 55ms
memory: 94988kb
input:
308 37560
output:
677894649
result:
ok answer is '677894649'
Test #57:
score: 0
Accepted
time: 2ms
memory: 8472kb
input:
156 4128
output:
147687615
result:
ok answer is '147687615'
Test #58:
score: 0
Accepted
time: 4ms
memory: 16932kb
input:
315 5464
output:
153116074
result:
ok answer is '153116074'
Test #59:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
77 875
output:
338198198
result:
ok answer is '338198198'
Test #60:
score: 0
Accepted
time: 9ms
memory: 12180kb
input:
281 4077
output:
134947960
result:
ok answer is '134947960'
Test #61:
score: 0
Accepted
time: 32ms
memory: 57436kb
input:
240 28522
output:
522133037
result:
ok answer is '522133037'
Test #62:
score: 0
Accepted
time: 2ms
memory: 4788kb
input:
145 1337
output:
457007578
result:
ok answer is '457007578'
Test #63:
score: 0
Accepted
time: 24ms
memory: 53472kb
input:
265 24032
output:
174507832
result:
ok answer is '174507832'
Test #64:
score: 0
Accepted
time: 82ms
memory: 151248kb
input:
361 51966
output:
98093292
result:
ok answer is '98093292'
Test #65:
score: 0
Accepted
time: 5ms
memory: 12900kb
input:
163 7605
output:
87500368
result:
ok answer is '87500368'
Test #66:
score: 0
Accepted
time: 2ms
memory: 5580kb
input:
112 2456
output:
694228602
result:
ok answer is '694228602'
Test #67:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
140 602
output:
262217147
result:
ok answer is '262217147'
Test #68:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
41 263
output:
159294086
result:
ok answer is '159294086'
Test #69:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
62 423
output:
617782977
result:
ok answer is '617782977'
Test #70:
score: 0
Accepted
time: 66ms
memory: 117900kb
input:
339 42858
output:
919247673
result:
ok answer is '919247673'
Test #71:
score: 0
Accepted
time: 4ms
memory: 11388kb
input:
283 3601
output:
436899526
result:
ok answer is '436899526'
Test #72:
score: 0
Accepted
time: 45ms
memory: 88468kb
input:
290 36876
output:
202033568
result:
ok answer is '202033568'
Test #73:
score: 0
Accepted
time: 2ms
memory: 5052kb
input:
130 1819
output:
835356558
result:
ok answer is '835356558'
Test #74:
score: 0
Accepted
time: 2ms
memory: 4988kb
input:
109 2151
output:
175806468
result:
ok answer is '175806468'
Test #75:
score: 0
Accepted
time: 7ms
memory: 18708kb
input:
285 6904
output:
632562337
result:
ok answer is '632562337'
Test #76:
score: 0
Accepted
time: 67ms
memory: 111880kb
input:
333 41317
output:
249561580
result:
ok answer is '249561580'
Test #77:
score: 0
Accepted
time: 27ms
memory: 51220kb
input:
259 23197
output:
969435882
result:
ok answer is '969435882'
Test #78:
score: 0
Accepted
time: 10ms
memory: 16784kb
input:
159 10881
output:
782931936
result:
ok answer is '782931936'
Test #79:
score: 0
Accepted
time: 72ms
memory: 133764kb
input:
369 44549
output:
766370743
result:
ok answer is '766370743'
Test #80:
score: 0
Accepted
time: 35ms
memory: 59068kb
input:
330 21372
output:
698212240
result:
ok answer is '698212240'
Test #81:
score: 0
Accepted
time: 72ms
memory: 124204kb
input:
327 47009
output:
952052269
result:
ok answer is '952052269'
Test #82:
score: 0
Accepted
time: 4ms
memory: 11364kb
input:
145 7153
output:
448408780
result:
ok answer is '448408780'
Test #83:
score: 0
Accepted
time: 2ms
memory: 5028kb
input:
250 963
output:
640977
result:
ok answer is '640977'
Test #84:
score: 0
Accepted
time: 3ms
memory: 16012kb
input:
177 9160
output:
593516344
result:
ok answer is '593516344'
Test #85:
score: 0
Accepted
time: 5ms
memory: 7524kb
input:
240 2364
output:
802921121
result:
ok answer is '802921121'
Test #86:
score: 0
Accepted
time: 7ms
memory: 9908kb
input:
122 7027
output:
929507063
result:
ok answer is '929507063'
Test #87:
score: 0
Accepted
time: 25ms
memory: 46504kb
input:
342 16107
output:
8886654
result:
ok answer is '8886654'
Test #88:
score: 0
Accepted
time: 26ms
memory: 54100kb
input:
248 25745
output:
749755917
result:
ok answer is '749755917'
Test #89:
score: 0
Accepted
time: 3ms
memory: 6616kb
input:
103 3956
output:
97322678
result:
ok answer is '97322678'
Test #90:
score: 0
Accepted
time: 60ms
memory: 100352kb
input:
298 41077
output:
842560614
result:
ok answer is '842560614'
Test #91:
score: 0
Accepted
time: 51ms
memory: 90476kb
input:
285 38718
output:
886825013
result:
ok answer is '886825013'
Test #92:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 0
output:
1
result:
ok answer is '1'
Test #93:
score: 0
Accepted
time: 26ms
memory: 52424kb
input:
340 18308
output:
400760934
result:
ok answer is '400760934'
Test #94:
score: 0
Accepted
time: 1ms
memory: 4000kb
input:
86 985
output:
776454803
result:
ok answer is '776454803'
Test #95:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
118 308
output:
728023369
result:
ok answer is '728023369'
Test #96:
score: 0
Accepted
time: 3ms
memory: 8900kb
input:
121 5865
output:
763501658
result:
ok answer is '763501658'
Test #97:
score: 0
Accepted
time: 11ms
memory: 18612kb
input:
191 10246
output:
144608876
result:
ok answer is '144608876'
Test #98:
score: 0
Accepted
time: 22ms
memory: 40668kb
input:
300 15887
output:
128248570
result:
ok answer is '128248570'
Test #99:
score: 0
Accepted
time: 141ms
memory: 254064kb
input:
400 79800
output:
1
result:
ok answer is '1'
Test #100:
score: 0
Accepted
time: 71ms
memory: 123804kb
input:
400 38000
output:
905690778
result:
ok answer is '905690778'
Extra Test:
score: 0
Extra Test Passed