牛客挑战赛 73
A S 老师的公式
先把
算出来，可以发现
。
然后根据 ，用循环计算
，每次乘法后取模，中间结果恰好
在 long long 范围内。
最后再对 long long 求一次 gcd 即可。
#include <bits/stdc++.h>
using LL = long long;
LL n;
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
int main() {
std::cin >> n;
LL a = n * (n + 1) / 2;
LL prod = 1;
for(int i = 1; i <= n; i ++) {
prod = 1LL * prod * i % a;
}
LL ans = gcd(prod, a);
std::cout << ans << std::endl;
return 0;
}
B S 老师的签到
使用两个队列，按 分层 BFS。
每次只从当前队列扩展到下一层的最小字符即可。
时间复杂度线性。
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
const int N = 2005;
char s[N][N], ans[N * 2];
int n, m;
struct node {
int x, y;
};
bool vis[N][N];
vector<node> q[2];
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) {
scanf("%s", s[i] + 1);
}
int c = 0, w = 1;
q[c].push_back(node{1, 1}); vis[1][1] = true;
ans[w] = s[1][1];
for(int i = 1; i <= n + m - 2; i ++) {
c ^= 1; q[c].clear();
char o = 'z';
for(node u: q[c^1]) {
int x = u.x, y = u.y;
if(x < n) o = min(o, s[x+1][y]);
if(y < m) o = min(o, s[x][y+1]);
}
ans[++w] = o;
for(node u: q[c^1]) {
int x = u.x, y = u.y;
if(x < n && o == s[x+1][y] && !vis[x+1][y]) {
q[c].push_back({x + 1, y});
vis[x+1][y] = true;
}
if(y < m && o == s[x][y+1] && !vis[x][y+1]) {
q[c].push_back({x, y + 1});
vis[x][y+1] = true;
}
}
}
puts(ans + 1);
return 0;
}
C S 老师的求和
题意：
定义
求 。
题解：
简单方法：由路径的组合意义知
复杂方法：使用不超过 的自然数幂和公式硬推，或者使用拉格朗日插值等均可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 10, mod = 998244353;
int inv[] = {1, 499122177, 166374059, 291154603};
int a, b;
long long L(int i, int k) {
int ans = 1ll * inv[i] * ((1ll * a * k + 1ll * i * a + 1ll * (i + 1) * b) % mod) % mod;
for (int j = 0; j < i; ++j)
ans = 1ll * ans * (k + j) % mod;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int k;
cin >> a >> b >> k;
cout << L(0, k) << " " << L(1, k) << " " << L(2, k) << " " << L(3, k) << '\n';
}
}
D S 老师的虚树
题意：
给你一个点数为 、边上有颜色的树，对于
求出选
个不同的点构成斯坦纳树的颜色数的期望。
。
题解：
发现求期望实际上求出方案数后除以一个组合数就行了，那么我们只需要考虑方案数，对于方案数，可以计算每个颜色的概率之后加和。
那么现在的主要问题是单个颜色的期望怎么算，考虑容斥，即不包含该边的概率。
我们将所有该种颜色的边断开，假设剩下的连通块大小分别为 ，那么该颜色对于
的贡献为
。
那么最后答案就是要求形如 的每一项系数。
而
可以用一次减法卷积解决。
对于所有连通大小的处理，可以按照 dfs 序从大到小加入栈在线性时间内维护，也可以使用虚树。
总复杂度为 NTT 的复杂度 。
#include <bits/stdc++.h>
using namespace std;
int read() {
int res = 0, w = 1;
char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
return res * w;
}
#define fi first
#define se second
#define pii pair<int, int>
using LL = long long;
using uLL = unsigned long long;
using uint = unsigned;
const int INF = 1e9;
const int Mod = 998244353, inv2 = (Mod + 1) / 2;
int upd(int x) { return x + (x >> 31 & Mod); }
int fpow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = 1ll * res * x % Mod;
x = 1ll * x * x % Mod, y >>= 1;
}
return res;
}
const int MAX_N = (1 << 20) + 10;
#define vi vector<int>
int Limit, omg[MAX_N];
int fac[MAX_N], ifc[MAX_N], inv[MAX_N];
void FFT_prepare(int len) {
for (Limit = 1; Limit < len; Limit <<= 1);
static int L = 1;
for (int &i = L; i < Limit; i <<= 1) {
omg[i] = 1;
int w = fpow(3, Mod / 2 / i);
for (int j = 1; j < i; j++) omg[i + j] = 1ll * omg[i + j - 1] * w % Mod;
}
}
void DFT(vi &p) {
for (int i = Limit >> 1, s = Limit; i; i >>= 1, s >>= 1)
for (int j = 0; j < Limit; j += s)
for (int k = 0, o = i; k < i; ++k, ++o) {
int x = p[j + k], y = p[i + j + k];
p[j + k] = upd(x + y - Mod), p[i + j + k] = 1ll * omg[o] * upd(x - y) % Mod;
}
}
void IDFT(vi &p) {
for (int i = 1, s = 2; i < Limit; i <<= 1, s <<= 1)
for (int j = 0; j < Limit; j += s)
for (int k = 0, o = i; k < i; ++k, ++o) {
int x = p[j + k], y = 1ll * omg[o] * p[i + j + k] % Mod;
p[j + k] = upd(x + y - Mod), p[i + j + k] = upd(x - y);
}
reverse(p.begin() + 1, p.end());
for (int i = 0, inv = fpow(Limit, Mod - 2); i < Limit; i++) p[i] = 1ll * p[i] * inv % Mod;
}
void NTT(vi &p, int op) {
p.resize(Limit);
if (op == 1) DFT(p);
else IDFT(p);
}
vi operator*(vi a, vi b) {
int len = a.size() + b.size();
FFT_prepare(len);
NTT(a, 1), NTT(b, 1);
for (int i = 0; i < Limit; i++) a[i] = 1ll * a[i] * b[i] % Mod;
NTT(a, 0), a.resize(len);
return a;
}
void binomPrepare(int n) {
for (int i = fac[0] = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;
ifc[n] = fpow(fac[n], Mod - 2);
for (int i = n - 1; ~i; i--) ifc[i] = 1ll * (i + 1) * ifc[i + 1] % Mod;
for (int i = inv[0] = 1; i <= n; i++) inv[i] = 1ll * ifc[i] * fac[i - 1] % Mod;
}
int C(int n, int m) {
return 1ll * fac[n] * ifc[m] % Mod * ifc[n - m] % Mod;
}
int N, fa[MAX_N], fc[MAX_N];
int L[MAX_N], R[MAX_N], dfn[MAX_N], tim;
vector <pii> G[MAX_N];
void dfs(int x) {
L[x] = ++tim, dfn[tim] = x;
for (auto e: G[x]) {
if (e.fi == fa[x]) continue;
fc[e.fi] = e.se, fa[e.fi] = x;
dfs(e.fi);
}
R[x] = tim;
}
int c[MAX_N];
int sum(int x) {
int res = 0;
for (; x >= 1; x -= x & -x) res += c[x];
return res;
}
void add(int x, int v) { for (; x <= N; x += x & -x) c[x] += v; }
vector<int> edge[MAX_N];
vi F;
int main() {
N = read();
F.resize(N + 1);
for (int i = 1; i < N; i++) {
int u = read(), v = read(), w = read();
G[u].emplace_back(v, w), G[v].emplace_back(u, w);
}
dfs(1);
binomPrepare(N);
for (int i = 1; i <= N; i++) add(i, 1);
for (int i = N; i >= 2; i--) {
int x = dfn[i];
edge[fc[x]].push_back(x);
}
for (int i = 1; i <= N; i++) {
vector <pii> rollback;
for (int x: edge[i]) {
int sz = sum(R[x]) - sum(L[x] - 1);
F[sz]++;
rollback.emplace_back(L[x], sz);
add(L[x], -sz);
}
F[sum(N)]++;
for (int j = rollback.size() - 1; j >= 0; j--) {
add(rollback[j].fi, rollback[j].se);
}
}
vi G(N + 1);
for (int i = 0; i <= N; i++) G[i] = ifc[N - i];
for (int i = 0; i <= N; i++)
F[i] = 1ll * F[i] * fac[i] % Mod;
F = F * G;
for (int i = 1; i <= N; i++) {
int f = 1ll * ifc[i] * F[N + i] % Mod;
f = upd(1ll * N * C(N, i) % Mod - f);
f = 1ll * f * fpow(C(N, i), Mod - 2) % Mod;
printf("%d%c", f, " \n"[i == N]);
}
return 0;
}
E S 老师的礼物
题意：
给定一棵树每个结点相邻结点编号的最小值 ，问对应的树有至少两种，唯一确定还是不存在。如果唯一，要输出这棵树。
。
题解：
先将 和
连边，如果存在
，
或连出至少三个点的环则无解。
我们称目前同一个连通块的点为相同颜色。接下来需要考虑所有颜色不同的 满足
，连边
，问当前图是否是树。
先判连通性，再判边数为 。
判连通性可以忽略颜色，对于所有满足 的二元组
连边。对一维扫描线，另外一维用堆维护每个并查集中第二维最小的点即可。
判边数时，若边数为 ，只需依次找到所有边。用线段树维护最小值，每次加入一种颜色前在线段树上通过维护最小值 DFS 找到所有边，再把这种颜色所有点加入线段树。
时间复杂度 。
验题人提供了复杂度为线性的并查集做法，因此没有打算放 通过。
#include <bits/stdc++.h>
#define pb push_back
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;
using pii = pair<int, int>;
const int N = 5e5 + 10;
const int INF = 2e9;
int n, a[N];
struct ufs {
int f[N];
void init() {
for (int i = 1; i <= n; i++)
f[i] = i;
}
int find(int u) {
return u == f[u] ? u : f[u] = find(f[u]);
}
bool unite(int u, int v) {
u = find(u);
v = find(v);
f[u] = v;
return u != v;
}
} F, G;
struct Node {
int i;
bool operator < (const Node &b) const {
return a[i] > a[b.i];
}
};
vector<int> vec[N], col[N];
#define ls u << 1, l, mid
#define rs u << 1 | 1, mid + 1, r
struct SGT {
int mi[N * 4];
void upd(int u) {
mi[u] = min(mi[u * 2], mi[u * 2 + 1]);
}
void build(int u, int l, int r) {
mi[u] = INF;
if (l == r)
return;
int mid = (l + r) >> 1;
build(ls);
build(rs);
upd(u);
}
void modify(int u, int l, int r, int x, int y) {
if (l == r) {
mi[u] = y;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) modify(ls, x, y);
else modify(rs, x, y);
upd(u);
}
vector<int> seq;
void solve(int u, int l, int r, int ql, int qr, int x) {
if (mi[u] > x || l > qr || r < ql)
return;
if (l == r) {
seq.pb(l);
return;
}
int mid = (l + r) >> 1;
solve(ls, ql, qr, x);
solve(rs, ql, qr, x);
}
} T;
#undef ls
#undef rs
int main() {
int test;
scanf("%d", &test);
while (test--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
bool fail = false;
for (int i = 1; i <= n; i++) {
if (i == a[i]) fail = true;
if (a[a[i]] > i) fail = true;
}
if (fail) {
puts("None");
continue;
}
F.init();
vector <pii> e;
for (int i = 1; i <= n; i++) {
if (a[a[i]] == i) {
if (i < a[i]) {
if (!F.unite(i, a[i])) {
fail = true;
break;
}
e.push_back(pii(i, a[i]));
}
} else {
if (!F.unite(i, a[i])) {
fail = true;
break;
}
e.push_back(pii(i, a[i]));
}
}
if (fail) {
puts("None");
continue;
}
for (int i = 1; i <= n + 1; i++) vec[i].clear();
for (int i = 1; i <= n; i++) {
vec[a[i]].pb(i);
}
priority_queue <Node> q;
for (int i = 1; i <= n; i++) G.f[i] = F.f[i]; //copy
vector<int> c(n + 1);
per(i, n, 1) {
q.push({i});
for (int u: vec[i]) {
vector<int> cur;
while (q.size()) {
int x = q.top().i;
if (a[x] > u) break;
q.pop();
cur.pb(x);
}
c[G.find(u)] = 0;
for (int v: cur) c[G.find(v)] = 0;
for (int v: cur) G.unite(u, v);
for (int v: cur) {
if (!c[F.find(v)]++) {
q.push({v});
}
}
}
}
bool con = true;
rep(i, 1, n)con &= G.find(i) == G.find(1);
if (!con) {
puts("None");
} else {
rep(i, 1, n) col[i].clear();
rep(i, 1, n) col[F.find(i)].pb(i);
T.build(1, 1, n);
rep(i, 1, n) {
for (int x: col[i]) {
T.seq.clear();
T.solve(1, 1, n, a[x], n, x);
for (int y: T.seq) {
e.pb({x, y});
}
}
if (e.size() >= n)
break;
for (int x: col[i]) {
T.modify(1, 1, n, x, a[x]);
}
}
if (e.size() == n - 1) {
puts("Unique");
for (auto &[x, y]: e)
if (x > y) swap(x, y);
sort(e.begin(), e.end());
for (auto [x, y]: e) {
printf("%d %d\n", x, y);
}
} else {
puts("Many");
}
}
}
return 0;
}
F S 老师的合并
题意：
给两棵有根、有标号，子结点有顺序的树 ，求有多少种方案将这两棵树合并成一棵树
, 使得合并之后属于同一棵树的结点的祖先后代关系不变、在 DFS 序中的顺序不变。
题解：
将树转化成括号序，问题即变为按顺序合并两个括号序列，使得同一个括号序中的括号嵌套关系不变。
在合并括号序列时，可以先考虑最外层的括号，对内层的括号转化为子问题递归求解。假设合并的两段括号序起点固定，设 表示合并第一个括号序长度为
、第二个括号序长度为
的前缀的方案数。转移时枚举最后一个括号从哪个序列中选择，不妨设为序列 1，则可以选择序列 2 的一段后缀与最后一个括号的子括号序列合并，即
。最后一个括号从序列 2 选择的方案数类似。
标算采用区间 DP 的方式，状态总数 ，转移
，总复杂度为
。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL read() {
char ch = getchar();
LL sum = 0;
bool f = 0;
while ((ch < '0' || ch > '9') && ch != '-')ch = getchar();
if (ch == '-')f = 1, ch = getchar();
while (ch >= '0' && ch <= '9')sum = sum * 10 + ch - '0', ch = getchar();
if (f) sum = -sum;
return sum;
}
const int N = 102;
const int mod = 998244353;
int n1, n2;
vector<int> G1[N], G2[N];
int dp[N][N][N][N];
int id1[N], id2[N];
vector<int> bin1[N], bin2[N];
bool vis[N][N][N][N];
void Add(LL &x, LL y) {
x += y;
if (x >= mod)
x -= mod;
}
void DFS(int u, int dep, vector<int> *G, vector<int> *tt, int *ttt) {
tt[dep].push_back(u);
ttt[u] = tt[dep].size() - 1;
for (int v: G[u])
DFS(v, dep + 1, G, tt, ttt);
return;
}
int ct = 0;
int Solve(int nw1, int nw2, int lp1, int rp1, int lp2, int rp2) {
if (lp1 == -1 || lp2 == -1)return 1;
if (lp1 > rp1 || lp2 > rp2)return 1;
int l1 = bin1[nw1][lp1], r1 = bin1[nw1][rp1];
int l2 = bin2[nw2][lp2], r2 = bin2[nw2][rp2];
if (vis[l1][r1][l2][r2])
return dp[l1][r1][l2][r2];
LL res = 0;
++ct;
Add(res, Solve(nw1, nw2, lp1, rp1 - 1, lp2, rp2));
Add(res, Solve(nw1, nw2, lp1, rp1, lp2, rp2 - 1));
int ll = 0, rr = 0;
if (G2[r2].size())ll = id2[G2[r2][0]], rr = id2[G2[r2].back()];
else ll = rr = -1;
for (int i = 1; i <= rp1 - lp1 + 1; i++)
Add(res, 1ll * Solve(nw1, nw2, lp1, rp1 - i, lp2, rp2 - 1) * Solve(nw1, nw2 + 1,
rp1 - i + 1, rp1, ll, rr) % mod);
if (G1[r1].size())ll = id1[G1[r1][0]], rr = id1[G1[r1].back()];
else ll = rr = -1;
for (int i = 1; i <= rp2 - lp2 + 1; i++)
Add(res, 1ll * Solve(nw1, nw2, lp1, rp1 - 1, lp2, rp2 - i) * Solve(nw1 + 1, nw2,
ll, rr, rp2 - i + 1, rp2) % mod);
vis[l1][r1][l2][r2] = 1;
dp[l1][r1][l2][r2] = res;
return res;
}
int main() {
n1 = read();
for (int i = 2; i <= n1; i++)
G1[read()].push_back(i);
n2 = read();
for (int i = 2; i <= n2; i++)
G2[read()].push_back(i);
DFS(1, 0, G1, bin1, id1);
DFS(1, 0, G2, bin2, id2);
LL ans = 0;
if (G1[1].size()) {
Add(ans, Solve(1, 0, id1[G1[1][0]], id1[G1[1].back()], 0, 0));
} else Add(ans, 1);
if (G2[1].size()) {
Add(ans, Solve(0, 1, 0, 0, id2[G2[1][0]], id2[G2[1].back()]));
} else Add(ans, 1);
cout << ans;
return 0;
}
投递数字马力（杭州）信息技术有限公司等公司6个岗位 >