题目描述：
农夫约翰对牛棚里昏暗的灯光感到不满，刚刚安装了一个新吊灯。
新吊灯由 $ N $ 个灯泡组成，这 $ N $ 个灯泡围成一圈，编号为 $ 0 \sim N−1 $ 。
奶牛对这个新吊灯非常着迷，并且喜欢玩以下游戏：
对于第 $ i $ 个灯泡，如果在 $ T−1 $ 时刻，它左侧的灯泡（当 $ i>0 $ 时，为第 $ i−1 $ 个灯泡；当 $ i=0 $ 时，为第 $ N−1 $ 个灯泡）是开着，那么在 $ T $ 时刻，就切换这个灯泡的状态。
这个游戏将持续 $ B $ 单位时间。
给定灯泡的初始状态，请确定在 $ B $ 单位时间后，它们的最终状态。
输入格式
第一行包含两个整数 $ N $ 和 $ B $ 。
接下来 $ N $ 行，按顺序描述每个灯泡的初始状态，每行包含一个整数 $ 1 $ （表示开）或 $ 0 $ （表示关）。
输出格式
共 $ N $ 行，按顺序每行输出一个灯泡的最终状态。
数据范围
输入样例：
输出样例：
样例解释
灯泡状态如下：
1
2
3
4
5
6
7
| 时刻 T=0: 1 0 0 0 0
时刻 T=1: 1 1 0 0 0
时刻 T=2: 1 0 1 0 0
时刻 T=3: 1 1 1 1 0
时刻 T=4: 1 0 0 0 1
时刻 T=5: 0 1 0 0 1
时刻 T=6: 1 1 1 0 1
|
题解：
因为 $ B $ 很大，所以应该想到会出现循环。打表发现第一段非循环，后面的是一直循环的。因此需要求出第一个循环就行了。
看一下状态压缩，最多是 $ 16 $ 位，暗示需要进行 int 压缩。关键是这个操作，可以发现这个操作其实就是右移一位然后做异或运算。使用位运算模拟出来。
因此实际位置为 (b - st)%p + st。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
int vis[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
ll b;
cin >> n >> b;
int num = 0;
for (int i = 0, x; i < n; i++)
{
cin >> x;
num <<= 1;
num |= x;
}
int tot = 0;
for (int i = 1;; i++)
{
int tmp = (num & 1) << (n - 1) | (num >> 1);
num ^= tmp;
a[i] = num;
if (vis[num] == 0)
{
vis[num] = i;
}
else
{
tot = i - vis[num];
break;
}
}
int start = vis[num];
int index = b;
if (b > start)
{
index = (b - start) % tot + start;
}
for (int i = n - 1; i >= 0; i--)
{
cout << ((a[index] >> i) & 1) << endl;
}
return 0;
}
|