QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#306162 | #7223. The Jump Address | chenxinyang2006 | AC ✓ | 47ms | 4308kb | C++14 | 3.4kb | 2024-01-16 14:43:10 | 2024-01-16 14:43:10 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
template <int P>
class mod_int
{
using Z = mod_int;
private:
static int mo(int x) { return x < 0 ? x + P : x; }
public:
int x;
int val() const { return x; }
mod_int() : x(0) {}
template <class T>
mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
bool operator==(const Z &rhs) const { return x == rhs.x; }
bool operator!=(const Z &rhs) const { return x != rhs.x; }
Z operator-() const { return Z(x ? P - x : 0); }
Z pow(long long k) const
{
Z res = 1, t = *this;
while (k)
{
if (k & 1)
res *= t;
if (k >>= 1)
t *= t;
}
return res;
}
Z &operator++()
{
x < P - 1 ? ++x : x = 0;
return *this;
}
Z &operator--()
{
x ? --x : x = P - 1;
return *this;
}
Z operator++(int)
{
Z ret = x;
x < P - 1 ? ++x : x = 0;
return ret;
}
Z operator--(int)
{
Z ret = x;
x ? --x : x = P - 1;
return ret;
}
Z inv() const { return pow(P - 2); }
Z &operator+=(const Z &rhs)
{
(x += rhs.x) >= P && (x -= P);
return *this;
}
Z &operator-=(const Z &rhs)
{
(x -= rhs.x) < 0 && (x += P);
return *this;
}
Z operator-()
{
return -x;
}
Z &operator*=(const Z &rhs)
{
x = 1ULL * x * rhs.x % P;
return *this;
}
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o) \
friend T operator o(const Z &lhs, const Z &rhs) \
{ \
Z res = lhs; \
return res o## = rhs; \
}
setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
friend istream& operator>>(istream& is, mod_int& x)
{
long long tmp;
is >> tmp;
x = tmp;
return is;
}
friend ostream& operator<<(ostream& os, const mod_int& x)
{
os << x.val();
return os;
}
};
using Z = mod_int<mod>;
Z power(Z p,ll k){
Z ans = 1;
while(k){
if(k % 2 == 1) ans *= p;
p *= p;
k /= 2;
}
return ans;
}
int n,k;
Z dp[80005];
int main(){
scanf("%d%d",&n,&k);
dp[0] = 1;
rep(i,1,n){
per(j,k - i,0) dp[j + i] -= dp[j];
rep(j,1,k) dp[j] += dp[j - 1];
}
printf("%d\n",dp[k].val());
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4224kb
input:
5 5
output:
22
result:
ok answer is '22'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4108kb
input:
10 10
output:
21670
result:
ok answer is '21670'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4240kb
input:
43 573
output:
151111947
result:
ok answer is '151111947'
Test #4:
score: 0
Accepted
time: 2ms
memory: 4176kb
input:
136 8441
output:
947744762
result:
ok answer is '947744762'
Test #5:
score: 0
Accepted
time: 6ms
memory: 4216kb
input:
250 24855
output:
267058586
result:
ok answer is '267058586'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4244kb
input:
19 144
output:
829831149
result:
ok answer is '829831149'
Test #7:
score: 0
Accepted
time: 2ms
memory: 4240kb
input:
165 7898
output:
273298170
result:
ok answer is '273298170'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
79 2284
output:
391434138
result:
ok answer is '391434138'
Test #9:
score: 0
Accepted
time: 6ms
memory: 4236kb
input:
210 18011
output:
229025031
result:
ok answer is '229025031'
Test #10:
score: 0
Accepted
time: 8ms
memory: 4228kb
input:
222 21624
output:
374536877
result:
ok answer is '374536877'
Test #11:
score: 0
Accepted
time: 15ms
memory: 4284kb
input:
323 28611
output:
322286021
result:
ok answer is '322286021'
Test #12:
score: 0
Accepted
time: 5ms
memory: 4244kb
input:
242 19194
output:
956859180
result:
ok answer is '956859180'
Test #13:
score: 0
Accepted
time: 20ms
memory: 4100kb
input:
301 43058
output:
112369944
result:
ok answer is '112369944'
Test #14:
score: 0
Accepted
time: 3ms
memory: 4284kb
input:
322 3814
output:
494916262
result:
ok answer is '494916262'
Test #15:
score: 0
Accepted
time: 28ms
memory: 4224kb
input:
375 50059
output:
907151160
result:
ok answer is '907151160'
Test #16:
score: 0
Accepted
time: 26ms
memory: 4100kb
input:
353 46837
output:
126652360
result:
ok answer is '126652360'
Test #17:
score: 0
Accepted
time: 3ms
memory: 4280kb
input:
151 8072
output:
625246122
result:
ok answer is '625246122'
Test #18:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
168 266
output:
106628027
result:
ok answer is '106628027'
Test #19:
score: 0
Accepted
time: 3ms
memory: 4260kb
input:
352 11138
output:
303194013
result:
ok answer is '303194013'
Test #20:
score: 0
Accepted
time: 1ms
memory: 4240kb
input:
66 1064
output:
667093543
result:
ok answer is '667093543'
Test #21:
score: 0
Accepted
time: 1ms
memory: 4244kb
input:
39 344
output:
160009829
result:
ok answer is '160009829'
Test #22:
score: 0
Accepted
time: 1ms
memory: 4240kb
input:
8 5
output:
343
result:
ok answer is '343'
Test #23:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
87 2167
output:
717772069
result:
ok answer is '717772069'
Test #24:
score: 0
Accepted
time: 11ms
memory: 4160kb
input:
280 33040
output:
241903514
result:
ok answer is '241903514'
Test #25:
score: 0
Accepted
time: 1ms
memory: 4176kb
input:
25 134
output:
130553510
result:
ok answer is '130553510'
Test #26:
score: 0
Accepted
time: 1ms
memory: 4244kb
input:
28 135
output:
309607374
result:
ok answer is '309607374'
Test #27:
score: 0
Accepted
time: 10ms
memory: 4160kb
input:
358 16978
output:
492851973
result:
ok answer is '492851973'
Test #28:
score: 0
Accepted
time: 1ms
memory: 4160kb
input:
158 1233
output:
625631137
result:
ok answer is '625631137'
Test #29:
score: 0
Accepted
time: 1ms
memory: 4224kb
input:
154 376
output:
698760105
result:
ok answer is '698760105'
Test #30:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
105 5266
output:
723203660
result:
ok answer is '723203660'
Test #31:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
16 95
output:
858025878
result:
ok answer is '858025878'
Test #32:
score: 0
Accepted
time: 3ms
memory: 4284kb
input:
360 3971
output:
253466237
result:
ok answer is '253466237'
Test #33:
score: 0
Accepted
time: 2ms
memory: 4220kb
input:
145 7318
output:
821457072
result:
ok answer is '821457072'
Test #34:
score: 0
Accepted
time: 0ms
memory: 4284kb
input:
142 8802
output:
42104268
result:
ok answer is '42104268'
Test #35:
score: 0
Accepted
time: 1ms
memory: 4144kb
input:
69 1115
output:
590589426
result:
ok answer is '590589426'
Test #36:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
45 875
output:
567474290
result:
ok answer is '567474290'
Test #37:
score: 0
Accepted
time: 12ms
memory: 4164kb
input:
334 23120
output:
917970258
result:
ok answer is '917970258'
Test #38:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
70 31
output:
102807792
result:
ok answer is '102807792'
Test #39:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
10 39
output:
2298
result:
ok answer is '2298'
Test #40:
score: 0
Accepted
time: 15ms
memory: 4148kb
input:
350 27845
output:
564312115
result:
ok answer is '564312115'
Test #41:
score: 0
Accepted
time: 9ms
memory: 4236kb
input:
226 25325
output:
596579436
result:
ok answer is '596579436'
Test #42:
score: 0
Accepted
time: 2ms
memory: 4232kb
input:
242 4690
output:
317585068
result:
ok answer is '317585068'
Test #43:
score: 0
Accepted
time: 5ms
memory: 4240kb
input:
251 10960
output:
314089256
result:
ok answer is '314089256'
Test #44:
score: 0
Accepted
time: 15ms
memory: 4228kb
input:
299 40557
output:
337066135
result:
ok answer is '337066135'
Test #45:
score: 0
Accepted
time: 6ms
memory: 4104kb
input:
250 13471
output:
575053689
result:
ok answer is '575053689'
Test #46:
score: 0
Accepted
time: 14ms
memory: 4184kb
input:
355 32531
output:
975021749
result:
ok answer is '975021749'
Test #47:
score: 0
Accepted
time: 3ms
memory: 4276kb
input:
211 5254
output:
197909
result:
ok answer is '197909'
Test #48:
score: 0
Accepted
time: 16ms
memory: 4156kb
input:
370 28334
output:
199601902
result:
ok answer is '199601902'
Test #49:
score: 0
Accepted
time: 24ms
memory: 4156kb
input:
362 40586
output:
965702618
result:
ok answer is '965702618'
Test #50:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
142 7765
output:
744224074
result:
ok answer is '744224074'
Test #51:
score: 0
Accepted
time: 2ms
memory: 4160kb
input:
256 10917
output:
880368585
result:
ok answer is '880368585'
Test #52:
score: 0
Accepted
time: 2ms
memory: 4240kb
input:
158 5041
output:
199261084
result:
ok answer is '199261084'
Test #53:
score: 0
Accepted
time: 0ms
memory: 4156kb
input:
323 5257
output:
648781556
result:
ok answer is '648781556'
Test #54:
score: 0
Accepted
time: 6ms
memory: 4240kb
input:
206 18139
output:
955697459
result:
ok answer is '955697459'
Test #55:
score: 0
Accepted
time: 1ms
memory: 4148kb
input:
93 2885
output:
523005422
result:
ok answer is '523005422'
Test #56:
score: 0
Accepted
time: 18ms
memory: 4180kb
input:
308 37560
output:
677894649
result:
ok answer is '677894649'
Test #57:
score: 0
Accepted
time: 0ms
memory: 4240kb
input:
156 4128
output:
147687615
result:
ok answer is '147687615'
Test #58:
score: 0
Accepted
time: 3ms
memory: 4148kb
input:
315 5464
output:
153116074
result:
ok answer is '153116074'
Test #59:
score: 0
Accepted
time: 1ms
memory: 4180kb
input:
77 875
output:
338198198
result:
ok answer is '338198198'
Test #60:
score: 0
Accepted
time: 2ms
memory: 4220kb
input:
281 4077
output:
134947960
result:
ok answer is '134947960'
Test #61:
score: 0
Accepted
time: 11ms
memory: 4188kb
input:
240 28522
output:
522133037
result:
ok answer is '522133037'
Test #62:
score: 0
Accepted
time: 1ms
memory: 4104kb
input:
145 1337
output:
457007578
result:
ok answer is '457007578'
Test #63:
score: 0
Accepted
time: 10ms
memory: 4224kb
input:
265 24032
output:
174507832
result:
ok answer is '174507832'
Test #64:
score: 0
Accepted
time: 28ms
memory: 4104kb
input:
361 51966
output:
98093292
result:
ok answer is '98093292'
Test #65:
score: 0
Accepted
time: 2ms
memory: 4284kb
input:
163 7605
output:
87500368
result:
ok answer is '87500368'
Test #66:
score: 0
Accepted
time: 1ms
memory: 4288kb
input:
112 2456
output:
694228602
result:
ok answer is '694228602'
Test #67:
score: 0
Accepted
time: 1ms
memory: 4236kb
input:
140 602
output:
262217147
result:
ok answer is '262217147'
Test #68:
score: 0
Accepted
time: 1ms
memory: 4308kb
input:
41 263
output:
159294086
result:
ok answer is '159294086'
Test #69:
score: 0
Accepted
time: 1ms
memory: 4152kb
input:
62 423
output:
617782977
result:
ok answer is '617782977'
Test #70:
score: 0
Accepted
time: 18ms
memory: 4244kb
input:
339 42858
output:
919247673
result:
ok answer is '919247673'
Test #71:
score: 0
Accepted
time: 2ms
memory: 4228kb
input:
283 3601
output:
436899526
result:
ok answer is '436899526'
Test #72:
score: 0
Accepted
time: 16ms
memory: 4224kb
input:
290 36876
output:
202033568
result:
ok answer is '202033568'
Test #73:
score: 0
Accepted
time: 1ms
memory: 4104kb
input:
130 1819
output:
835356558
result:
ok answer is '835356558'
Test #74:
score: 0
Accepted
time: 0ms
memory: 4164kb
input:
109 2151
output:
175806468
result:
ok answer is '175806468'
Test #75:
score: 0
Accepted
time: 4ms
memory: 4164kb
input:
285 6904
output:
632562337
result:
ok answer is '632562337'
Test #76:
score: 0
Accepted
time: 21ms
memory: 4220kb
input:
333 41317
output:
249561580
result:
ok answer is '249561580'
Test #77:
score: 0
Accepted
time: 9ms
memory: 4148kb
input:
259 23197
output:
969435882
result:
ok answer is '969435882'
Test #78:
score: 0
Accepted
time: 3ms
memory: 4144kb
input:
159 10881
output:
782931936
result:
ok answer is '782931936'
Test #79:
score: 0
Accepted
time: 25ms
memory: 4240kb
input:
369 44549
output:
766370743
result:
ok answer is '766370743'
Test #80:
score: 0
Accepted
time: 11ms
memory: 4148kb
input:
330 21372
output:
698212240
result:
ok answer is '698212240'
Test #81:
score: 0
Accepted
time: 23ms
memory: 4160kb
input:
327 47009
output:
952052269
result:
ok answer is '952052269'
Test #82:
score: 0
Accepted
time: 2ms
memory: 4240kb
input:
145 7153
output:
448408780
result:
ok answer is '448408780'
Test #83:
score: 0
Accepted
time: 1ms
memory: 4224kb
input:
250 963
output:
640977
result:
ok answer is '640977'
Test #84:
score: 0
Accepted
time: 0ms
memory: 4184kb
input:
177 9160
output:
593516344
result:
ok answer is '593516344'
Test #85:
score: 0
Accepted
time: 0ms
memory: 4100kb
input:
240 2364
output:
802921121
result:
ok answer is '802921121'
Test #86:
score: 0
Accepted
time: 2ms
memory: 4280kb
input:
122 7027
output:
929507063
result:
ok answer is '929507063'
Test #87:
score: 0
Accepted
time: 9ms
memory: 4244kb
input:
342 16107
output:
8886654
result:
ok answer is '8886654'
Test #88:
score: 0
Accepted
time: 10ms
memory: 4288kb
input:
248 25745
output:
749755917
result:
ok answer is '749755917'
Test #89:
score: 0
Accepted
time: 1ms
memory: 4308kb
input:
103 3956
output:
97322678
result:
ok answer is '97322678'
Test #90:
score: 0
Accepted
time: 19ms
memory: 4236kb
input:
298 41077
output:
842560614
result:
ok answer is '842560614'
Test #91:
score: 0
Accepted
time: 14ms
memory: 4284kb
input:
285 38718
output:
886825013
result:
ok answer is '886825013'
Test #92:
score: 0
Accepted
time: 1ms
memory: 4220kb
input:
2 0
output:
1
result:
ok answer is '1'
Test #93:
score: 0
Accepted
time: 10ms
memory: 4156kb
input:
340 18308
output:
400760934
result:
ok answer is '400760934'
Test #94:
score: 0
Accepted
time: 1ms
memory: 4104kb
input:
86 985
output:
776454803
result:
ok answer is '776454803'
Test #95:
score: 0
Accepted
time: 1ms
memory: 4216kb
input:
118 308
output:
728023369
result:
ok answer is '728023369'
Test #96:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
121 5865
output:
763501658
result:
ok answer is '763501658'
Test #97:
score: 0
Accepted
time: 4ms
memory: 4220kb
input:
191 10246
output:
144608876
result:
ok answer is '144608876'
Test #98:
score: 0
Accepted
time: 7ms
memory: 4240kb
input:
300 15887
output:
128248570
result:
ok answer is '128248570'
Test #99:
score: 0
Accepted
time: 47ms
memory: 4284kb
input:
400 79800
output:
1
result:
ok answer is '1'
Test #100:
score: 0
Accepted
time: 23ms
memory: 4288kb
input:
400 38000
output:
905690778
result:
ok answer is '905690778'
Extra Test:
score: 0
Extra Test Passed