[atAGC043B]123 Triangle

不妨先操作一轮，使得$0\le a_{i}\le 2$

结论：若序列中存在1，则答案为0或1

考虑归纳，注意到若序列中存在1，除非所有元素均为1，否则操作一轮后必然仍存在1，那么根据归纳假设即成立，而当所有元素均为1时，显然答案一定为0或1（序列长度已经为1），同样成立

由此，实际上只需要通过奇偶性即可确定答案，而注意到$|x-y|\equiv x+y(mod\ 2)$，因此不妨将转移的式子变为$a'_{i}=a_{i}+a_{i+1}$（模2意义下）

简单计数，不难发现$a_{i}$对答案的贡献即${n-1\choose i-1}a_{i}$，求出其模2的值并相加即可

另外，如果序列中不存在1，分类讨论：

1.若序列中不存在2，显然答案即为0

2.若序列中存在2，不妨将所有$a_{i}$除以2后求出答案，再将答案乘上2即可

时间复杂度为$o(n)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 1000005

 4 int n,a[N];

 5 char s[N];

 6 int C(int n,int m){

 7     return (n&m)==m;

 8 }

 9 int calc(){

10     int ans=0;

11     for(int i=1;i<=n;i++)

12         if (a[i]&1)ans^=C(n-1,i-1);

13     return ans;

14 }

15 int main(){

16     scanf("%d%s",&n,s+1);

17     n--;

18     for(int i=1;i<=n;i++)a[i]=abs((int)s[i]-(int)s[i+1]);

19     bool flag=0;

20     for(int i=1;i<=n;i++)

21         if (a[i]==1)flag=1;

22     if (flag)printf("%d\n",calc());

23     else{

24         flag=0;

25         for(int i=1;i<=n;i++)

26             if (a[i]==2)flag=1;

27         if (!flag)printf("0\n");

28         else{

29             for(int i=1;i<=n;i++)a[i]>>=1;

30             printf("%d\n",(calc()<<1));

31         }

32     }

33     return 0;

34 }

巴特西

[atAGC043B]123 Triangle

最新文章

热门文章