洛谷P1990 覆盖墙壁
题目描述
你有一个长为 \(N\) 宽为 \(2\) 的墙壁，给你两种砖头：一个长 \(2\) 宽 \(1\)，另一个是 L 型覆盖 \(3\) 个单元的砖头。如下图：
0 0
0 00
砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖 \(N\times 2\) 的墙壁的覆盖方法。例如一个 \(2\times3\) 的墙可以有 \(5\) 种覆盖方法，如下：
012 002 011 001 011
012 112 022 011 001
注意可以使用两种砖头混合起来覆盖，如 \(2\times4\) 的墙可以这样覆盖：
0112
0012
给定 \(N\)，要求计算 \(2\times N\) 的墙壁的覆盖方法。由于结果很大，所以只要求输出最后 \(4\) 位。例如 \(2\times 13\) 的覆盖方法为 \(13465\)，只需输出 \(3465\) 即可。如果答案少于 \(4\) 位，就直接输出就可以，不用加前导 \(0\)，如 \(N=3\) 时输出 \(5\)。
输入格式
一个整数 \(N\)，表示墙壁的长。
输出格式
输出覆盖方法的最后 \(4\) 位，如果不足 \(4\) 位就输出整个答案。
样例 #1
输入样例 #1
13
输出样例 #1
3465
提示
数据保证，\(1\leq N\leq 1000000\)。
解题思路
解题方法来自 info___tion。
假设 \(f_n\) 表示前 \(n\) 列被铺满的方案数，则
-
当前 \(n-1\) 列被铺满，铺满前 \(n\) 列方案数为 \(f_{n-1}\)，这时只能放置竖立的砖头；
-
当前 \(n-2\) 列被铺满，铺满前 \(n\) 列方案数为 \(f_{n-2}\)，这时只能放置横着的砖头；倘若放置竖立的砖头，则和上一个重复；
-
假设 \(g_n\) 表示前 \((n+1)\) 列被铺满的，但目前第 \((n+1)\) 列未被铺满的方案数，则有两种情况，一种是该列上面缺失，另一种是该列下面缺失，则铺满前 \(n\) 列有 \(2 * g_{n-2}\)；
- 维护 \(g_n\)，要么是后面补了一个横着的砖头，要么是补了一个 \(L\) 型砖头，因此 \(g_n=g_{n-1}+f_{n-1}\)。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010, M = 10000;
typedef long long LL;
int n;
int f[N], g[N];
int main() {
cin >> n;
f[0] = 1, g[0] = 0, f[1] = g[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = ((f[i - 1] + f[i - 2]) % M + 2 * g[i - 2] % M) % M;
g[i] = (g[i - 1] + f[i - 1]) % M;
}
cout << f[n];
return 0;
}
洛谷P3612 [USACO17JAN] Secret Cow Code S
题面翻译
奶牛正在试验秘密代码，并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。
给定一个字符串，对字符串进行一次操作（每一次正确的操作，最后一个字符都会成为新的第一个字符），然后把操作后的字符串放到操作前的字符串的后面。也就是说，给定一个初始字符串，之后的每一步都会增加当前字符串的长度。
给定初始字符串和 \(N\)，请帮助奶牛计算无限字符串中位置为 \(N\) 的字符。
第一行输入一个字符串。该字符串包含最多 \(30\) 个大写字母，数据保证 \(N \leq 10^{18}\)。
第二行输入 一个整数 \(N\)。请注意，数据可能很大，放进一个标准的 \(32\) 位整数容器可能不够，所以你可能要使用一个 \(64\) 位的整数容器（例如，在 C/C++ 中是 long long）。
请输出从初始字符串生成的无限字符串中的下标为 \(N\) 的字符。第一个字符的下标是 \(N=1\)。
感谢 @y_z_h 的翻译
题目描述
The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.
Given a string \(s\), let \(F(s)\) be \(s\) followed by \(s\) "rotated" one character to the right (in a right rotation, the last character of \(s\) rotates around and becomes the new first character). Given an initial string \(s\), the cows build their infinite-length code string by repeatedly applying \(F\); each step therefore doubles the length of the current string.
Given the initial string and an index \(N\), please help the cows compute the character at the \(N\)th position within the infinite code string.
输入格式
The input consists of a single line containing a string followed by \(N\). The string consists of at most 30 uppercase characters, and \(N \leq 10^{18}\).
Note that \(N\) may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a "long long" in C/C++).
输出格式
Please output the \(N\)th character of the infinite code built from the initial string. The first character is \(N=1\).
样例 #1
样例输入 #1
COW 8
样例输出 #1
C
提示
In this example, the initial string COW expands as follows:
COW -> COWWCO -> COWWCOOCOWWC
解题思路
分治。
对于一个长度为 \(2n\) 的字符串 \(S\)，可知 \(S_n=S_{n+1}\)，\(S_i=S_{i+n+1}\ (1\le i \le n-1)\)，因此根据此可以将大问题划分为小问题。
-
如果 \(t\) 位于 \(n+1\)，则相当于求解 \(t-1\) 处的字符；
-
如果 \(t\) 位于 \([n+2,2n]\)，则求解 \(t-(n+1)\) 的字符，而 \(n=S.length * 2^{x}\)。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 10000;
typedef long long LL;
string S;
LL n, length;
void dfs(LL n) {
if (n <= length) {
cout << S[n - 1];
return;
}
LL i = length;
while ((i << 1) < n) i <<= 1;
n -= (i + 1);
if (n == 0) n = i;
dfs(n);
}
int main() {
cin >> S >> n;
length = S.size();
dfs(n);
return 0;
}