「CQOI2018」九连环

题目链接 [CQOI2018]九连环

题目背景

九连环是一种源于中国的传统智力游戏。如图所示,九个的圆环套在一把“剑”上,并且互相牵连。游戏的目标是把九个圆环全部从“剑”上卸下

img

题目描述

圆环的装卸需要遵守两个规则:

  1. 第一个(最右边) 环任何时候都可以任意装上或卸下
  2. 如果第 kk 个环没有被卸下,且第 kk 个环右边的所有环都被卸下,则第 k+1k+1 个环(第 kk 个环左边相邻的环) 可以任意装上或卸下

与魔方的千变万化不同,解九连环的最优策略是唯一的。为简单起见,我们以“四连环”为例,演示这一过程。这里用 11 表示环在“剑”上,00 表示环已经卸下。

初始状态为 1111 ,每步的操作如下:

  1. 1101 (根据规则2,卸下第 2 个环)
  2. 1100 (根据规则1,卸下第 1 个环)
  3. 0100 (根据规则2,卸下第 4 个环)
  4. 0101 (根据规则1,装上第 1 个环)
  5. 0111 (根据规则2,装上第 2 个环)
  6. 0110 (根据规则1,卸下第 1 个环)
  7. 0010 (根据规则2,卸下第 3 个环)
  8. 0011 (根据规则1,装上第 1 个环)
  9. 0001 (根据规则2,卸下第 2 个环)
  10. 0000 (根据规则1,卸下第 1 个环)

由此可见,卸下“四连环”至少需要 1010 步。随着环数增加,需要的步数也会随之增多。例如卸下九连环,就至少需要 341341 步。

请你计算,有 nn 个环的情况下,按照规则, 全部卸下至少需要多少步。

输入输出格式

输入格式

输入文件第一行,为一个整数 mm,表示测试点数目。

接下来 mm 行,每行一个整数 nn

输出格式

输出文件共m行,对应每个测试点的计算结果

输入输出样例

输入样例

1
2
3
4
3
3
5
9

输出样例

1
2
3
5
21
341

说明

对于 10%10\% 的数据,1n101\le n\le 10

对于 30%30\% 的数据,1n301\le n\le 30

对于 100%100\% 的数据,1n105,1m101\le n\le 10^5,1\le m\le 10

题解

水题水题

用爆搜简单的打一个表

n1234567
12510214285

会发现一个简单的式子

我们用 f[i] 表示 ii 连环最少需要的步数

1
2
3
4
5
6
7
f[1] = 1
for i = 2 to n
if i & 1 then do
f[i] = 2 * f[i - 1]
else do
f[i] = 2 * f[i - 1] + 1
end if

我们打一下这个的二进制:

n1234567
12510214285
1101011010101011010101010101

这样珂海星

但是我们看到了二进制表示也对题目没什么帮助(

我们将两个相邻的变量相加

n1+22 + 33 + 44 + 55 + 66 + 77 + 8
11111111111111111111111111111111111

所以说

fn+fn+1=2n+1fn+2fn+(!n&1)=2n+1fn=2n+13\begin{aligned}f_n+f_{n+1}&=2^{n+1}\\f_n+2f_n+(!n\&1)&=2^{n+1}\\f_n&=\lfloor\frac{2^{n+1}}{3} \rfloor\end{aligned}

接下来我们用快速幂就可以了= =









等等..取模呢QAQ

不取模会崩掉吧

高精会T死(

我们还是老老实实打个FFT吧(,不会的同学可以看看 「数学」FFT / DFT / IDFT学习笔记

代码:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
// Code From: https://www.cnblogs.com/RabbitHu/p/BZOJ5300.html
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#define enter putchar('\n')
#define space putchar(' ')
using namespace std;
typedef long long ll;
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op == 1) x = -x;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}

const int N = 150000;
const double PI = acos(-1);
int T, x;

struct cp {
double a, b;
cp(){}
cp(double x, double y): a(x), b(y){}
cp operator + (const cp &obj) const {
return cp(a + obj.a, b + obj.b);
}
cp operator - (const cp &obj) const {
return cp(a - obj.a, b - obj.b);
}
cp operator * (const cp &obj) const {
return cp(a * obj.a - b * obj.b, a * obj.b + b * obj.a);
}
} inv[N], omg[N];

void init(int n){
for(int i = 0; i < n; i++){
omg[i] = cp(cos(2 * PI / n * i), sin(2 * PI / n * i));
inv[i] = cp(omg[i].a, -omg[i].b);
}
}
void fft(cp *a, int n, cp *omg){
int lim = 0;
while((1 << lim) < n) lim++;
for(int i = 0; i < n; i++){
int t = 0;
for(int j = 0; j < lim; j++)
if(i >> j & 1) t |= 1 << (lim - j - 1);
if(i < t) swap(a[i], a[t]);
}
for(int l = 2; l <= n; l <<= 1){
int m = l / 2;
for(cp *p = a; p != a + n; p += l)
for(int i = 0; i < m; i++){
cp t = omg[n / l * i] * p[i + m];
p[i + m] = p[i] - t;
p[i] = p[i] + t;
}
}
}

struct big {
int g[N], len;
big(){
memset(g, 0, sizeof(g));
len = 1;
}
big(int x){
memset(g, 0, sizeof(g));
len = 0;
if(!x){
len = 1;
return;
}
while(x) g[len++] = x % 10, x /= 10;
}
void out(){
for(int i = len - 1; i >= 0; i--)
printf("%d", g[i]);
enter;
}
void operator /= (int x){
int sum = 0, newlen = 0;
for(int i = len - 1; i >= 0; i--){
sum = sum * 10 + g[i];
if(sum < x) g[i] = 0;
else{
if(!newlen) newlen = i + 1;
g[i] = sum / x;
sum %= x;
}
}
len = max(newlen, 1);
}
void operator *= (const big &b){
static cp A[N], B[N];
int newlen = len + b.len - 1, n = 1;
while(n < newlen) n <<= 1;
for(int i = 0; i < n; i++){
A[i] = cp(i < len ? g[i] : 0, 0);
B[i] = cp(i < b.len ? b.g[i] : 0, 0);
}
init(n);
fft(A, n, omg);
fft(B, n, omg);
for(int i = 0; i < n; i++)
A[i] = A[i] * B[i];
fft(A, n, inv);
for(int i = 0; i < newlen; i++)
g[i] = (int)floor(A[i].a / n + 0.5);
g[len = newlen] = 0;
for(int i = 0; i < len; i++)
g[i + 1] += g[i] / 10, g[i] %= 10;
if(g[len]) len++;
}
} ret, a;

int main(){

read(T);
while(T--){
read(x), x++;
ret = big(1), a = big(2);
while(x){
if(x & 1) ret *= a;
a *= a;
x >>= 1;
}
ret /= 3;
ret.out();
}

return 0;
}

然后就完了吗?

没有

窝之前好像在 「数学」FFT / DFT / IDFT学习笔记 的开头放了一段AC Code

每次,既然是高精,有是简单的式子为什么还要写FFT呢?Python大法好!

AC Code:

1
for i in range(int(input())) : print(pow(2, int(input()) + 1) // 3)
坚持原创技术分享,您的支持将鼓励我继续创作!