intgetId(int y, int m, int d){ if (m < 3) {y --; m += 12;} return365 * y + y / 4 - y / 100 + y / 400 + (153 * (m - 3) + 2) / 5 + d - 307; } vector<int> date(int id){ int x = id + 1789995, n, i, j, y, m, d; n = 4 * x / 146097; x -= (146097 * n + 3) / 4; i = (4000 * (x + 1)) / 1461001; x -= 1461 * i / 4 - 31; j = 80 * x / 2447; d = x - 2447 * j / 80; x = j / 11; m = j + 2 - 12 * x; y = 100 * (n - 49) + i + x; return vector<int>({y, m, d}); }
voidwork(){ int M, y, m, d; scanf("%d%d%d%d", &M, &y, &m, &d); int id = getId(y, m, d); int l = 0, r = sqrt(2e9); while (l < r) { int mid = (l + r) / 2; int v = M + (0 + mid) * (mid + 1) / 2; if (v >= 1000000000) r = mid; else l = mid + 1; } id += l; auto ret = date(id); printf("%d %d %d\n", ret[0], ret[1], ret[2]); }
intmain(){ int T; scanf("%d", &T); while (T--) work(); }
C Counting K-ary Palindromes
T122395
确认过眼神，是不会做的题。流下了数学不好的眼泪。
题目概述
求k进制下能被p整除的所有的长度为n的回文数字的个数模998244353的值。
1≤n≤1e18
2≤k≤16
2≤p≤1000且p为质数
题解
这题没怎么听懂。
首先考虑p 与k 不互素的情况。这种情况下，整除只与最后一位有关，且有kp− 1 种取法，其余位任取。注意k = p 时答案为[n = 1]，可能会导致部分没有特判的程序挂掉。现在考虑(p, k) = 1 的情况。考虑暴力：dpi,j 表示前i 位和后i 位填好了，其余位取0 时mod p = j的方案数。更新一位的复杂度是O(kp) 的，总复杂度是O(nkp) 的。考虑优化，由费马小定理，ki mod p 存在长度为p − 1 循环节，因此ki + kn−i−1 mod p 也有长度为p − 1 的循环节。按p − 1 分块后，每块的贡献是相同的，而块的背包合并可以通过类似多项式乘法的循环卷积来实现，因此就可以快速幂了。
预处理一个块和处理边缘的零散部分的复杂度是O(kp2), 一次块的暴力卷积是O(p2) 的，因此总复杂度为O(kp2 + p2(log n − log p))。
标程使用vector 实现，不开O2 也只跑了一秒，应该是不卡常的。
#include<bits/stdc++.h> usingnamespace std; typedeflonglong LL; typedef pair<int, int> pii; #define read(a) scanf("%d", &a) #define x first #define y second
#define MOD 998244353
LL power(LL x, LL y, LL z){ LL ret = 1; for ( x %= z; y; y >>= 1) { if (y & 1) ret = ret * x % z; x = x * x % z; } return ret; }
LL solve(LL n, LL a, LL b, LL m){ if (b == 0) return n * (a / m); if (a >= m) return n * (a / m) + solve(n, a % m, b, m); if (b >= m) return (n - 1) * n / 2 * (b / m) + solve(n, a, b % m, m); returnsolve((a + b * n) / m, (a + b * n) % m, m, b); }
LL A, B, K;
voidwork(){ scanf("%lld%lld%lld", &A, &B, &K); LL l = 1, r = (double)A * B > 3e18 ? 2e18 + 10 : min(LL(2e18) + 10, A * B - 1); assert(double(A - 1) * (B - 1) / 2 >= K); while (l < r) { LL mid = (l + r) / 2; LL n = mid / A + 1, m = B, a = mid - (n - 1) * A + B, b = A; LL tot = solve(n, a, b, m) - 1; LL cnt = mid - tot; if (cnt >= K) r = mid; else l = mid + 1; } printf("%lld\n", l); }
intmain(){ int T; scanf("%d", &T); while (T--) work(); }
w + t 相同的数据都没有本质区别，因此可以转化为r′ = 0,w′ = w + t 的题目来做。无论以什么角度射入圆，我们都可以把圆旋转到激光为竖直的情况来开，因此问题就转化为用一个可水平平移的无限长w + t 宽的长方形切一个半径为s 的圆能切下的最大边长。求导可知相切时边长取最大值，因此计算相应弧长即可。
int n, tcnt; int a[N], rt[N], dep[N]; vector <int> E[N]; LL sc[N], delta; int curdep;
intMerge(int x, int y, int l, int r){ if (!y) return x; if (!x) return y; if (l == r) { delta += t[x].dep * t[y].cnt + t[y].dep * t[x].cnt - 2ll * curdep * t[x].cnt * t[y].cnt; t[x].dep += t[y].dep; t[x].cnt += t[y].cnt; } else { int mid = (l + r) / 2; t[x].l = Merge(t[x].l, t[y].l, l, mid); t[x].r = Merge(t[x].r, t[y].r, mid + 1, r); } return x; }
intinit(int p, int l, int r){ int x = ++tcnt; if (l < r) { int mid = (l + r) / 2; if (p <= mid) t[x].l = init(p, l, mid); else t[x].r = init(p, mid + 1, r); } else t[x].dep = curdep, t[x].cnt = 1; return x; }
voiddfs(int x, int fa){ curdep = dep[x]; rt[x] = init(a[x], 1, n); for (auto v : E[x]) if (v != fa){ dep[v] = dep[x] + 1; dfs(v, x); sc[x] += sc[v]; delta = 0; curdep = dep[x]; rt[x] = Merge(rt[x], rt[v], 1, n); sc[x] += delta; } }
intmain(){ scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); E[u].push_back(v); E[v].push_back(u); } dfs(1, -1); for (int i = 1; i <= n; i++) printf("%lld ", sc[i]); }
