QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#281233 | #1261. Inv | KLPP# | AC ✓ | 63ms | 493744kb | C++14 | 1.6kb | 2023-12-09 23:40:43 | 2023-12-09 23:40:44 |
Judging History
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'