[心之碎片] - 20240816模拟赛
本帖最后由 柿子饼同学 于 2024-8-16 21:58 编辑总结与反思
ll = 1ll * int * int
取模要看好了, 不要把 ans 也乘了
一定要会打部分分!
A - 考虑条件的限制有什么巧方法水过去, 而不是一来就想高级算法
B - 中缀表达式求值要会
C - EXgcd 要更熟练一点
D - 计数题一定要有组合思想, 分类要细致, dfs 相关(做差, 栈, 树上差分) 之类的简单算法要先想, 树上路径其实是点
P7229 SLON
B 的 dfs 求中缀表达式
int dfs() {
int res = 0, cur = 1, temp = 0;
for (; s != ')' && s; pos++) {
if (s == '(') {
pos++;
temp = dfs();
} else if (isdigit(s) || s == 'x') {
temp = temp * 10 + mp];
temp %= m;
} else {
cur = 1ll * cur * temp % m;
temp = 0;
if (s != '*')
res = (res + cur + m) % m;
if (s == '-')
cur = -1;
if (s == '+')
cur = 1;
}
}
cur = 1ll * cur * temp % m;
return (res + cur + m) % m;
}
C - P4031 可做题2
没啥可说的, 之前想的是枚举最后的 , 后来发现可以数论分块...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, a1, l, r, k, p, m;
struct Matrix {
ll mat;
Matrix() { memset(mat, 0, sizeof(mat)); }
Matrix operator*(const Matrix& t) const {
Matrix temp;
for (int k = 0; k < 2; k++) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
temp.mat += mat * t.mat % p;
temp.mat %= p;
}
}
}
return temp;
}
} base;
ll Exgcd(ll a, ll b, ll& x, ll& y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll x1, y1;
ll d = Exgcd(b, a % b, x1, y1);
x = y1, y = x1 - a / b * y1;
return d;
}
Matrix qp(Matrix a, ll b) {
Matrix res;
for (int i = 0; i < 2; i++) res.mat = 1;
while (b) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("fib.in", "r", stdin);
freopen("fib.out", "w", stdout);
base.mat = base.mat = base.mat = 1;
cin >> T;
while (T--) {
cin >> a1 >> l >> r >> k >> p >> m;
a1 %= p;
auto cur = qp(base, k - 1);
ll ka1 = a1 * cur.mat % p;
ll ka2 = cur.mat % p;
ll gcd = __gcd(ka2, p);
// ak = ka1 + ka2*a2
// 得到不定方程:
// ka2*x + p*y = m - ka1
// A*x + B*y = C
if ((m - ka1) % gcd) {
cout << "0\n";
continue;
}
ll A = ka2 / gcd, B = p / gcd, C = (m - ka1) / gcd;
ll x, y, d;
d = Exgcd(A, B, x, y);
x = (x * C % B + B) % B;
// x 是最小正整数解, x*a2 + ka1 = ak
if (x > r) {
cout << "0\n";
} else {
if (l <= x) {
cout << (r - x) / B + 1 << '\n';
} else {
cout << (r - x) / B - (l - 1 - x) / B << '\n';
}
}
}
return 0;
}
D - 树上路径交
知知有一棵n个节点的树，根节点为1，树上每条边长度为1，定义G路径是连接祖先节点和其子孙节点的路径。
她想要知道有多少对路径的路径交是长度在 之间的G路径。
首先想到枚举交的部分, 然后一上一下每个点求一个不在同一个子树里取两个点的方案数
然后这里相当于利用 dfs 栈批量处理了
typedef long long ll;
const int N = 3e6 + 5;
const ll P = 1e9 + 7;
int n, l, r;
// up, 除了 i 这个子树和她的父节点, 在剩余子树中选择两个点使得不在同一个子树的方案数
// dn, i 这个子树, 选择 2 个点使得不在同一子树的方案数(不包括 i)
ll up, dn, dep, siz, ans;
vector<int> e;
void dfs0(int u) {
siz = 1;
for (auto v : e) {
dfs0(v);
siz += siz;
}
ll temp = 1ll * n * (n - 1) / 2;
dn = 1ll * siz * (siz - 1) / 2;
for (auto v : e) {
// 强制减去两个点都在 v 子树的方案
dn -= siz * (siz - 1) / 2;
temp -= siz * (siz - 1) / 2;
}
dn %= P;
temp -= (n - siz) * (n - siz - 1) / 2;
for (auto v : e) {
// 上面已经减过重复情况了, 这里只需要减掉一个点在 v 子树内的方案数
up = temp - (n - siz) * siz;
}
}
ll stk;
int top;
void dfs(int u) {
if (u != 1) {
top++;
stk = (stk + up) % P;
if (top >= l) {
// sum 是指这一区间内的点上方选取 2 个不在同子树的点的方案数
ll sum = ((stk - stk) % P + P) % P;
// u 的子节点和这些点的上方节点, *2 是因为有 2 种情况, a, b -- c, d , a 可以选 c 也可以选 d
ans = (ans + 2 * sum % P * dn % P) % P;
// u 的子节点和这些点(相同结尾 都是在这个区间内的点)
ans = (ans + (min(top, r) - l + 1) * dn % P) % P;
// u 自己和这些点(相同起点 u)
ans = (ans + sum) % P;
}
}
for (auto v : e) {
dfs(v);
}
if (u != 1) {
top--;
}
} 加油 {:10_256:}{:10_256:} {:7_113:} {:10_277:}{:10_243:} 日常膜拜 {:10_277:} 👌 膜拜日常/orz 我看的是高手成长阶梯啊！{:10_254:} 谢谢 {:10_254:}good
页:
[1]