ARC167
前言
非常不可做的一场，全场数学，打得心累。
[ARC167A] Toasts for Breakfast Party
传送门link
对于任意一个盘子价值形如 \((x_i+x_j)^2\) 的形式，那么所有的价值加起来一定是 \(\sum x_i^2 + \sum x_jx_k\) 现在要最小化后面那个
排个序即可。
signed main()
{
cin >> n >> m;
for (rint i = 1; i <= n; i++) cin >> a[i];
sort (a + 1, a + 2 * m + 1);
int ans = 0;
for (rint i = 1; i <= 2 * m; i++) ans += a[i] * a[i];
for (rint i = 1; i <= m; i++) ans += 2 * a[i] * a[2 * m - i + 1];
cout << ans << endl;
return 0;
}
[ARC167B] Product of Divisors
传送门link
\(A=p_{1}^{m_1}p_{2}^{m_2}\cdots p_{k}^{m_k}\)，有 \(A^B=(p_{1}^{m_1}p_{2}^{m_2}\cdots p_{k}^{m_k})^B=p_{1}^{m_1\times B}p_{2}^{m_2\times B}\cdots p_{k}^{m_k\times B}\)
考虑每个质因数 \(p_i\) 对乘积贡献多少次
枚举其他质因数的方案为 \(\prod_{j\ne i}(m_jB+1)\)，而枚举这个质因数的次数的范围为 \(0\sim m_i B\)，答案为
\((0+1+\cdots+m_iB)\prod_{j\ne i}(m_jB+1)=\dfrac{m_iB\prod(m_jB+1)}{2}\)
由于 \(A\) 中原本就有 \(m_i\)
最后的答案为 \(Ans=\lfloor\dfrac{B}{2}\prod(m_iB+1)\rfloor\)
int a, b, B;
int m;
bool flag;
int ans;
void solve(int x)
{
int i = 2;
while (i <= sqrt(x))
{
int cnt = 0;
while (!(x % i))
{
x /= i;
cnt++;
}
m = (cnt * b + 1) % mod * m % mod;
if ((cnt & 1) && (B & 1)) flag = 0;
bool v = i != 2;
i += 1 + v;
}
if (x > 1)
{
m = m * (b + 1) % mod;
flag = 0;
}
}
signed main()
{
cin >> a >> b;
B = b;
flag = b & 1;
m = b %= mod;
solve(a);
ans = (m - flag) * 499122177 % mod;
cout << (ans % mod + mod) % mod << endl;
return 0;
}
[ARC167C] MST on Line++
传送门link
做不出来，官方题解也搞不懂，最后看的洛谷第一篇题解
考虑计算当前的 \(a_i\) 会成为多少个边权。
\(a_i\) 按 \(p\) 重新排列后，\(i\) 需要在前面选择一个父亲，则选择父亲的这条边的权值为 \(a_i\) 当且仅当前面的 \(k\) 个 \(a\) 中存在一个 \(a_j\) 使得 \(a_j\le a_j\)，其余的随便排
而 \(i\) 向儿子的全部连边中，边权为 \(a_i\) 当且仅当儿子 \(j\) 前面的 \(k\) 个 \(a\) 均比 \(a_j\) 大且 \(a_i\) 为最小的一个。则选出 \(k\) 个比 \(a_i\) 大的数进行排列并钦定这个排列右边的第一个数比 \(a_i\) 小即可
int n, k;
int a[N];
int fac[N], ifac[N], inv[N];
int ans;
void init()
{
fac[0] = 1;
fac[1] = inv[1] = 1;
for (rint i = 2; i < N; i ++)
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
ifac[0] = ifac[1] = 1;
for (rint i = 2; i < N; i++)
{
ifac[i] = inv[i] * ifac[i - 1] % mod;
}
}
int C(int a, int b)
{
if (b < 0 || a < b) return 0;
return fac[a] * ifac[a - b] % mod * ifac[b] % mod;
}
signed main()
{
cin >> n >> k;
init();
for (rint i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
for (rint i = 1; i <= n; i++)
{
int add, t;
for (rint j = 1; j < k; j++)
{
add = a[i] * (C(n - 1, j) - C(n - i, j) + mod);
t = n - j - 1;
ans += add % mod * fac[j] % mod * fac[t] % mod;
}
add = a[i] * (n - k) % mod * (C(n - 1, k) - C(n - i, k) + mod);
t = n - k - 1;
ans += add % mod * fac[k] % mod * fac[t] % mod;
for (rint j = 1; j < k; j++)
{
add = a[i] * C(n - i, j - 1) % mod;
t = n - j - 1;
ans += add * fac[j] % mod * fac[t] % mod * (i - 1) % mod;
}
t = n - k - 1;
add = a[i] * (n - k) % mod * C(n - i, k - 1) % mod;
ans += add * fac[k] % mod * fac[t] % mod * (i - 1) % mod;
ans %= mod;
}
cout << ans << endl;
return 0;
}
[ARC167D] Good Permutation
传送门link
连边 \(i\to P_i\)，形成了若干个不相交的环。
若\(P\) 是一个好的排列当且仅当图上只有一个环。
从小到大依次贪心确定每一位的值，如果存在至少一个 \(P_j=u,j > i\)（\(i\) 为当前位置），\(i,j\) 不在一个环且 \(u < P_i\)，找到最小的 \(u\) 并 \(\text{swap}(P_i,P_j)\)
否则不希望字典序变大，尽量不换。但如果 \(i\) 是它所在连通块的最后一个位置，必须要换，找到后面最小的 \(u\)，设 \(P_j=u\)，并 \(\text{swap}(P_i,P_j)\)
判断是否在一个环使用并查集即可
#define X it->x
#define Y it->y
using namespace std;
const int N = 2e5 + 5;
int n;
int a[N];
int fa[N], minn[N];
int sz[N], p[N];
struct node
{
int x, y;
friend bool operator < (node a, node b)
{
return a.x < b.x;
}
};
set<node> s;
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int a, int b)
{
int x = find(a);
int y = find(b);
if (x != y)
{
s.erase({minn[x], x});
s.erase({minn[y], y});
fa[x] = y;
sz[y] += sz[x];
minn[y] = min(minn[y], minn[x]);
s.insert({minn[y], y});
}
}
signed main()
{
int T;
cin >> T;
while (T--)
{
s.clear();
cin >> n;;
for (rint i = 1; i <= n; i++)
{
cin >> a[i];
p[a[i]] = fa[i] = minn[i] = i;
sz[i] = 1;
s.insert({i, i});
}
for (rint i = 1; i <= n; i++) merge(i, a[i]);
for (rint i = 1; i <= n; i++)
{
if (s.size() == 1) break;
auto it = s.begin();
while (find(i) == find(Y)) it++;
if (X < a[i] || sz[find(i)] == 1)
{
int j = p[X];
swap(a[i], a[j]);
swap(p[a[i]], p[a[j]]);
merge(i, j);
}
sz[find(i)]--;
}
for (rint i = 1; i <= n; i++) cout << a[i] << " ";
cout << endl;
}
return 0;
}
[ARC167E] One Square in a Triangle
传送门link
三角形平移对答案没有影响，设一个点为 \((0,0)\)。
面积 \(\frac{S}{2}\)，定一个点为 \((2,0)\)，然后把三角形高度设为 \(\frac{S}{2}\) 。因为不能再产生其它正方形，所以让一条斜边与正方形有一个交点，因为后面肯定这条斜边与另一条斜边的距离会变小，不可能再出现一个正方形。第三个点取 \((\frac{S}{2},\frac{S}{2})\) 。
考虑 \(S\) 是奇数的情况。一个点在 \((0,0)\)，设另外两个点为 \((x_1,y_1)\) 和 \((x_2,y_2)\)，则有 \(S=|x_1y_2-x_2y_1|\)，假设 \(x_1y_2\) 为奇数，接着给 \(x_1\) 和 \(x_2\) 一个值。给个 \(3\) 和 \(1\) ，\(S=|3y_2-y_1|\)，考虑去绝对值，让 \(y_1<3y_2\)，因为这两个奇偶性不同，让 \(3y_2-y_1=1\) 就可以了，解出来 \(y_1=\frac{S-3}{2},y_2=\frac{S-1}{2}\)。
有一些无解的情况要特判，偶数的情况发现只有 \(2\) 无解，奇数 \(1,3,5,7\) 无解。
signed main()
{
cin >> T;
while (T--)
{
int s;
cin>> s;
if (s == 1 | s == 2 || s == 3 || s == 5 || s == 7) puts("No");
else
{
puts("YES");
if (s & 1) cout << "0 0 1 3 " << (s - 1) / 2 << " " << (s - 3) / 2 << endl;
else cout << "0 0 2 0 " << s / 2 << " " << s / 2 << endl;
}
}
return 0;
}
[ARC167F] Tree Tree Tree
传送门link
Question
给你整数 \(N\) 和 \(K\)，使得 \(2\leq K\leq N\).
问题：potato
有一棵加权有根树，其顶点为 \(N\) ，编号为 \(1\) 至 \(N\)。顶点 \(1\) 是根。
对于每个 \(2\leq i\leq N\)，点 \(i\) 的父顶点是 \(p_{i}\;(1\leq p_{i} < i)\)，连接 \(i\) 和 \(p_{i}\) 的边的权重是 \(q_{i-1}\)。
这里，\(q=(q_{1},q_{2},\dots,q_{N-1})\) 是 \((1,2,\dots,N-1)\) 的排列。
假设 \(cost(u,v)\) 是连接顶点 \(u\) 和 \(v\) 的简单路径中一条边的最大权重。
找到 \(\sum_{u=1}^{N} \sum_{v=u+1}^{N} cost(u,v)\)。
问题：tomato
给你一个整数 \(a\)，使得 \(1\leq a\lt K\)。在上面的问题中，\(p\) 和 \(q\) 可能有 \(\frac{((N-1)!)^{2}}{K-1}\) 对，且 \(p_{K}=a\)。求所有这些对的答案之和，模数\(998244353\)。
求每个 \(a=1,\dots,K-1\) 的问题 tomato 的答案。
Solution
如果我们固定 \(p\)，并让 \(A_{i}\) 表示路径长度为 \(i\) 的顶点 \(u,v\;(u\lt v)\) 对的数目，那么所有 \(q\) 的 "potato " 问题答案之和可以用序列 \(B=(B_{1},\dots, B_{N-1})\) 表示为 $ \sum_{i=0}^{N-1} A_{i}B_{i}$。因此，"tomato " 问题的答案可以表示为 \([x^{N-1}] (f_{a}(x) g(x))\)，其中 \([x^i]f_{a}(x)\) 是顶点 \(u\) 和 \(v\) 之间的路径长度为 \(i\) 和 \(p_{K}=a\) 以及 \(g(x)=\sum_{j=1}^{N-1}B_{j}x^{N-1-j}\) 的三元组 \((p,u,v)\) 的个数。
首先，很容易看出 \(B_{j}=\frac{N! j}{j+1}\).
让我们根据路径的类型分解 \(f_{a}(x)\) 并分别计算每一部分。
\(f_{a1}(x)\) : 连接顶点 \(u\) 和 \(v\) 且至少不包含其中一个顶点 \(a\) 和 \(K\) 的路径的数目。
\(f_{a2}(x)\) : 连接顶点 \(u\) 和 \(v\) 且包含顶点 \(a\) 和 \(K\)，且 \(u\) 和 \(v\) 的 LCA 为 \(a\) 的路径数。
\(f_{a3}(x)\) : 连接顶点 \(u\) 和 \(v\) 且包含顶点 \(a\) 和 \(K\)，且 \(u\) 和 \(v\) 的 LCA 不为 \(a\) 的路径条数。
对于 \(f_{a1}(x)\)
设 \(h_{i}(x)\) 是从 \(f_{a1}(x)\) 中提取 LCA 为 \(1\leq i\leq N\) 的项得到的多项式，则下式成立：
\[h_{i}(x)=\frac{1}{2}\left(\prod_{2\leq j\leq i,j\neq K} j-1 \right)\prod_{i\lt j\leq N,j\neq K}((j-1)+2x). \]这里，\(h_{i}(x)\) 的常数项可以是任何项（因为它不会影响结果）。因此可以在\(O(N\log^{2}(N))\) 中通过分治计算出来
对于 \(f_{a2}(x)\)
\[f_{a2}(x)=x(a-1)!\prod_{j=a+1}^{K-1}((j-1)+x)\prod_{j=K+1}^{N}((j-1)+2x) \]对于 \(f_{a3}(x)\)
\[f_{a3}(x)=x^{2}\sum_{i=1}^{a-1}\left((i-1)!\prod_{j=i+1}^{a-1}((j-1)+2x)\prod_{j=a+1}^{K-1}((j-1)+x)\right)\prod_{j=K+1}^{N}((j-1)+2x) \]虽然无法在规定的时间内明确计算出 \(f_{a2}(x)\) 和 \(f_{a3}(x)\) ，但适当地去除不必要的项，计算出 \(O(N\log^{2}(N))\) 中所有 \(a\) 的 \([x^{N-1}] (f_{a2}(x)g(x))\) 和 \([x^{N-1}] (f_{a3}(x)g(x))\)
仅以 \(f_{a3}\) 为例子
对于任意整数 \(0 \leq l\leq r\lt K\) ，定义 \(x\) 的多项式 \(X_{l,r},Y_{l,r},Z_{l,r},W_{l,r},DP1_{l,r},DP2_{l,r}\) 如下：
-
\(\displaystyle X_{l,r}=\prod_{i=l}^{r-1} \max(i,1)\)
-
\(\displaystyle Y_{l,r}=\prod_{i=l}^{r-1} (i+2x)\)
-
\(\displaystyle Z_{l,r}=\prod_{i=l}^{r-1} (i+x)\)
-
\(\displaystyle W_{l,r}=\sum_{j=l+1}^{r}X_{l,j}Y_{j,r}\)
-
\(\displaystyle DP1_{l,r}=g(x)x^{2}X_{0,l}Z_{r,K-1}\prod_{j=K}^{N-1}(j+2x)\)
-
\(\displaystyle DP2_{l,r}=g(x)x^{2}W_{0,l}Z_{r,K-1}\prod_{j=K}^{N-1}(j+2x)\)
由于 \(g(x)f_{a3}(x)=DP2_{a-1,a}\) 成立，所以只要找到所有 \(1\leq a\lt K\) 的 \([x^{N-1}] DP2_{i-1,i}\) 即可。
对于任意整数 \(0\leq l\lt m\lt r\leq K\) ，下面的条件成立
\(DP1_{l,m}=DP1_{l,r}Z_{m,r}\)
\(DP1_{m,r}=DP1_{l,r}X_{l,m}\) \(DP2_{l,m}=DP2_{l,r}Z_{m,r}\)
\(DP2_{l,r}=DP2_{l,r}Y_{l,m}+DP1_{l,r}W_{l,m}\)
由于 \(DP1_{0,K-1}\) 和 \(DP2_{0,K-1}\) 很容易找到，所以从这里开始，选择 \(m\) 为 \(m=\frac{l+r}{2}\)，就可以在 \(O(\log K)\) 多项式乘法中找到 \(DP2_{a-1,a}\)。
在计算 \(DP1\) 和 \(DP2\) 之前，应先计算用于求 \(DP2_{a-1,a}\) 的 \(X,Y,Z,W\)。
由于 \(Y_{l,r},Z_{l,r},W_{l,r}\) 最多是 \((r-l)\) 阶多项式，随着 \(r-l\) 的减小，被乘多项式的阶数也随之减小
因此，在预计算中进行多项式乘法和加法运算的多项式的总度数为 \(O(K\log{K})\)，所以预计算可以在时间复杂度为 \(O(K\log^{2}{K})\) 的情况下完成。
除了求 \(DP1_{0,K-1}\) 所需的 \(O(N\log^{2}{N})\) 时间外，\(DP1_{l,r}\) 和 \(DP2_{l,r}\) 的计算也可以在 \(O(K\log^{2}K)\) 时间内完成，因为求 \([x^{N-1}] DP2_{a-1,a}\) 时最多只需保留 \(O(r-l)\) 项。
Code
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 5;
const int M = 3e5 + 5;
const int mod = 998244353;
int n, K;
int ans[N], rev[M], w[M];
int maxn;
int fac[N], inv[N];
int tot;
template<typename T>
void upd(int &a, T b)
{
a = (a + b) % mod;
}
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
void init()
{
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for (rint i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
for (rint i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
void init(int len)
{
int l = 0;
maxn = 1;
while (maxn <= len)
{
maxn <<= 1;
l++;
}
for (rint i = 0; i < maxn; i++)
{
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
for (rint i = 1; i < maxn; i <<= 1)
{
int kk = qpow(3, (mod - 1) / (i << 1));
w[i] = 1;
for (rint j = 1; j < i; j++)
{
w[i + j] = w[i + j - 1] * kk % mod;
}
}
}
void NTT(vector<int> &p, bool flag)
{
static unsigned long long a[M];
p.resize(maxn);
for (rint i = 0; i < maxn; i++)
{
a[i] = p[rev[i]];
}
for (rint i = 1; i < maxn; i <<= 1)
{
for (rint j = 0; j < maxn; j += i << 1)
{
for (rint k = j; k < j + i; k++)
{
unsigned long long x = a[k], y = a[k + i] * w[i + k - j] % mod;
a[k] = x + y;
a[k + i] = x + mod - y;
}
}
}
if (flag)
{
for (rint i = 0; i < maxn; i++)
{
p[i] = a[i] % mod;
}
}
else
{
reverse(a + 1, a + maxn);
int inv = qpow(maxn, mod - 2);
for (rint i = 0; i < maxn; i++) p[i] = a[i] % mod * inv % mod;
}
}
vector<int> operator+(const vector<int> &a, const vector<int> &b)
{
int n = a.size(), m = b.size();
vector<int> ans(max(n, m));
for (rint i = 0; i < n; i++) ans[i] = a[i];
for (rint i = 0; i < m; i++) upd(ans[i], b[i]);
return ans;
}
vector<int> operator-(const vector<int> &a, const vector<int> &b)
{
int n = a.size(), m = b.size();
vector<int> ans(max(n, m));
for (rint i = 0; i < n; i++) ans[i] = a[i];
for (rint i = 0; i < m; i++) upd(ans[i], mod - b[i]);
return ans;
}
vector<int> operator*(vector<int> a, int k)
{
for (rint &i : a) i = i * k % mod; return a;
}
vector<int> mul(vector<int> a, vector<int> b, int Type = -1)
{
int n = a.size(), m = b.size();
if (Type < 0) Type = n + m - 1;
init(n + m);
NTT(a, 1), NTT(b, 1);
for (rint i = 0; i < maxn; i++) a[i] = a[i] * b[i] % mod;
NTT(a, 0), a.resize(Type);
return a;
}
vector<int> mul__(vector<int> a, vector<int> b, int Type = -1)
{
int n = a.size(), m = b.size();
if (Type < 0) Type = n - m + 1;
a.resize(m + Type - 1);
reverse(b.begin(), b.end());
init(m + Type - 1);
NTT(a, 1), NTT(b, 1);
for (rint i = 0; i < maxn; i++) a[i] = a[i] * b[i] % mod;
NTT(a, 0);
move(a.begin() + m - 1, a.begin() + m + Type - 1, a.begin());
a.resize(Type);
return a;
}
struct node
{
vector<int> P0, P1, P2, Ps;
node operator+(const node &x)const
{
node ans;
ans.P0 = mul(P0, x.P0);
ans.P1 = mul(P1, x.P1);
ans.P2 = mul(P2, x.P2);
ans.Ps = mul(Ps, x.P1) + mul(P0, x.Ps);
return ans;
}
} val[M];
struct node2
{
vector<int> P0, P1, Ps;
node2 operator+(const node2 &x)const
{
node2 ans;
ans.P0 = mul(P0, x.P0);
ans.P1 = mul(P1, x.P1);
ans.Ps = mul(P0, x.Ps) + mul(Ps, x.P1);
return ans;
}
};
void build(int p, int l, int r)
{
if (l == r)
{
val[p].P0 = {max(l - 1, 1ll), 0};
val[p].P1 = {max(l - 1, 1ll), 1};
val[p].P2 = {max(l - 1, 1ll), (mod + 1) / 2};
val[p].Ps = {0, max(l - 1, 1ll)};
return;
}
int mid = (l + r) / 2;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
val[p] = val[p << 1] + val[p << 1 | 1];
}
vector<int> solve1(int l, int r)
{
if (l == r) return {max(l - 1, 1ll), 1};
int mid = (l + r) >> 1;
return mul(solve1(l, mid), solve1(mid + 1, r));
}
node2 solve2(int l, int r)
{
if (l == r)
{
node2 ans;
if (l != K)
{
ans.P0 = {max(l - 1, 1ll), 0};
ans.P1 = {max(l - 1, 1ll), 1};
ans.Ps = {0, max(l - 1, 1ll)};
}
else
{
ans.P0 = ans.P1 = {1, 0};
ans.Ps = {0, 1};
}
return ans;
}
int mid = (l + r) >> 1;
return solve2(l, mid) + solve2(mid + 1, r);
}
void solve3(int p, int l, int r, const vector<int> &u, const vector<int> &d)
{
if (l == r) return upd(ans[l], (mod + 1) / 2 * u[1] + max(l - 1, 1ll) * d[1]);
int mid = (l + r) >> 1;
solve3(p * 2, l, mid, mul__(u, val[p * 2 + 1].P2), mul__(d, val[p * 2 + 1].P2));
solve3(p * 2 + 1, mid + 1, r, mul__(u, val[p * 2].P1) + mul__(d, val[p * 2].Ps), mul__(d, val[p * 2].P0));
}
void calc()
{
vector<int> F = K < n ? mul({0, 1}, solve1(K + 1, n)): (vector<int>) {0, 1}, G(n + 1);
for (rint i = 2, pw = 1; i <= n; pw = pw * 2 % mod, i++) G[i] = pw * inv[i] % mod; G = mul__(G, F);
vector<int> H = solve2(1, n).Ps;
int t = 0;
for (rint i = 2, pw = 1; i <= n; pw = pw * 2 % mod, i++) upd(t, pw * inv[i] % mod * H[i]);
fill(ans + 1, ans + K, t); solve3(1, 1, K - 1, vector<int>(G.size()), G);
tot = n * (n - 1) / 2 % mod * fac[n - 1] % mod * inv[K - 1] % mod;
}
signed main()
{
cin >> n >> K;
init(); build(1, 1, K - 1);
calc();
for (rint i = 1; i < K; i++)
{
int rs = (tot - ans[i] + mod) % mod * fac[n] % mod;
cout << rs << endl;
}
return 0;
}