[蓝桥] 第十二届国赛真题-异或变换

前言

t a g : tag : tag: 蓝桥杯国赛 周期性 字符串变换 传送门 :

题意 : 给定一个 01 01 01字符串,每个回合字符串都会变化如下 :

s i ′ = s i − 1 ⊕ s i ( i > = 1 ) s'_i=s_{i-1} \oplus s_i (i>=1) si′​=si−1​⊕si​(i>=1), s 0 ′ = s 0 s'_0=s_0 s0′​=s0​

询问 k k k次之后字符串的状态 思路 : 我们经过打表可得,字符串总是 2 t 2^t 2t次一循环, t 表 示 第 一 个 大 于 等 于 字 符 串 长 度 的 二 次 幂 t表示第一个大于等于字符串长度的二次幂 t表示第一个大于等于字符串长度的二次幂

同时又因为字符长度控制在 10000 10000 10000以内,所以我们可以跑一遍暴力

一开始搞出这个规律还是有点疑神疑鬼的,毕竟 2 x 2^x 2x的规律第一次见

暂时不会证明

code :

ll n,k;
string s;

void blgg_orz(){
	
	string temp = s;
	
	
	int len = s.size(); 
	
	for(int i = 1;i