2022 gdcpc题解(10/13)
2022gdcpc
和学弟vp了一下这场，本来抓的数学选手咕咕了，只有2个人，打下来的感觉就是套路题和码量太大了，太久没写码量题导致 I I I调太久了，最后G没写完，K也没冲出来，感觉数学大爹在的话这K应该随便秒。
A.拼图
置换相关，数学爹不在不会
B.FFT
题解
考虑组合意义，其实就是输出n的排列
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
int fc = 1;
for (int i = 1; i <= n; i++)
fc = 1ll * fc * (i) % 998244353;
cout << fc << endl;
}
C.魔法师
不会，待补
D.剪纸
不难发现答案就是斐波那契数列，这题cf上个月好像才出了个类似的。注意 n = 2 n = 2 n=2特判
#include <bits/stdc++.h>
using namespace std;
long long n, f[1000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
f[0] = f[1] = 1;
for (int i = 2; i <= 100; i++) {
f[i] = f[i - 1] + f[i - 2];
}
int j = 0;
if (n == 2) {
cout << "1 1\n";
} else {
while (f[j + 2] <= n) j++;
cout << f[j] << " " << f[j + 1] << endl;
}
}
E.黑白大陆
考虑一种特殊情况，即对黑白格子两两染色，我们发现这不仅是个二分图，还是个分层图，所以考虑将同色块缩点，相邻不同色块的点进行连边，也是个分层图，从分层图上某个颜色到相邻点的代价即等价于一次魔法的代价。所以枚举每个点，最小值即是以该点为起点的任意点为终点的最短路的最大值，注意到达某点的时候，
假如该点颜色为黑色，需要再用一次魔法
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int maxn = 2500 + 11;
int n, m, G[60][60], vis[60][60], sid[60][60], idcnt, col[maxn];
vector<unordered_set<int>> e;
void bfs(int i, int j, int c) {
queue<pair<int, int>> q;
q.push({i, j}), vis[i][j] = 1, sid[i][j] = idcnt;
while (q.size()) {
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int tx = dx[d] + x, ty = dy[d] + y;
if (tx <= 0 || ty <= 0 || tx > n || ty > m || vis[tx][ty] ||
G[tx][ty] != c)
continue;
q.push({tx, ty}), vis[tx][ty] = 1, sid[tx][ty] = idcnt;
}
}
}
struct Node {
int d, x;
bool operator<(const Node& rhs) const { return d > rhs.d; }
};
int dis[maxn];
int dijkstra(int s) {
for (int i = 0; i <= idcnt; i++) dis[i] = 1e9;
priority_queue<Node> q;
q.push({dis[s] = 0, s});
int mxdis = 0, mxcol = col[s];
while (q.size()) {
auto [dd, x] = q.top();
q.pop();
if (dd != dis[x]) continue;
if (dis[x] > mxdis) {
mxdis = dis[x], mxcol = col[x];
}
for (int v : e[x]) {
if (dis[v] > dis[x] + 1) {
dis[v] = dis[x] + 1;
q.push({dis[v], v});
}
}
}
return mxdis + mxcol;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> G[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!vis[i][j]) ++idcnt, col[idcnt] = G[i][j], bfs(i, j, G[i][j]);
e.assign(idcnt + 11, {});
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (sid[i][j] != sid[i - 1][j]) {
e[sid[i - 1][j]].insert(sid[i][j]);
e[sid[i][j]].insert(sid[i - 1][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= m; j++) {
if (sid[i][j] != sid[i][j - 1]) {
e[sid[i][j - 1]].insert(sid[i][j]);
e[sid[i][j]].insert(sid[i][j - 1]);
}
}
}
int ans = 1e9;
for (int i = 1; i <= idcnt; i++) ans = min(ans, dijkstra(i));
cout << ans << endl;
}
F.望舒客栈的每日委托
队友写的，用set模拟即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 11;
int n, table_sz[maxn];
set<int> st[5];
struct Event {
int Time, table, x, a, d, t;
bool operator<(const Event& rhs) const { return Time > rhs.Time; }
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
priority_queue<Event> q;
for (int i = 1, x, a, d, t; i <= n; i++) {
cin >> x >> a >> d >> t;
q.push({a, -1, x, a, d, t});
}
int ans = 0;
while (q.size()) {
auto it = q.top();
q.pop();
if (it.table == -1) {
int mnid = -1, sz = -1;
if (it.t) {
for (int i = it.x; i <= 4; i++) {
if (st[i].size()) {
if (mnid == -1 || mnid > *st[i].begin())
mnid = *st[i].begin(), sz = i;
}
}
} else {
if (st[4].size()) mnid = *st[4].begin(), sz = 4;
}
if (mnid == -1) {
mnid = ++ans, sz = 4;
st[4].insert(ans);
table_sz[ans] = 4;
}
st[sz].erase(mnid);
st[sz - it.x].insert(mnid);
table_sz[mnid] = sz - it.x;
q.push({it.d, mnid, it.x, it.a, it.d, it.t});
} else {
int mnid = it.table;
st[table_sz[mnid]].erase(mnid);
table_sz[mnid] += it.x;
st[table_sz[mnid]].insert(mnid);
}
}
cout << ans << endl;
}
G.Rock&Frog
考虑一个简单的
d
p
dp
dp,
d
p
[
i
]
=
d
p
[
j
]
+
a
[
j
]
c
[
i
]
2
+
b
[
j
]
c
[
i
]
dp[i] = dp[j] + a[j]c[i] ^2 + b[j]c[i]
dp[i]=dp[j]+a[j]c[i]2+b[j]c[i]
考虑这是一个关于
c
[
i
]
c[i]
c[i]的二次函数，似乎无法维护，根据题目给出的条件对两个二次函数做差与韦达定理，得到
x
1
+
x
2
<
0
x_1 + x2 < 0
x1+x2<0, 又由于c[i] >= 0, 所以两个二次函数在
x
>
=
0
x>=0
x>=0有且只有一个交点，很多人对李超线段树存在误区，以为只能维护线段或直线，其实对于交点<= 1且只有两段单调性的函数，都可以用李超线段树来维护，这题就是类似维护直线分类讨论即可，注意标记永久化与动态开点，不得不吐槽的是，这题还要用__int128, 注意中间不要爆了。
#include<bits/stdc++.h>
#define lson lc[p], l, mid
#define rson rc[p], mid + 1, r
#define ls lc[p]
#define rs rc[p]
using namespace std;
using ll = __int128;
const int maxn = 1e5 + 5;
const ll inf = 1e18;
ll INF = (ll)inf * inf;
const int N = maxn * 18 * 4;
const int M = 1e9;
int a[maxn], b[maxn], c[maxn];
ll dp[maxn];
struct F {
int a, b;
ll c;
ll cal(int x) {
return (ll) a * x * x + (ll)b * x + c;
}
} fx[maxn];
void print(__int128 x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
struct SegmentTree {
int lc[N], rc[N], cnt;
F ff[N];
void update(int &p, int l, int r, int L, int R, F x) {
if (!p) {
p = ++cnt;
ff[p] = x;
ls = rs = 0;
return;
}
if (L <= l && r <= R) {
if (x.cal(l) < ff[p].cal(l) && x.cal(r) < ff[p].cal(r)) {
ff[p] = x;
} else if (x.cal(l) >= ff[p].cal(l) && x.cal(r) >= ff[p].cal(r)) {
return;
} else {
int mid = l + r >> 1;
if (x.cal(l) > ff[p].cal(l)) {
if (ff[p].cal(mid) > x.cal(mid)) {
update(lson, L, R, ff[p]);
ff[p] = x;
} else {
update(rson, L, R, x);
}
} else {
if (x.cal(mid) > ff[p].cal(mid)) {
update(lson, L, R, x);
} else {
update(rson, L, R, ff[p]);
ff[p] = x;
}
}
}
return;
}
int mid = l + r >> 1;
if (L <= mid)
update(lson, L, R, x);
if (R > mid)
update(rson, L, R, x);
}
ll query(int p, int l, int r, int x) {
if (!p)
return INF;
if (l == r) {
return ff[p].cal(x);
}
int mid = l + r >> 1;
ll ans = ff[p].cal(x);
if (x <= mid)
return min(ans, query(lson, x));
else
return min(ans, query(rson, x));
}
}tr;
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &a[i], &b[i], &c[i]);
fx[i].a = a[i], fx[i].b = b[i];
}
dp[1] = 0;
fx[1].c = dp[1];
int rt = 0;
tr.update(rt, 0, M, 0, M, fx[1]);
for (int i = 2; i <= n; ++i) {
dp[i] = tr.query(rt, 0, M, c[i]);
fx[i].c = dp[i];
tr.update(rt, 0, M, 0, M, fx[i]);
}
print(dp[n]);
return 0;
}
H.梅花易数
队友写的模拟
#include <bits/stdc++.h>
using namespace std;
map<string, int> H;
map<int, int> T;
void print(int S) {
for (int i = 0; i < 6; i++) {
int s = (S >> i) & 1;
if (s) cout << "---" << endl;
else cout << "- -" << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
H["Zi"] = 1;
H["Chou"] = 2;
H["Yin"] = 3;
H["Mao"] = 4;
H["Chen"] = 5;
H["Si"] = 6;
H["Wu"] = 7;
H["Wei"] = 8;
H["Shen"] = 9;
H["You"] = 10;
H["Xu"] = 11;
H["Hai"] = 12;
T[1] = 7;
T[2] = (0) | (1 << 1) | (1 << 2);
T[3] = (1) | (0 << 1) | (1 << 2);
T[4] = (0) | (0 << 1) | (1 << 2);
T[5] = (1) | (1 << 1) | (0 << 2);
T[6] = (0) | (1 << 1) | (0 << 2);
T[7] = (1) | (0 << 1) | (0 << 2);
T[0] = (0) | (0 << 1) | (0 << 2);
string y, h;
int m, d;
cin >> y >> m >> d >> h;
int t0 = (H[y] + m + d) % 8;
int t1 = (H[y] + m + d + H[h]) % 8;
int t2 = (H[y] + m + d + H[h]) % 6;
if (t2 == 0) t2 = 5;
else t2 -= 1;
print(T[t0] | (T[t1] << 3));
cout << endl;
print((T[t0] | (T[t1] << 3)) ^ (1 << (5 - (t2))));
}
I.Rock&String
转化后等价于问任意某个字符串的任意两个之间的最小距离差值。
无聊的SAM套路题，SAM parents树上线段树合并即可，线段树维护距离左端点的endpos最小距离，距离右端点的endpos的最小距离，询问的时候倍增跳过去查，纯码农题，vp的时候调了1h, 吐了
#include<bits/stdc++.h>
#define lson lc[p], l, mid
#define rson rc[p], mid + 1, r
#define ls lc[p]
#define rs rc[p]
using namespace std;
const int INF = 2e9;
const int maxn = 4e5 + 5;
const int N = maxn * 18 * 4;
struct SAM {
int len[maxn], link[maxn], ch[maxn][26], last, tot, rt[maxn], ld[N], rd[N], ans[N], lc[N], rc[N], cnt, lg[maxn];
int strlen, f[maxn][22], d[maxn], pos[maxn];
vector<int> G[maxn];
SAM() {
tot = last = 1;
}
void pushUp(int p, int l, int r) {
int mid = l + r >> 1;
if (!ls) {
ld[p] = ld[rs] + (mid - l + 1);
rd[p] = rd[rs];
ans[p] = ans[rs];
} else if(!rs) {
rd[p] = rd[ls] + (r - mid);
ld[p] = ld[ls];
ans[p] = ans[ls];
} else {
ld[p] = ld[ls];
rd[p] = rd[rs];
ans[p] = min({ans[ls], ans[rs], rd[ls] + ld[rs] + 1});
}
}
void update(int &p, int l, int r, int x, int val) {
if (!p)
p = ++cnt;
if (l == r) {
ld[p] = rd[p] = 0;
ans[p] = INF;
return;
}
int mid = l + r >> 1;
if (x <= mid)
update(lson, x, val);
else
update(rson, x, val);
pushUp(p, l, r);
}
int merge(int p, int q, int l, int r) {
if (!p || !q)
return p + q;
int x = ++cnt;
if (l == r) {
ld[x] = min(ld[p], ld[q]);
rd[x] = min(rd[p], rd[q]);
ans[x] = min(ans[p], ans[q]);
return x;
}
int mid = l + r >> 1;
lc[x] = merge(ls, lc[q], l, mid);
rc[x] = merge(rs, rc[q], mid + 1, r);
pushUp(x, l, r);
return x;
}
void dfs(int x, int fa) {
d[x] = d[fa] + 1;
f[x][0] = fa;
for (int i = 1; i <= lg[d[x]]; ++i)
f[x][i] = f[f[x][i - 1]][i - 1];
for (auto &v : G[x]) {
dfs(v, x);
rt[x] = merge(rt[x], rt[v], 1, strlen);
}
}
int extend(int c, int id) {
int cur = ++tot, p = last; last = cur;
len[cur] = len[p] + 1;
update(rt[cur], 1, strlen, len[cur], 1);
for (;p&&!ch[p][c]; p = link[p])
ch[p][c] = cur;
if (!p)
link[cur] = 1;
else {
int q = ch[p][c];
if (len[p] + 1 == len[q])
link[cur] = q;
else {
int clone = ++tot;
memcpy(ch[clone], ch[q], sizeof(ch[q]));
len[clone] = len[p] + 1;
link[clone] = link[q];
link[q] = link[cur] = clone;
for (; p && ch[p][c] == q; p = link[p]) {
ch[p][c] = clone;
}
}
}
return cur;
}
void solve() {
for (int i = 1; i <= tot; ++i) {
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}
for (int i = 2; i <= tot; ++i) {
G[link[i]].emplace_back(i);
}
dfs(1, 0);
int m;
cin >> m;
for (int i = 1; i <= m; ++i) {
int l, r;
cin >> l >> r;
int ps = pos[r];
for (int i = 19; i >= 0; --i) {
if (len[f[ps][i]] >= r - l + 1) {
ps = f[ps][i];
}
}
if (ps == 1 || ans[rt[ps]] == INF) {
cout << -1 << '\n';
} else {
cout << r - l + ans[rt[ps]] + 1 << '\n';
}
}
}
} sam;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
sam.strlen = s.length();
for (int i = 0; i < s.length(); ++i) {
sam.pos[i + 1] = sam.extend(s[i] - 'a', i + 1);
}
sam.solve();
return 0;
}
/*
abaabccababc
5
1 2
3 4
6 6
1 9
1 3
4
-1
2
-1
10
*/
J.新英雄
可撤销贪心。
1的位置是敌方小兵就无解。
我们能拿法力就拿法力，遇到敌人直接走，假如遇到敌人不够法力的时候，在0 - 1复用得到2点法力，最后的时候累计的时间减去累计法力 / 2 向下取整即可，考虑这个可撤销贪心的正确性，因为你在友军拿法力值的时候，你撤销等价于先少一点法力，再走斩消耗一点法力，所以相当于撤销2点法力，所以最后一定是2点2点法力可以全部考虑到0 - 1, 相当于提前预支代价。
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
struct Seg {
int t, l, r;
friend bool operator<(const Seg&x, const Seg&y) {
return x.l < y.l;
}
}seg[maxn], seg2[maxn];
int n, m, num;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> seg[i].t >> seg[i].l >> seg[i].r;
}
seg[0].t = 1;
seg[0].l = seg[0].r = 0;
seg2[0].t = 1;
seg2[0].l = seg2[0].r = 0;
sort(seg + 1, seg + 1 + m);
for (int i = 1; i <= m; ++i) {
if (seg[i].t == seg2[num].t) {
seg2[num].r = max(seg2[num].r, seg[i].r);
} else {
seg2[++num].t = seg[i].t;
seg2[num].l = seg[i].l;
seg2[num].r = seg[i].r;
}
}
if (!seg2[0].r) {
cout << "0/21/0";
return 0;
}
ll ans = 0, sum = 0;
for (int i = 0; i <= num; ++i) {
int len = seg2[i].r - seg2[i].l + 1 - (i == 0);
if (seg2[i].t == 1) {
sum += len;
ans += 3 * len;
} else {
if (sum < len) {
ll res = len - sum;
if (res & 1) {
res++;
}
sum += res;
ans += 3 * res;
}
ans += len;
sum -= len;
}
}
cout << ans - sum / 2 * 2;
return 0;
}
K.斐波那契
不会，数学队友不在，另一个队友没rush出来
L.启航者
O ( n 2 ) O(n^2) O(n2)枚举点，套路的考虑换根dp，f[x]表示从根往子树方向走最大值的答案， d p [ i ] [ 0 / 1 ] dp[i][0/1] dp[i][0/1] 表示从 i i i点出发下一个走最大值还是次大值的答案，先 d f s dfs dfs一次求出f和 d p [ 1 ] [ ∗ ] dp[1][*] dp[1][∗]，第二次从1进去 d f s dfs dfs的时候, 对于 x x x点，考虑走父亲还是儿子，同时考虑父亲是自己的最大还是次大，自己是父亲的最大还是次大，转移即可， 这里的值是无重复的，直接记录最大次大值转移即可。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 5;
vector<int> G[maxn];
ll dp[maxn][2], f[maxn];
int n, mx[maxn][2], a[maxn];
void dfs1(int x, int fa) {
int mx = -1, id = 0;
for (auto &v : G[x]) {
if (v == fa)
continue;
if (a[v] > mx) {
mx = a[v];
id = v;
}
}
for (auto &v : G[x]) {
if (v == fa)
continue;
dfs1(v, x);
}
f[x] = f[id] + a[x];
}
void getMx(int x, int v) {
if (a[v] > mx[x][0]) {
mx[x][1] = mx[x][0];
mx[x][0] = a[v];
} else if (a[v] > mx[x][1]) {
mx[x][1] = a[v];
}
}
void dfs2(int x, int fa) {
for (auto &v : G[x]) {
if (v == fa && x != 1) {
if (a[v] == mx[x][0]) {
if (mx[v][0] == a[x]) {
dp[x][0] = dp[fa][1] + a[x];
} else {
dp[x][0] = dp[fa][0] + a[x];
}
} else if (a[v] == mx[x][1]) {
if (a[x] == mx[v][0]) {
dp[x][1] = dp[fa][1] + a[x];
} else {
dp[x][1] = dp[fa][0] + a[x];
}
}
} else {
if (a[v] == mx[x][0]) {
dp[x][0] = a[x] + f[v];
} else if(a[v] == mx[x][1]) {
dp[x][1] = a[x] + f[v];
}
}
}
for (auto & v: G[x]) {
if (v == fa)
continue;
dfs2(v, x);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 2; i <= n; ++i) {
int x;
cin >> x;
G[i].emplace_back(x);
G[x].emplace_back(i);
}
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
mx[i][0] = mx[i][1] = -1;
dp[i][0] = dp[i][1] = a[i];
}
for (int i = 1; i <= n; ++i) {
for (auto v : G[i]) {
getMx(i, v);
}
}
dfs1(1, 0);
for (int i = 1; i <= n; ++i) {
if (a[i] == mx[1][0]) {
dp[1][0] = f[i] + a[1];
} else if(a[i] == mx[1][1]) {
dp[1][1] = f[i] + a[1];
}
}
dfs2(1, 0);
ll ans = 0;
int id = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, dp[i][0]);
}
for (int i = 1; i <= n; ++i) {
if (dp[i][0] == ans) {
id = i;
break;
}
}
cout << id << "\n" << ans;
return 0;
}
M.拉格朗日插值
原题套皮，怎么大四还要推拉格朗日乘数法啊，队友正好在考研让他给了公式，然后自己推了一下，推完后最大值是 k ( − k / 2 ) k^{(-k/2)} k(−k/2)， 考虑剩下的子问题就是个傻逼题，2020年澳门 A A A题也出过, 构造生成函数 F ( x ) = ∏ i = 1 m ( 1 + b i x ) F(x) = \prod_{i = 1} ^ {m} (1 + b_ix) F(x)=∏i=1m(1+bix), 做分治 f f t fft fft即可，答案即是第 k k k项的系数，最终答案是 k − k / 2 F ( x ) [ k ] ∗ i n v ( C ( m , k ) ) k^{-k/2} F(x)[k] * inv(C(m, k)) k−k/2F(x)[k]∗inv(C(m,k))
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353, G = 3;
const int maxn = 1e5 + 5;
int b[maxn];
int mul(int x, int y) {
return (ll) x * y % mod;
}
int Add(int x, int y) {
x += y;
if (x >= mod)
x -= mod;
return x;
}
int Sub(int x, int y) {
x -= y;
if (x < 0)
x += mod;
return x;
}
int mypow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1)
ans = mul(ans, a);
a = mul(a, a);
b >>= 1;
}
return ans;
}
namespace Poly
{
typedef vector<int> poly;
poly roots, rev;
void getRevRoot(int base) {
int lim = 1 << base;
if ((int)roots.size() == lim)
return;
roots.resize(lim);rev.resize(lim);
for (int i = 1; i < lim; ++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));
for (int mid = 1; mid < lim; mid <<= 1) {
int wn = mypow(G, (mod - 1) / (mid << 1));
roots[mid] = 1;
for (int i = 1; i < mid; ++i)
roots[mid + i] = mul(roots[mid + i - 1], wn);
}
}
void ntt(poly &a, int base) {
int lim = 1 << base;
for (int i = 0; i < lim; ++i) {
if (i < rev[i])
swap(a[i], a[rev[i]]);
}
for (int mid = 1; mid < lim; mid <<= 1) {
for (int i = 0; i < lim; i += (mid << 1)) {
for (int j = 0; j < mid; ++j) {
int x = a[i + j], y = mul(a[i + j + mid], roots[j + mid]);
a[i + j] = Add(x, y);
a[i + j + mid] = Sub(x, y);
}
}
}
}
poly operator*(poly a, poly b) {
int lim = (int)a.size() + (int)b.size() - 1, base = 0;
while ((1 << base) < lim)
++base;
a.resize(1 << base);
b.resize(1 << base);
getRevRoot(base);
ntt(a, base);
ntt(b, base);
for (int i = 0; i < (1 << base); ++i)
a[i] = mul(a[i], b[i]);
ntt(a, base);
reverse(a.begin() + 1, a.end());
a.resize(lim);
int inv = mypow(1 << base, mod - 2);
for (int i = 0; i < lim; ++i)
a[i] = mul(a[i], inv);
return a;
}
poly solve(int l, int r) {
if (l == r) {
return {1, b[l]};
}
int mid = l + r >> 1;
return solve(l, mid) * solve(mid + 1, r);
}
} // namespace name
int fac[maxn], facinv[maxn];
void init() {
fac[1] = fac[0] = 1;
for (int i = 2; i < maxn; ++i)
fac[i] = (ll) fac[i - 1] * i % mod;
facinv[maxn - 1] = mypow(fac[maxn - 1], mod - 2);
for (int i = maxn - 2; i >= 0; --i)
facinv[i] = (ll)facinv[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
return (ll)fac[n] * facinv[n - m] % mod * facinv[m] % mod;
}
int main() {
init();
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
auto it = Poly::solve(1, n);
cout << (ll)(mypow(mypow(k, k / 2), mod - 2)) * it[k] % mod * mypow(C(n, k), mod - 2) % mod;
return 0;
}
感觉GDCPC还是一贯的套路题巨多，机时还是很紧缺的。