AtCoder Grand Contest 043 B - 123 Triangle （组合数学&奇偶性）

101 阅读 0 评论 67 点赞

我是靠谱客的博主甜美香水，这篇文章主要介绍AtCoder Grand Contest 043 B - 123 Triangle （组合数学&奇偶性），现在分享给大家，希望可以做个参考。

AtCoder Grand Contest 043 B - 123 Triangle （组合数学&奇偶性）

题目传送门

题意：给长度为n由（1，2，3)组成序列求按相邻绝对差值运算后结果是多少。

分析：
------ step1.由于是绝对差值，所以（1，2，3）等价于（0，1，2）运算.
-------step2.结果只能在（0，1，2）中，首先可以对奇偶性进行判断。
-------step3.根据杨辉三角可知每个数的使用次数为C(n-1,i)如果最后1的使用次数为奇数结果肯定为1，因为1与0或2相减结果都为1。
-------step4.接下来讨论结果为0或2的情况。
------------pos1.结果为2，肯定结果倒推，2->{0,2}->{0,2,0}一直推下取可知原序列不可能有1，所以当序列中无1时，就相当于0和2进行异或运算，同样每个数贡献次数也是C(n-1,i）由于0^任何数都为0，所以只需考虑2的次数，如果2的次数为奇数，答案为2.
------------pos2.其他情况结果都为0.

一个结论：
在这里插入图片描述
简要证明方法见我的另一个博客：传送门

AC代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main(){
	int b[3]={},n,f=0;
	string a;
	cin>>n>>a;
	for(int i=0;i<n;i++) 
	{
		--a[i];
		if(a[i]=='1') f=1;
		b[a[i]-'0']+=(((n-1)&i)==i);
	}
	if(b[1]&1) puts("1");
	else if(!f&&(b[2]&1)) puts("2");
	else puts("0");
	return 0;
}