T1 锻造 forging
题目描述
“欢迎啊,老朋友。”
一阵寒暄过后,厂长带他们参观了厂子四周,并给他们讲锻造的流程。
“我们这里的武器分成若干的等级,等级越高武器就越厉害,并且对每一等级的武器都有两种属性值 b 和 c,但是我们初始只能花\(a\)个金币来生产\(1\)把\(0\)级剑......”
“所以你们厂子怎么这么垃圾啊,不能一下子就造出来\(999\)级的武器吗?”勇者不耐烦的打断了厂长的话。
“别着急,还没开始讲锻造呢......那我们举例你手中有一把\(x\)级武器和一把\(y\)级武器\((y = max(x − 1, 0))\),我们令锻造附加值\(k = min(c_x , b_y )\),则你有 \(\frac{k}{c_x}\) 的概率将两把武器融合成一把\(x + 1\)级的武器。”
“......但是,锻造不是一帆风顺的,你同样有 \(1−\frac{k}{c_x}\) 的概率将两把武器融合成一把\(max(x − 1, 0)\) 级的武器......”
勇者听完后暗暗思忖,他知道厂长一定又想借此机会坑骗他的零花钱,于是求助这个村最聪明的智者——你,来告诉他,想要强化出一把\(n\)级的武器,其期望花费为多少?
由于勇者不精通高精度小数,所以你只需要将答案对\(998244353\)取模即可。
分析
期望DP+线性逆元。
设\(f[i]\)表示打造成等级为\(i\)的武器的期望花费，那么考虑转移：
\[f[i]=f[i-1]+f[i-2]+P\times (f[i] - f[i - 2])
\]
\]
其中,\(P=(1-\frac{k}{c_{i-1}})\)，为打造失败的概率。
这个方程表示，若打造成功，那么花费即为\(f[i-1]+f[i-2]\)，若未成功，那么我们就有了一件等级为\(i-2\)的武器，所以格外的花费就应该是\(f[i]-f[i-2]\)，然后整理可得：
\[f[i]=\frac{c_{i-1}}{k} \times f[i-1]+f[i-2]
\]
\]
然后再加个线性求逆元就行了。
时间复杂度\(O(n)\)。
#include<cstdio>
#include<cstdlib>
#define ll long long
#define Re register
const int N = 1e7 + 5;
const int P = 998244353;
inline int read() {
int f = 1, x = 0; char ch;
do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0' || ch > '9');
do {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
return f * x;
}
inline int min(int a, int b) { return a < b ? a : b; }
inline void hand_in() {
freopen("forging.in", "r", stdin);
freopen("forging.out", "w", stdout);
}
int n, a, bx, by, cx, cy, p, b[N], c[N], inv[N], f[N];
int main() {
hand_in();
inv[0] = inv[1] = 1;
for (Re int i = 2;i <= 10000000; ++i) {
inv[i] = (ll)(P - (P / i)) * (ll)inv[P % i] % P;
}
n = read(), a = read(), bx = read(), by = read(), cx = read(), cy = read(), p = read();
b[0] = by + 1, c[0] = cy + 1;
for (Re int i = 1;i < n; ++i) {
b[i] = ((ll)b[i - 1] * bx + by) % p + 1;
c[i] = ((ll)c[i - 1] * cx + cy) % p + 1;
}
f[0] = a, f[1] = ((ll)(((ll)c[0] * inv[min(c[0], b[0])]) % P + 1) * f[0]) % P;
for (int i = 2;i <= n; ++i) {
f[i] =((((ll)c[i - 1] * inv[min(c[i - 1], b[i - 2])]) % P * f[i - 1]) % P + f[i - 2]) % P;
}
printf("%d\n", f[n]);
return 0;
}
T2 整除 division
题目大意
求解\(x^m\equiv x (mod p_1\times p_2\times \dots \times p_c)\)在\([1, p_1\times p_2\times \dots \times p_c]\)区间取值间的个数。
分析
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define Re register
const int N = 1e5 + 5;
const int P = 998244353;
inline int read() {
int f = 1, x = 0; char ch;
do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0' || ch > '9');
do {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
return f * x;
}
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a < b ? b : a; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
inline void hand_in() {
freopen("division.in", "r", stdin);
freopen("division.out", "w", stdout);
}
inline ll mi(ll a, ll b, ll p) {
ll ret = 1;
while (b) {
if (b & 1) ret *= a, ret %= p;
a *= a, a %= p;
b >>= 1;
}
return ret;
}
int prim[N], vis[N], tot;
inline void Prim() {
vis[1] = 1;
for (int i = 2;i <= 10000; ++i) {
if (!vis[i]) prim[++tot] = i;
for (int j = 1;j <= tot; ++j) {
if (prim[j] * i > 10000) break;
vis[prim[j] * i] = 1;
if (!(i % prim[j])) break;
}
}
}
int pw[N];
inline int calc(int m, int p) {
pw[1] = 1, pw[p] = 0;
for (int i = 2;i < p; ++i) {
if (!vis[i]) pw[i] = mi(i, m, p);
for (int j = 1;prim[j] <= i; ++j) {
if (prim[j] * i > p) break;
pw[prim[j] * i] = pw[prim[j]] * pw[i];
if (!(i % prim[j])) break;
}
}
int ret = 1;
for (int i = 1;i < p; ++i) ret += (pw[i] == i);
return ret;
}
inline ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
int id, T, c, m, ans;
int main() {
hand_in();
id = read();
T = read();
Prim();
while (T --) {
c = read(), m = read();
ans = 1;
for (int i = 1, p;i <= c; ++i) {
p = read();
// ans = ((ll)ans * calc(m, p)) % P;
ans = ((ll)ans * (gcd(m - 1, p - 1) + 1)) % P;
}
printf("%d\n", ans);
}
return 0;
}
T3 欠钱 money
分析
将有向有根树改成无向无根树存下来,树上倍增+启发式合并,每次合并时暴力重构倍增数组,倍增数组多存一个到\(2^i\)的父节点的方向,全向上为\(1\),全向下为\(2\),两个都有为\(3\),询问时判断两个点的方向关系就可以了。
时间复杂度\(O(nlog^2n + mlogn)\)。
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define Re register
const int N = 1e5 + 5;
const int INF = 0x7fffffff;
const int BASE = 16;
inline int read() {
int f = 1, x = 0; char ch;
do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0' || ch > '9');
do {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
return f * x;
}
inline void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
inline void hand_in() {
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
}
int n, m, last;
struct Graph {
int to[N << 1], nxt[N << 1], w[N << 1], dir[N << 1], head[N], cnt;
inline void add(int x, int y, int z, int d) {
++cnt;
to[cnt] = y, w[cnt] = z, dir[cnt] = d, nxt[cnt] = head[x], head[x] = cnt;
}
}G;
int f[N], sz[N];
int anc[N][BASE + 1], mn[N][BASE + 1], dir[N][BASE + 1], dep[N], up[N];
inline void init() {for (Re int i = 1;i <= n; ++i) f[i] = i, sz[i] = 1, up[i] = 1; }
inline void dfs(int u, int fa, int rt) {
f[u] = rt, dep[u] = dep[fa] + 1;
for (Re int i = 1;i <= BASE; ++i) {
anc[u][i] = anc[anc[u][i - 1]][i - 1];
mn[u][i] = min(mn[u][i - 1], mn[anc[u][i - 1]][i - 1]);
dir[u][i] = (dir[u][i - 1] | dir[anc[u][i - 1]][i - 1]);
}
for (Re int i = G.head[u], v;i;i = G.nxt[i]) {
v = G.to[i];
if (v == fa) continue;
anc[v][0] = u;
mn[v][0] = G.w[i];
dir[v][0] = 3 ^ G.dir[i];
dfs(v, u, rt);
}
}
inline void merge(int u, int v, int w) {
G.add(u, v, w, 1), G.add(v, u, w, 2);
int dirs = sz[f[u]] < sz[f[v]] ? 1 : 2;
if (dirs == 2) swap(u, v);
anc[u][0] = v, mn[u][0] = w, dir[u][0] = dirs;
sz[f[v]] += sz[f[u]];
dfs(u, v, f[v]);
}
inline int ask(int u, int v) {
if (f[u] != f[v]) return 0;
int dirs = 0, res = INF;
if (dep[u] < dep[v]) swap(u, v), dirs = 3;
for (int i = BASE; i >= 0; --i) {
if (dep[u] - (1 << i) >= dep[v]) {
if (dir[u][i] != (1 ^ dirs)) return 0;
res = min(res, mn[u][i]);
u = anc[u][i];
}
}
if (u == v) return res;
for (int i = BASE;i >= 0; --i) {
if (anc[u][i] != anc[v][i]) {
if (dir[u][i] != (1 ^ dirs) || dir[v][i] != (2 ^ dirs)) return 0;
res = min(res, min(mn[u][i], mn[v][i]));
u = anc[u][i], v = anc[v][i];
}
}
if (dir[u][0] != (1 ^ dirs) || dir[v][0] != (2 ^ dirs)) return 0;
res = min(res, min(mn[u][0], mn[v][0]));
return res;
}
int main() {
hand_in();
n = read(), m = read(), init();
for (Re int i = 1, op, a, b, c;i <= m; ++i) {
op = read(), a = read(), b = read();
a = (a + last) % n + 1;
b = (b + last) % n + 1;
if (!op) {
c = read();
c = (c + last) % n + 1;
merge(a, b, c);
}
else {
write(last = ask(a, b));
puts("");
}
}
return 0;
}