250716 模拟赛
有一排 \(n\) 个空位，每个位置可以放一个物品或者不放，要求不能连续放 \(c\) 个物品，问方案数。
\(n\le 10^{18},\ c\le 500\)
用 DP 容易做到 \(O(n)\)，并且可以用矩阵快速幂优化到 \(O(c^3\log n)\)，不能通过。
注意到 \(c\) 很小，但 \(n\) 很大，考虑另一些枚举 \(c\) 并且包含 \(\log n\) 的做法。我们将当前长为 \(n\) 的问题劈成两半 \(L,R\)（\(L+R=n\)），然后处理分割线附近的情况。我们可以枚举分割线左、右两侧分别有连续多少个物品，记为 \(i,j\)，它们需要满足 \(i+j\le c\)。\(L,R\) 分别去掉 \(i+1\) 和 \(j+1\) 之后剩下的部分变为子问题递归处理。
考虑这样做的时间复杂度。生成的 \(O(c)\) 个子问题 \(n'\) 都满足 \(n'\in [\frac 12 n-c,\frac 12 n]\)（分析时间复杂度时不细扣边界）；下一层递归之后生成的子问题 \(n''\) 都满足 \(n''\in [\frac 12 n'-c,\frac 12 n']=[\frac 14 n-\frac 32 c,\frac 14 n]\)；注意到区间长度始终不会超过 \(2c\)，同时最多 \(\log n\) 层，因此本质不同子问题数量为 \(O(c\log n)\) 级别。
由于转移时还需要枚举 \(c\)（这里不要暴力枚举 \((i,j)\)，使用前缀和优化即可），因此总时间复杂度为 \(O(c^2\log n)\)。再将 \(n\le 10^6\) 直接预处理出来，可以更快（约 \(\frac 13\)）。
代码
| #include<iostream>
#include<unordered_map>
#include<cstring>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
inline void add(int &a, int b) { a = (a + b) % MOD; }
ll n;
int c;
struct hash_table {
static const int MOD = 1e7 + 19;
struct Node {
ll key;
int v, next;
} pool[64 * 510 * 510];
int nn, head[MOD];
inline hash_table() : nn(0) { memset(head, 0, sizeof(head)); }
int &insert(ll key) {
pool[++nn] = {key, 0, head[key % MOD]};
head[key % MOD] = nn;
return pool[nn].v;
}
int &operator[](ll key) {
for(int i = head[key % MOD]; i; i = pool[i].next) {
if(pool[i].key == key) return pool[i].v;
}
return insert(key);
}
} mp;
namespace baoli {
const int N = 1e6 + 10;
int f[N];
void work(int tp = 1, int _n = n) {
int s = 1;
f[-1 + 2] = 1;
f[0 + 2] = 1;
for(int i = 1; i <= _n; i++) {
if(i - c - 2 >= -1) s = (s - f[i - c - 2 + 2] + MOD) % MOD;
s = (s + f[i - 1 + 2]) % MOD;
f[i + 2] = s;
}
if(tp) cout << f[_n + 2] << '\n';
}
}
namespace c2logv {
using baoli::f;
int dfs(ll n) {
if(n < -1) return 0;
if(n <= 0) return 1;
if(n <= 1) return 2;
if(n <= 1000000) return f[n];
int &res = mp[n];
if(res) return res;
ll l = n / 2, r = n - l;
int sum = 0;
for(int i = c; i >= 0; i--) {
add(sum, dfs(r - (c - i) - 1));
add(res, (ll)sum * dfs(l - i - 1) % MOD);
}
return res;
}
void work() {
if(c == 0) { cout << 1 << '\n'; return; }
baoli::work(0, 1000000);
for(int i = 1; i <= 1000000; i++) f[i] = f[i + 2];
cout << dfs(n) << '\n';
}
}
// #define FIO
signed main() {
#ifdef FIO
freopen("nuclear.in", "r", stdin);
freopen("nuclear.out", "w", stdout);
#endif
cin >> n >> c;
// 原题还需要数据点分治
if(n <= 1000000) baoli::work();
else c2logv::work();
return 0;
}
|
有 \(n\) 个物品，A 和 B 轮流取物品，A 先手。每个人每回合至少取一个物品，至多取上一个人上一次取物品数的两倍。将最后一个物品拿走的人获胜。A 在第一回合可以取任意物品。问 A 第一回合至少取多少物品可以胜利（假设 A,B 足够聪明）。
\(n\le 10{18}\)
先考虑暴力，设 \(f[i][j]\) 表示还剩 \(i\) 个物品，上一次拿了 \(j\) 个物品，是否先手必胜。容易做到 \(O(n^2)\)。
暴力
| #include<iostream>
using namespace std;
const int N = 10010;
int n;
bool f[N][N];
int main() {
cin >> n;
if(n > 10010) return 0;
for(int i = 1; i <= n; i++) f[1][i] = 1;
for(int i = 2; i <= n; i++) {
bool tmp = 0;
for(int j = 1; j <= n; j++) {
if(2 * j - 1 <= i) tmp = tmp || !f[i - (2 * j - 1)][2 * j - 1];
if(2 * j <= i) tmp = tmp || !f[i - (2 * j)][2 * j];
f[i][j] = tmp;
}
}
for(int i = 1; i <= n; i++) {
if(!f[n - i][i]) { cout << i << '\n'; break; }
}
return 0;
}
|
然后打出 \(n\in[1,100]\) 的表：
for n in {1..100}
do
echo -e "$n \c"
echo $n | ./a
done
表
1 1
2 2
3 3
4 1
5 5
6 1
7 2
8 8
9 1
10 2
11 3
12 1
13 13
14 1
15 2
16 3
17 1
18 5
19 1
20 2
21 21
22 1
23 2
24 3
25 1
26 5
27 1
28 2
29 8
30 1
31 2
32 3
33 1
34 34
35 1
36 2
37 3
38 1
39 5
40 1
41 2
42 8
43 1
44 2
45 3
46 1
47 13
48 1
49 2
50 3
51 1
52 5
53 1
54 2
55 55
56 1
57 2
58 3
59 1
60 5
61 1
62 2
63 8
64 1
65 2
66 3
67 1
68 13
69 1
70 2
71 3
72 1
73 5
74 1
75 2
76 21
77 1
78 2
79 3
80 1
81 5
82 1
83 2
84 8
85 1
86 2
87 3
88 1
89 89
90 1
91 2
92 3
93 1
94 5
95 1
96 2
97 8
98 1
99 2
100 3
发现当 \(n\) 是斐波那契数的时候，其答案是其本身；其余情况，答案也都是斐波那契数。猜测跟斐波那契数有关
发现两个斐波那契数中间的答案和开头的答案完全相同，不难想到是删除了比 \(n\) 小的最大的斐波那契数，直到 \(n\) 是斐波那契数。
代码
| // 比暴力还短
#include<iostream>
#define ll long long
using namespace std;
ll n, m;
ll fib[100];
// #define FIO
int main() {
#ifdef FIO
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
#endif
cin >> n;
fib[0] = fib[1] = 1;
for(int i = 2; i <= 100; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
if(fib[i] > n) { m = i; break; }
}
for(int i = m; i >= 0; i--) {
if(n == fib[i]) {
cout << n << '\n';
break;
} else if(n > fib[i]) {
n -= fib[i];
}
}
return 0;
}
|