QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#76806 | #1261. Inv | Lautisticyc | WA | 23ms | 4492kb | C++14 | 2.9kb | 2023-02-12 11:37:53 | 2023-02-12 11:37:56 |
Judging History
answer
/*
是一个排列,然后有一些位置两两交换了。
那么我们记录前面有多少个位置交换了,并且后面一个还没确定的。
每次有新加一个交换,结束一个交换和不动的选择。
然后看下逆序对是怎么变的~
假设现在剩了i个。
那么不动,这i个都会贡献1,同时,他们的后面一个还没有确定,还会贡献1,总贡献2i。
加一个,那么,贡献是2*i+1(1是这两个本身)
减一个,比较麻烦。剩下i-1个贡献2i-2,然后确定了一个,具体确定的是哪一个捏?这个不知道,所以还可能和后面的产生贡献
0~i-1都有可能。
但是这样的话前面也会有这个贡献,所以要*2。
那么状态是dp[i][j][k]表示当前在i,有j个头,k个逆序对的方案数奇偶性。
状态数就n^4了。
……
转移还有个n。
n^5。
分奇偶性差分维护可以n^4吧。
等下转移是不是错了。
加一个,此时不应计算和其他头的逆序对。但可以和其他的尾计算。i+1
减一个,此时可以把这个头和别的头计算,并将这个尾和别的尾和别的头计算。i-1+[0,i-1]*2
------------------------------------------------------------------------------
经过转化,变成了求逆序对个数为k的排列个数奇偶性。
n^3。
dp[i][j]表示当前长度为i,逆序对个数为j。
第i次可加0~i-1。
那么直接来个前缀异或和维护一下好了。
具体是dp[i][j]=sum[i-1][j]^sum[i-1][j-i]
DP[i]=SUM[i-1]^(SUM[i-1]<<i)
SUM[i]捏?
总不能再来硬累一个前缀和吧。
-------------------------------------------------------------------------------------------------
所有的操作都是可用生成函数表示的,也就是我们可以先把前缀和累完。
那么一开始只有0位置有值。
计算一下组合数就有了。
?
1/(1-x)^n
咋个办呢
01234567
0 11111111
1 10101010
2 11001100
3 10001000
4 11110000
5 10100000
6 11000000
7 10000000
solve(i,j)
如果i,j最高位相同。0
如果不同,减掉继续。
到达1,1时返回1
是不是复杂了。
*/
#include<bits/stdc++.h>
using namespace std;
int n,k;
bitset<2000010> bt;
int solve(int x,int y)
{
if(!x||!y) return 1;
// printf("%d %d %d %d %d %d\n",x,__builtin_clz(x),x-(1<<(31-__builtin_clz(x))),y,__builtin_clz(y),y-(1<<(31-__builtin_clz(y))));
if(__builtin_clz(x)==__builtin_clz(y)) return 0;
if(31-__builtin_clz(x)>31-__builtin_clz(y)) return solve(x-(1<<(31-__builtin_clz(x))),y);
else return solve(x,y-(1<<(31-__builtin_clz(y))));
}
int main()
{
// printf(" %d %d %d\n",1-(1<<(31-__builtin_clz(1))),2-(1<<(31-__builtin_clz(2))),3-(1<<(31-__builtin_clz(3))));
scanf("%d %d",&n,&k);
if(!k)
{
printf("0\n");
return 0;
}
for(int i=0;i<=k;++i) bt[i]=solve(n-1,i);
for(int i=1;i<=n;++i) bt^=(bt<<i);
printf("%d\n",(int)bt[k]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 4336kb
input:
4 1
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 3ms
memory: 4264kb
input:
10 21
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 20ms
memory: 4488kb
input:
500 124331
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4492kb
input:
20 122
output:
1
result:
ok answer is '1'
Test #5:
score: 0
Accepted
time: 7ms
memory: 4272kb
input:
100 999
output:
0
result:
ok answer is '0'
Test #6:
score: 0
Accepted
time: 23ms
memory: 4488kb
input:
500 100001
output:
1
result:
ok answer is '1'
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 3940kb
input:
5 0
output:
0
result:
wrong answer expected '1', found '0'