QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#482904#7223. The Jump AddressinksamuraiAC ✓141ms254064kbC++231.7kb2024-07-18 00:55:382024-07-18 00:55:38

Judging History

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

  • [2024-07-18 00:55:38]
  • 评测
  • 测评结果:AC
  • 用时:141ms
  • 内存:254064kb
  • [2024-07-18 00:55:38]
  • 提交

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