QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76806#1261. InvLautisticycWA 23ms4492kbC++142.9kb2023-02-12 11:37:532023-02-12 11:37:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-12 11:37:56]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:4492kb
  • [2023-02-12 11:37:53]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'