Content
- ZJU-ICPC Summer 2020 Contest 7 by Group A
-
- Problem B. Card Game
-
- Problem D. Cafeterias
-
- Problem E. Lifelong Learning
- ZJU-ICPC Summer 2020 Contest 8 by Group B
-
- Problem C. Thresholding
-
- Problem D. Mysterious Machine
-
- Problem E. Magic
-
- Problem F. Can you find B
- ZJU-ICPC Summer 2020 Contest 9 by Group C
-
- Problem A. An easy problem
-
- Problem B. Ball
-
- Problem F. FFT
ZJU-ICPC Summer 2020 Contest 7 by Group A
Problem B. Card Game
你正在与 (p(le 10^5))（包括自己）个人玩一个游戏，每个人手上有一张手牌，手牌上有数字 (b_1, b_2, cdots b_n(in[1, c(le 10^5)]))。牌堆大小为 (n)，其上的数字 (in[1, c])。每个人轮流将桌上的一张卡片换成自己手上的卡片，你是第一个操作的。如果最后的桌子上留下的卡片中 (h(in [1, c])) 是 唯一 的众数那么视为你成功。求有多少种可行的操作使你必胜，并输出必胜策略中交换的牌。
我们不妨从最坏情况考虑——每个人都不希望你赢，于是纷纷把你的牌 (h) 换掉。
因此我们令自己 最后操作。枚举一遍牌堆的牌并验证。维护全局众数可以直接线段树。
时间复杂度 (O(nlog c))。注意 (n = 1) 时特判，具体见代码。
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n, p, maxc, h;
int a[N], c[N];
#define mid ((l + r) >> 1)
int val[N << 2], cnt[N << 2];
void pushup(int x) {
val[x] = max(val[x << 1], val[x << 1 | 1]);
cnt[x] = 0;
if (val[x] == val[x << 1]) cnt[x] += cnt[x << 1];
if (val[x] == val[x << 1 | 1]) cnt[x] += cnt[x << 1 | 1];
}
void build(int l, int r, int* dat, int x = 1) {
if (l == r) { val[x] = dat[l], cnt[x] = 1; return; }
build(l, mid, dat, x << 1);
build(mid + 1, r, dat, x << 1 | 1);
pushup(x);
}
void update(int p, int v, int l = 1, int r = maxc, int x = 1) {
if (l == r) { val[x] += v; return; }
if (p <= mid) update(p, v, l, mid, x << 1);
else update(p, v, mid + 1, r, x << 1 | 1);
pushup(x);
}
signed main() {
ios::sync_with_stdio(false);
cin >> n >> p >> maxc >> h;
for (int i = 1; i <= n; i++)
cin >> a[i], c[a[i]]++;
if (n == 1) {
int t = 0;
for (int i = 1; i <= p; i++)
cin >> t;
if (t == h) printf("1
1");
else printf("0");
return 0;
}
int cur; cin >> cur;
for (int i = 2; i <= p; i++) {
int t; cin >> t;
--c[h], ++c[t];
}
build(1, maxc, c);
vector<int> ans;
for (int i = 1; i <= n; i++) {
update(a[i], -1);
--c[a[i]], ++c[cur];
update(cur, 1);
if (val[1] == c[h] && cnt[1] == 1)
ans.push_back(i);
update(a[i], 1);
++c[a[i]], --c[cur];
update(cur, -1);
}
cout << ans.size() << endl;
for (auto i : ans)
cout << i << ' ';
return 0;
}
Problem D. Cafeterias
给定一个 (n(le 10^5)) 个点， (m(le 2 imes 10^5)) 条边的无向图，并标有 (k(le n)) 个特殊点。现给定 (T(le 10^5)) 个询问，每次给出整数 (t(le 10^9))，求有多少点存在到达特殊点，长度为 (t-1) 的 不一定 简单的路径。
显然一跳路径可以通过“反复横跳”来加长路径：(1 o 3 o 4) 可以变为 (1 o 3 o 4 o 3 o 4)。而且一次增加 (2)。
于是求出两种最短路——长度分别为奇数和偶数时的最短路径长。求出最短路可以通过“反复横跳”来构造出新的路径。由于图不带边权，于是直接 Bfs。
然后将所有最短距离排序（无法到达记为无限大）。
对于询问的 (t)，我们先判断其奇偶性，再在最短路长数组上二分即可。
时间复杂度 (O(nlog n))。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Article : ZJU Summer Training 2020
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n, m, k, T;
bool spec[N];
vector<int> G[N];
long long dist[2][N];
struct queNode { int pos; long long dis; };
void solve() {
queue<queNode> que;
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i++)
if (spec[i]) que.push(queNode{i, 0});
while (!que.empty()) {
queNode x = que.front();
que.pop();
if (dist[x.dis & 1][x.pos] <= x.dis)
continue;
dist[x.dis & 1][x.pos] = x.dis;
for (auto y : G[x.pos])
que.push(queNode{y, x.dis + 1});
}
}
vector<long long> res[2];
signed main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; i++) {
int p; scanf("%d", &p);
spec[p] = true;
}
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (G[i].size() == 0) spec[i] = false;
solve();
res[0] = vector<long long>(dist[0] + 1, dist[0] + 1 + n);
res[1] = vector<long long>(dist[1] + 1, dist[1] + 1 + n);
sort(res[0].begin(), res[0].end());
sort(res[1].begin(), res[1].end());
scanf("%d", &T);
while (T--) {
long long t;
scanf("%lld", &t), --t;
if (t == 0) printf("%d
", k);
else printf("%d
", int(upper_bound(res[t & 1].begin(), res[t & 1].end(), t) - res[t & 1].begin()));
}
}
Problem E. Lifelong Learning
给定一个长为 (n(le 10^6)) 的数列 ({a_1, a_2, cdots, a_n}(a_i le 10^6))。每次操作可以改变数列中的一个元素的值。求最少的操作次数，使最终的数列满足：前半部分满足 (a_i + 1 = a_{i + 1})，后半部分满足 (a_i - 1 = a_{i + 1})。若 (n) 为偶数则 (a_{frac n 2} = a_{frac n 2+1}) 。
我们先将每一个数，以中间数 ( ext{mid} = lfloor dfrac{n+1}{2} floor) 为基准，对于每一个位置 (i)，进行操作 (a_i leftarrow a_i + |i - ext{mid}|)。
接下来我们在操作后的 (a) 数列上贪心地取众数，记众数的出现次数为 (k)。显然这样可以最大化不改的数的个数。
答案即为 (n - k)。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
int n, a[N];
int buc[N << 1];
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
int mid = (n + 1) / 2;
for (int i = 1; i < mid; i++)
a[i] += mid - i;
if (!(n & 1)) ++mid;
for (int i = mid + 1; i <= n; i++)
a[i] += i - mid;
for (int i = 1; i <= n; i++)
buc[a[i]]++;
int mode = *max_element(buc + 1, buc + (N << 1));
printf("%d
", n - mode);
return 0;
}
ZJU-ICPC Summer 2020 Contest 8 by Group B
Problem C. Thresholding
给定一个 (w(le 640) imes h(le 640)) 的矩阵，矩阵中的元素为整数且 (in [0, 2^{16}))。你可以设一个间值 (k)，将矩阵中所有 (le k) 的元素归入集合 (0)，其他的归入集合 (1)。设集合 (S) 占总数大小的比例为 (omega_S)，集合 (S) 的方差为 (sigma_S^2)。求 (sigma_w^2 = omega_0sigma_0^2 + omega_1sigma_1^2) 的最小值。
注意到本题中的“矩阵”是假象，实质上就是一堆数字。
于是显然可以枚举数字的分布情况，这可以通过排序完成。枚举时需要动态维护左右两部分的方差，可以使用公式 (sigma = sum x^2 - (sum x)^2)。预处理一个前缀和以及前缀
但理论上不能直接扫，因为我们不能让两个相同的元素在不同的集合里，于是这里要特判。然而好像不判也过了。
复杂度 (O(whlog (wh)))。直接三分应该也行。
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 640 * 640 + 5;
inline double sqr(double x) {
return x * x;
}
double val[N], s[N], ss[N];
int w, h, n;
inline double getvar(int l, int r) {
if (l > r) return 0;
return (ss[r] - ss[l - 1]) / (r - l + 1) - sqr((s[r] - s[l - 1]) / (r - l + 1));
}
signed main() {
scanf("%d%d", &w, &h), n = w * h;
for (int t, i = 1; i <= n; i++)
scanf("%d", &t), val[i] = t;
sort(val + 1, val + 1 + n);
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + val[i], ss[i] = ss[i - 1] + sqr(val[i]);
double ans = getvar(1, n);
for (int i = 1; i < n; i++)
if (val[i] != val[i + 1])
ans = min(ans, getvar(1, i) * (i * 1.0 / n) + getvar(i + 1, n) * ((n - i) * 1.0 / n));
printf("%.10f
", ans);
return 0;
}
Problem D. Mysterious Machine
给定三个正整数 (x, y, z(le 5 imes 10^3))。构造三个 01 串 (A, B, C)，满足 ( ext{LCS}(A, B) = x, ext{LCS}(B, C) = y, ext{LCS}(A, C) = z)。其中 ( ext{LCS}(S, T)) 表示字符串 (S, T) 的最长公共子序列长度。构造出的长度不超过 (10^4)。
构造题。我们钦定 (x le y le z)，那么我们先将在字符串 (A) 中填充 (z) 个 ( exttt 1)，在 (B) 中填充 (x) 个 ( exttt 1)。这样保证了 ( ext{LCS}(A, B) = x)。
然后再向 (B) 后面添加 (y - x) 个 ( exttt 0)，最后在 (C) 中加 (5000) 个 ( exttt 1)，(5000) 个 ( exttt 0)。这样显然满足题意，因为我们可以近似的认为 ( ext{LCS}(B, C) = |B| = y, ext{LCS}(A, C) = |A| = z)。
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e4 + 5;
char str[3][N];
int x, y, z, a, b, c;
signed main() {
cin >> x >> y >> z;
a = 0, b = 1, c = 2;
if (x > z) swap(x, z), swap(b, c);
if (x > y) swap(x, y), swap(a, c);
if (y > z) swap(y, z), swap(b, a);
fill(str[a] + 1, str[a] + 1 + z, '1');
fill(str[b] + 1, str[b] + 1 + x, '1');
fill(str[b] + x + 1, str[b] + y + 1, '0');
fill(str[c] + 1, str[c] + 5000 + 1, '1');
fill(str[c] + 5001, str[c] + 10000 + 1, '0');
cout << (str[0] + 1) << endl;
cout << (str[1] + 1) << endl;
cout << (str[2] + 1) << endl;
return 0;
}
Problem E. Magic
给定 (n(le 20)) 个字符串 (S_1, S_2, cdots , S_n(sum|S_i| le 10^5))，任意排列这些字符串并拼接，可以计算出得到的新串的 本质不同 的子序列的个数，空串也算。求有多少种排列的方式，使得得到的新串的本质不同的子序列的个数为偶数。字符集 (Sigma) 为全体小写英文字母。
若只计算单串 (S) 的本质不同的子序列的个数，我们可以设计一个动态规划算法：设 (f(i, c)) 为子串 (S[1, i]) 以字符 (c) 结尾的本质不同的子序列的个数，且令 (s(i) = sumlimits_{cin Sigma} f(i, c))，即当前的答案。那么有状态转移方程：
由于本题只与奇偶性有关，我们不妨对 (2) 取模：
这相当于 (f) 与 (s) 之间的 交换。
我们注意以下初始状态：(f = 0)，只有 (s(0) = 1)（空串也算），而上式只存在交换，因此不难断定 为 1 的字符位置只有一个。
那么我们只需抓住这个位置即可。我们使用上述思想预处理出 (t)（代码中为 (f) 数组） —— (t(S, c)) 表示 1 的位置为 (c) 开始，“通过”在字符串 (S) 后 1 的位置。
根据这个 1 的位置，我们再考虑一种 dp：设 (g(S, c)) 表示，字符串集合（编号） (S) 中的字符串任意拼接，当 1 的位置为字符 (c) 时，存在几种满足题意的方案。
那么对于每一个状态 (g(S, c))，有：
显然需要满足条件 (i ot in S)。
状态压缩一下，可以有 (O(2^n imes n|Sigma|))。
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 21;
const int S = 26;
const int L = 1e5 + 5;
int n;
char str[L];
int f[N][S + 1];
long long g[1 << N][S + 1];
signed main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", str + 1);
int l = strlen(str + 1);
for (int j = 0; j <= S; j++) {
f[i][j] = j;
for (int p = 1; p <= l; p++)
if (f[i][j] && str[p] - 'a' + 1 == f[i][j]) f[i][j] = 0;
else if (!f[i][j]) f[i][j] = str[p] - 'a' + 1;
}
}
g[0][0] = 1;
for (int i = 0; i < (1 << n); i++)
for (int k = 0; k < n; k++)
if (!(i & (1 << k)))
for (int j = 0; j <= S; j++)
g[i | (1 << k)][f[k][j]] += g[i][j];
long long ans = 0;
for (int i = 1; i <= S; i++)
ans += g[(1 << n) - 1][i];
printf("%lld
", ans);
return 0;
}
F. Can you find B
给定长度为 (n(le 100)) 的数列 ({a_1, a_2, cdots , a_n}(a_i le 50))。试构造出数列 ({b}) ，使 (sumlimits_{i = 1} ^n |a_i - b_i|) 最小且 ({b}) 中的任意两个元素 (a, b) 满足 (gcd(x, y) = 1)。求出这个最小值。
(gcd = 1) 的条件是比较苛刻的，这导致了 ({b}) 中会存在大量的 (1)。
又因为 (a_i le 50)，所以 (b_i le 100)，原因是选择超过 (100) 的数显然不如直接选 (1)。
于是我们有这样一个 dp：设 (f(i, S)) 表示对于 (a) 的前 (i) 个数，选定数的 质因子 集合为 (S)，得到 (a, b) 的最小总差值。
那么有转移方程：
然而直接状压计算量高达 (2^{25} cdot 100 cdot n)，原地爆炸。因为 ([1, 100]) 内的质数有 (25) 个。
我们又发现一个性质：对于一个 (>50) 的质数，我们只可能选择其本身而非其倍数。原因见上，显然。
于是我们只枚举 (50) 以内的质数即可——范围缩小至 (15) 个。对于 (a) 数列，我们贪心地将其从小到大排序，小的对应小的。
我们计算答案时，我们取 左半部分的 dp，右半部分的较大质数。
dp 仍然是那个 dp，复杂的直降至 (O(2^p imes n imes max {a}))，其中 (p = 15)。
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 100;
const int P = 25; // <= 100
const int T = 15; // <= 50
const int prime[P + 5] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97
};
int ds[N + 5]; // set of prime divisions
int n, a[N + 5];
int f[N + 5][1 << T];
void dynamicPrograming() {
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int S = 0; S < (1 << T); S++) {
f[i][S] = min(f[i][S], f[i - 1][S] + a[i] - 1);
for (int j = 2; j <= N; j++) {
if (ds[j] == -1 || (S & ds[j])) continue;
int R = S | ds[j];
f[i][R] = min(f[i][R], f[i - 1][S] + abs(j - a[i]));
}
}
}
signed main() {
ios::sync_with_stdio(false);
for (int i = 2; i <= N; i++)
for (int j = 0; j < T; j++)
if (i % prime[j] == 0)
ds[i] |= (1 << j);
for (int i = T; i < P; i++)
ds[prime[i]] = -1;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
dynamicPrograming();
int ans = inf;
for (int i = n; i && n - i <= 9; --i) {
int cur = inf;
cur = min(cur, *min_element(f[i], f[i] + (1 << T)));
for (int j = i + 1; j <= n; j++)
cur += abs(a[j] - prime[T + j - i - 1]);
ans = min(ans, cur);
}
cout << ans << endl;
return 0;
}
ZJU-ICPC Summer 2020 Contest 9 by Group C
Problem A. An easy problem
给定 (n(le 10)) 个互不相同数字 ((in[0, 9]))。选择若干个数字拼接成整数 (a)，剩下拼成整数 (b)，拼成的数不应含前导零。求 (min |a - b|)。
真·签到。(n) 很小，可以暴力枚举 next_permutation。
但是有一个技巧——要最小化差值，一定是从中间分割数列。
一个小优化：(n=10) 时答案固定，直接输出。
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
using namespace std;
const int N = 10;
int T, n;
int a[N];
void solve() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
if (n == 10) {
cout << 247 << endl;
return;
}
int ans = INT_MAX;
sort(a, a + n);
do {
int left = 0, right = 0;
int mid = n / 2;
if ((a[0] == 0 || a[mid] == 0) && n >= 3)
continue;
for (int i = 0; i < mid; i++)
left = left * 10 + a[i];
for (int i = mid; i < n; i++)
right = right * 10 + a[i];
ans = min(ans, abs(left - right));
} while(next_permutation(a, a + n));
cout << ans << endl;
}
signed main() {
for (cin >> T; T; --T) solve();
return 0;
}
Problem B. Ball
给定两个球体，坐标大小，半径 (le 10^2)，求两个球体的体积并。
计算几何，分类讨论。
- 不相交，答案为 (V_1 + V_2)。
- 包含，答案为 (max(V_1, V_2))。
- 否则，答案为 ((V_1 + V_2) - (r_1 + r_2 - d)^2pi imes (d^2 + 2d(r_1 + r_2) - 3(r_1^2 + r_2^2) + 6r_1r_2)/(12d))，其中 (r_1, r_2) 为两圆半径，(d) 为两圆心距离。
#include <cmath>
#include <cstdio>
#include <iostream>
#include <tuple>
using namespace std;
const double pi = acos(-1);
const double eps = 1e-10;
typedef tuple<double, double, double> Point;
double sqr(double x) {
return x * x;
}
double dist(Point& A, Point& B) {
return sqrt(sqr(get<0>(A) - get<0>(B))
+ sqr(get<1>(A) - get<1>(B))
+ sqr(get<2>(A) - get<2>(B)));
}
double volume(double r) {
return pi * pow(r, 3) * 4.0 / 3.0;
}
bool included(Point& A, double r1, Point& B, double r2) {
return dist(A, B) + min(r1, r2) < max(r1, r2);
}
double intersection(Point& A, double r1, Point& B, double r2) {
double d = dist(A, B);
return pi * sqr(r1 + r2 - d)
* (sqr(d) + d * 2 * (r1 + r2) - 3 * (sqr(r1) + sqr(r2)) + 6 * r1 * r2) / (12 * d);
}
signed main() {
Point A, B;
double r1, r2;
cin >> get<0>(A) >> get<1>(A) >> get<2>(A) >> r1;
cin >> get<0>(B) >> get<1>(B) >> get<2>(B) >> r2;
if (r1 + r2 - dist(A, B) < eps) {
printf("%.10f
", volume(r1) + volume(r2));
return 0;
}
if (included(A, r1, B, r2)) {
printf("%.10f
", max(volume(r1), volume(r2)));
return 0;
}
double ans = volume(r1) + volume(r2) - intersection(A, r1, B, r2);
printf("%.10f
", ans);
return 0;
}
Problem F. FFT
给定 (n(le 10^2)) 个（有标号的）点，你可以在其间任意连边使之成为连通图。现在限定只允许连 (m) 条边，试问连成连通图的方案数。你需要根据所有的 (m in [0, frac{n(n - 1)}{2}]) 输出答案。
本题实质上是 限定边数有标号连通图计数 问题。
以下用 (c(x)) 表示 (frac{x(x - 1)}{2})。
考虑一种 dp：设 (F(m, k)) 为通过 (m) 条边连出 (k) 个连通块的方案数，(G(m, k)) 表示通过 (m) 条边，连成 (k) 个“假块”（人为划分的块，块间可能有连边）的方案数。
那么我们可以用 (F) 来表示 (G)：
我们可以选择个数大于等于 (k) 的块数进行“合并”，其中 (egin{Bmatrix} j \ k end{Bmatrix}) 表示 (j) 个连通块并入 (k) 个“假块”的方案数，即 第二类斯特林数。
但如果要反过来用 (G) 表示 (F) 呢？于是我们使用 斯特林反演 点击学习
方案数那么答案就是当 (k = 1) 时，代入得 (sumlimits_{j=1}^n G(m, j)(j-1)!(-1)^{j-1}) 即为所求。
但我们发现这个直接求居然比暴力 (O(n^6)) 还慢。于是我们把这个 (G) 拆成 (H)——(H(i, j, m)) 表示选取 (i) 个点，构成 (j) 个块（仍然是“假块”），余下可用的边数（注意这里定义反转了，不过这样好写）为 (m) 的方案数。有关系：
这个组合数表示在剩余的 (k) 条边中选出 (m) 条的方案数。
但我们又发现直接求 (H) 仍然爆炸，于是我们把 块数那一维缩掉，只保留两维。
如何加入系数 ((j-1)!(-1)^{j-1}) 的影响？只要在转移时乘上 (-1) 即可。
组合数系数的含义详见代码。
#include <iostream>
using namespace std;
const int N = 105;
const int mod = 998244353;
typedef long long LL;
int n;
LL fact[N * N];
LL invf[N * N];
LL f[N][N * N]; /* 上文的 H */
LL g[N]; /* 答案 */
inline int calc(int x) { /* 上文中的 c(x) */
return x * (x - 1) / 2;
}
LL fp(LL a, LL b, LL c) { /* 快速幂 */
if (!b) return 1ll;
LL t = fp(a, b / 2, c);
return t * t % c * ((b & 1) ? a : 1) % c;
}
LL C(int n, int m) { /* 求组合数 */
return fact[n] * invf[n - m] % mod * invf[m] % mod;
}
signed main() {
cin >> n;
fact[0] = 1ll;
for (int i = 1; i <= calc(n); i++)
fact[i] = fact[i - 1] * i % mod;
invf[calc(n)] = fp(fact[calc(n)], mod - 2, mod);
for (int i = calc(n) - 1; ~i; i--)
invf[i] = invf[i + 1] * (i + 1) % mod;
/* 预处理组合数 */
for (int i = 1; i <= n; i++)
f[i][calc(i)] = 1ll;
/* dp 初始化，此处 f 即为 H */
for (int i = 1; i <= n; i++)
for (int j = calc(i); ~j; --j)
for (int k = 1; k + i <= n; k++)
f[i + k][j + calc(k)] = (f[i + k][j + calc(k)] - f[i][j] * C(i + k - 1, k) % mod + mod) % mod;
/*
dp 处理 H：先顺序枚举点数，倒叙枚举边数，然后枚举新块的大小并合并到这 i 个点中。
注意乘上 -1，记得取模。
C(i + k - 1, k) 指合并后的 (i + k - 1) 个点中选出 k 个为“新加的”。
*/
for (int i = 0; i <= calc(n); i++)
for (int j = i; j <= calc(n); j++)
g[i] = (g[i] + f[n][j] * C(j, i) % mod) % mod;
/*
统计答案：系数 C(j, i) 表示剩余的 j 条边中选出 i 条。
记得取模。
*/
for (int i = 0; i <= calc(n); i++)
cout << g[i] << endl;
return 0;
}