Code Submission Evaluation System Login

HIIT Open 2016

Start:2016-05-28 11:00:00
End:2016-05-28 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2016 - Results
History
2016-05-28 15:04:41
Task:Kaaleppi's puzzle
Sender:Game of Nolife
Submission time:2016-05-28 15:04:41
Language:C++
Status:READY
Result:ACCEPTED

Test results

testverdicttime (s)
#1ACCEPTED0.06 / 5.00details
#2ACCEPTED0.06 / 5.00details
#3ACCEPTED0.05 / 5.00details

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

const ll M=1e9+7;
ll f[1010];
ll g[1010];
ll a[1010],b[1010];
const ll i2=5e8+4;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	a[2]=2;
	b[2]=0;
	g[2]=2;
	for (int i=3;i<=1000;i++) {
		a[i]=(b[i-1]*i2)%M;
		b[i]=(2*a[i-1]+2*b[i-1])%M;
		g[i]=(a[i]+b[i])%M;
	}
//	for (int i=2;i<=6;i++) cout<<g[i]<<endl;
//	cout<<"--"<<endl;
	f[1]=1;
	f[2]=0;
	f[3]=0;
	for (ll i=4;i<=1000;i++) {
		f[i]=((i-2)*f[i-1])%M;
		for (ll k=2;k<i;k++) {
			ll hlp=(g[k]*(i-k)-2)%M;
			hlp*=f[i-k];
			hlp%=M;
			f[i]+=hlp;
			f[i]%=M;
		}
	}
//	for (int i=1;i<=6;i++) cout<<f[i]<<endl;
	int t;
	cin>>t;
	for (int i=0;i<t;i++) {
		int n;
		cin>>n;
		cout<<f[n]<<"\n";
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
view   save

correct output
1
0
0
2
14
90
646
5242
47622
479306
5296790
63779034
831283558
661506141
203183149
878035968
456796197
911763426
428159996
654286749
...
view   save

user output
1
0
0
2
14
90
646
5242
47622
479306
5296790
63779034
831283558
661506141
203183149
878035968
456796197
911763426
428159996
654286749
...
view   save

Test 2

Verdict: ACCEPTED

input
20
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
...
view   save

correct output
436438246
92806357
21003215
151460560
326076265
424575830
228692865
201160758
157874096
500271360
735748839
456205691
368613063
327270428
147787261
753800152
993342525
445553830
110101472
711794305
...
view   save

user output
436438246
92806357
21003215
151460560
326076265
424575830
228692865
201160758
157874096
500271360
735748839
456205691
368613063
327270428
147787261
753800152
993342525
445553830
110101472
711794305
...
view   save

Test 3

Verdict: ACCEPTED

input
20
352
478
99
92
723
608
491
441
38
12
905
907
42
558
218
960
555
381
518
...
view   save

correct output
552481822
246955132
94569313
829032275
94621650
839827603
628162266
795849857
836338597
63779034
646544931
898906053
521761952
479901674
111527011
499723151
220091149
904428111
159152418
190829541
...
view   save

user output
552481822
246955132
94569313
829032275
94621650
839827603
628162266
795849857
836338597
63779034
646544931
898906053
521761952
479901674
111527011
499723151
220091149
904428111
159152418
190829541
...
view   save