QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#281233#1261. InvKLPP#AC ✓63ms493744kbC++141.6kb2023-12-09 23:40:432023-12-09 23:40:44

Judging History

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

  • [2023-12-09 23:40:44]
  • 评测
  • 测评结果:AC
  • 用时:63ms
  • 内存:493744kb
  • [2023-12-09 23:40:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for (int i = a; i < b; i++)
#define trav(a,b) for (auto a : b)
#define lld long long
using i64 = long long;
#define all(x) begin(x),end(x)
int DP[501][501*501];

int per[20];
int comb(int n){
	return (n*(n-1))/2;
}
void solve() {
	int n;
	cin>>n;
	int k;
	cin>>k;
		DP[0][0]=1;
		DP[1][0]=1;
		rep(i,2,n+1){
			int sz=comb(i)+1;

			rep(j,0,sz){
				DP[i][j]=0;
				if(j<=comb(i-1))DP[i][j]=DP[i-1][j];
				if(j-1>=0 && j-1<=comb(i-2))DP[i][j]+=DP[i-2][j-1];
				if(j-2>=0){
					DP[i][j]+=DP[i][j-2];
					if(j-2>=0 && j-2<=comb(i-1)){
						DP[i][j]-=DP[i-1][j-2];
					}
					if(j-2*i+1>=0 && j-2*i+1<=comb(i-2)){
						DP[i][j]-=DP[i-2][j-2*i+1];
					}
				}
				DP[i][j]%=2;
				DP[i][j]+=2;
				DP[i][j]%=2;
				
				//~ rep(l,0,i-1){
					//~ if(j-2*l-1>=0 && j-2*l-1<=comb(i-2)){
						//~ DP[i][j]+=DP[i-2][j-2*l-1];
					//~ }
				//~ }
			}
		}
		//~ rep(i,0,n+1){
			//~ rep(j,0,comb(i)+1)cout<<DP[i][j]<<" ";
			//~ cout<<endl;
		//~ }
		cout<<DP[n][k]%2<<"\n";
		
		//~ int cnt=0;
		//~ rep(i,0,n)per[i]=i;
		//~ do{
			//~ bool is_inv=true;
			//~ rep(i,0,n){
				//~ if(per[per[i]]!=i)is_inv=false;
			//~ }
			//~ if(is_inv){
				//~ int inv=0;
				//~ rep(i,0,n){
					//~ rep(j,i+1,n){
						//~ if(per[i]>per[j])inv++;
					//~ }
				//~ }
				//~ if(inv==k)cnt++;
			//~ }
		//~ }while(next_permutation(per,per+n));
		//~ cout<<cnt<<endl;
		//~ if(DP[n][k]!=cnt)cout<<"ERR\n";
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt = 1;
	//~ cin >> tt;
	while (tt--) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7804kb

input:

4 1

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 13888kb

input:

10 21

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 28ms
memory: 493088kb

input:

500 124331

output:

0

result:

ok answer is '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 24152kb

input:

20 122

output:

1

result:

ok answer is '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 102020kb

input:

100 999

output:

0

result:

ok answer is '0'

Test #6:

score: 0
Accepted
time: 47ms
memory: 493328kb

input:

500 100001

output:

1

result:

ok answer is '1'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

5 0

output:

1

result:

ok answer is '1'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

5 1

output:

0

result:

ok answer is '0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 9788kb

input:

5 2

output:

1

result:

ok answer is '1'

Test #10:

score: 0
Accepted
time: 1ms
memory: 7684kb

input:

5 3

output:

1

result:

ok answer is '1'

Test #11:

score: 0
Accepted
time: 1ms
memory: 7692kb

input:

5 4

output:

0

result:

ok answer is '0'

Test #12:

score: 0
Accepted
time: 1ms
memory: 9852kb

input:

5 5

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

5 6

output:

0

result:

ok answer is '0'

Test #14:

score: 0
Accepted
time: 1ms
memory: 9724kb

input:

5 7

output:

1

result:

ok answer is '1'

Test #15:

score: 0
Accepted
time: 1ms
memory: 9732kb

input:

5 8

output:

1

result:

ok answer is '1'

Test #16:

score: 0
Accepted
time: 1ms
memory: 7732kb

input:

5 9

output:

0

result:

ok answer is '0'

Test #17:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

5 10

output:

1

result:

ok answer is '1'

Test #18:

score: 0
Accepted
time: 43ms
memory: 493744kb

input:

500 73732

output:

1

result:

ok answer is '1'

Test #19:

score: 0
Accepted
time: 61ms
memory: 493144kb

input:

499 21121

output:

1

result:

ok answer is '1'

Test #20:

score: 0
Accepted
time: 63ms
memory: 491368kb

input:

499 100000

output:

0

result:

ok answer is '0'

Test #21:

score: 0
Accepted
time: 47ms
memory: 491504kb

input:

499 62262

output:

1

result:

ok answer is '1'

Test #22:

score: 0
Accepted
time: 43ms
memory: 493120kb

input:

499 23432

output:

1

result:

ok answer is '1'

Test #23:

score: 0
Accepted
time: 36ms
memory: 493120kb

input:

500 12321

output:

0

result:

ok answer is '0'

Test #24:

score: 0
Accepted
time: 31ms
memory: 493188kb

input:

500 60000

output:

1

result:

ok answer is '1'

Test #25:

score: 0
Accepted
time: 48ms
memory: 493064kb

input:

498 7498

output:

1

result:

ok answer is '1'

Test #26:

score: 0
Accepted
time: 39ms
memory: 493120kb

input:

498 76111

output:

1

result:

ok answer is '1'

Test #27:

score: 0
Accepted
time: 37ms
memory: 409092kb

input:

414 41414

output:

1

result:

ok answer is '1'

Test #28:

score: 0
Accepted
time: 19ms
memory: 417296kb

input:

422 42224

output:

1

result:

ok answer is '1'

Test #29:

score: 0
Accepted
time: 19ms
memory: 329288kb

input:

333 33333

output:

1

result:

ok answer is '1'

Test #30:

score: 0
Accepted
time: 23ms
memory: 493608kb

input:

500 51515

output:

1

result:

ok answer is '1'

Test #31:

score: 0
Accepted
time: 19ms
memory: 388672kb

input:

393 21222

output:

1

result:

ok answer is '1'

Test #32:

score: 0
Accepted
time: 40ms
memory: 491876kb

input:

500 124750

output:

1

result:

ok answer is '1'

Test #33:

score: 0
Accepted
time: 35ms
memory: 493152kb

input:

500 124749

output:

1

result:

ok answer is '1'

Test #34:

score: 0
Accepted
time: 40ms
memory: 493624kb

input:

500 0

output:

1

result:

ok answer is '1'

Test #35:

score: 0
Accepted
time: 55ms
memory: 493552kb

input:

500 1

output:

1

result:

ok answer is '1'

Test #36:

score: 0
Accepted
time: 1ms
memory: 5644kb

input:

1 0

output:

1

result:

ok answer is '1'