异或变换 ( 数学规律 )

H06:异或变换

总时间限制: 10000ms 

单个测试点时间限制: 1000ms

内存限制: 262144kB

描述

小蓝有一个 01 串 s = s1s2s3 · · · sn。
以后每个时刻，小蓝要对这个 01 串进行一次变换。每次变换的规则相同。
对于 01 串 s = s1s2s3 · · · sn，变换后的 01 串 s′ = s′1s′2s′3· · · s′n 为：
s′1 = s1;
s′i = si−1 ⊕ si。
其中 a ⊕ b 表示两个二进制的异或，当 a 和 b 相同时结果为 0，当 a 和 b 不同时结果为 1。
请问，经过 t 次变换后的 01 串是什么？

输入

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

对于 40% 的评测用例，1 ≤ n ≤ 100, 1 ≤ t ≤ 1000。
对于 80% 的评测用例，1 ≤ n ≤ 1000, 1 ≤ t ≤ 10^9。
对于所有评测用例，1 ≤ n ≤ 10000, 1 ≤ t ≤ 10^18。

输出

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

样例输入

5 3
10110

样例输出

11010

TLE思路:

根据

s′₁ = s₁;
s′_i = s_i−1 ⊕ s_i。

可推导出每一次变换的代码:

for(int i=n-1; i>=1; --i) a[i]^=a[i-1];

然后推导出运算部分的代码:

while (t--) for (int i = n - 1; i >= 1; --i) a[i] ^= a[i - 1];

不过因为

1 ≤ t ≤ 10^18

所以 O(tn) 会超时。能拿到60分

AC思路:

根据以上思路, 试几个数据:

5 3
10110

5 11
10110

5 19
10110

试了后发现, 这几个结果都等于

11010

规律: ti ≌ tj (mod 8)

也就是说, 只需找到模数, 即可获得比该数小且同结果(同余)的数。

所以可以发现, 模数是第一个≥n的2^k。

所以推导出模数公式:

int mod = 1;
while (mod<n) mod<<=1;

或者

int mod = 1;
while (mod<n) mod*=2;

最后直接将t和mod取模即可

t%=mod;

异或部分还是采用了第一种方法, 不过t小了许多, 最多是O((t mod 2^k) × n), 不会超时。

代码:

#include <iostream>
using namespace std;
int a[10000];
int main() {
	ios::sync_with_stdio(false);
	int n, mod = 1; int64_t t; cin >> n >> t;
	string s; cin >> s;
	for (int i = 0; i < n; ++i)a[i] = s[i] - '0';
	while (mod < n) mod <<= 1;
	t %= mod;
	while (t--)
		for (int i = n - 1; i >= 1; --i)a[i] ^= a[i - 1];
	for (int i = 0; i < n; ++i) cout << a[i];
}

内存:

340kB

时间:

24ms

AC