蓝桥杯-异或变换

蓝桥杯-异或变换 蓝桥杯-异或变换 题目描述

小蓝有一个01串 s = s 1 s 2 s 3 . . . s n s = s_1s_2s_3...s_n s=s1​s2​s3​...sn​。

以后每个时刻，小蓝要对这个01串进行一次变换。每次变换的规则相同。对于01串 s = s 1 s 2 s 3 . . . s n s = s_1s_2s_3...s_n s=s1​s2​s3​...sn​，变换后的01串 s ′ = s 1 ′ s 2 ′ s 3 ′ . . . s n ′ s' = s'_1s'_2s'_3...s'_n s′=s1′​s2′​s3′​...sn′​为：
s 1 ′ = s 1 ; s i ′ = s i − 1 ⊕ s i s'_1 = s_1;\ s'_i = s_{i−1}oplus s_i s1′​=s1​;si′​=si−1​⊕si​
请问，经过 t 次变换后的 01串是什么？

输入描述

输入的第一行包含两个整数 n, t，分别表示 01 串的长度和变换的次数。

第二行包含一个长度为 n 的 01 串。

输出描述

输出一行包含一个 01 串，为变换后的串。

输入输出样例 输入样例 #1

5 3
10110

输出样例 #1

11010

说明

对于 40% 的评测用例， 1 ≤ n ≤ 100 , 1 ≤ t ≤ 1000 1 ≤ n ≤ 100, 1 ≤ t ≤ 1000 1≤n≤100,1≤t≤1000。

对于 80% 的评测用例， 1 ≤ n ≤ 1000 , 1 ≤ t ≤ 1 0 9 1 ≤ n ≤ 1000, 1 ≤ t ≤ 10^9 1≤n≤1000,1≤t≤109 。

对于所有评测用例， 1 ≤ n ≤ 10000 , 1 ≤ t ≤ 1 0 18 1 ≤ n ≤ 10000, 1 ≤ t ≤ 10^{18} 1≤n≤10000,1≤t≤1018 。

思路

通过打表得到一个长度为n的01串的循环节为最小的大于等于n的2整数次幂。那么再求几次模拟即可。

代码

#include 

using namespace std;

const int N = 1e4+5;

typedef long long ll;
int a[N],n;
ll t,C;
string s;
int main() 
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  string s = "";
  cin >> n >> t;
  cin >> s;
  s = " " + s;
  for(int i = 1 ; i <= n ;i ++)
    a[i] = s[i] - '0';
  C = 1;
  while(C < n)
    C <<= 1;
  t %= C;
  while(t--)
  {
    for(int i = n ; i >= 2 ; i --)
    {
      a[i] ^= a[i-1];
    }
  }
  for(int i = 1 ; i <= n ; i ++)
    cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714332.html