ZOJ Monthly, January 2015 | ||
---|---|---|
A | Nuclear Power Plant | 8.33% (4/48) |
B | Cards | 15.47% (26/168) |
C | Cirno's Perfect Math Class | 25.00% (2/8) |
D | Unlucky Right Triangle | 25.00% (2/8) |
E | Easy Task | 37.34% (90/241) |
F | Fixed Point | 35.48% (11/31) |
G | GCD Reduce | 19.46% (66/339) |
H | Collect Chars | 5.61% (11/196) |
I | Ginomial Theorem | 0.00% (0/2) |
J | You need Medicine | 75.00% (3/4) |
这次比赛有好多数论题,感觉ZOJ月赛就快变成专题赛了。。嘛。。专题赛也有专题赛的好处啦。
先写好题目大意,题解之后慢慢补。。。
upd: 妈呀, 拖延了两个月才写题解.. 多不好意思.
有一棵树,记\(S(u) = \sum_{v=1}^{n}{d(u,v)^k} \mod 10^8+7\),其中\(d(u,v)\)为结点\(u,v\)之间的距离。求\(S(u)\)的最小值.
数据规模:\(1 \le n \le 10^5, 0 \le k \le 10\)
经典的两边dfs可以解决这题, 我们先求出以某个点为根的子树的值, 然后第二遍dfs的时候把父亲的答案累计过来. 具体实现参看程序.
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 100000 + 10; const int MAXK = 15, MOD = 100000007; vector<int> G[MAXN], W[MAXN]; int C[MAXK][MAXK]; int dp[MAXN][MAXK], ret[MAXN][MAXK]; int N, K; void dfs1(int u, int f) { memset(dp[u], 0, sizeof(dp[u])); dp[u][0] = 1; for (int i = 0; i < (int)G[u].size(); ++ i) { int v = G[u][i], w = W[u][i]; assert(w >= 0 && w < MOD); if (v == f) continue; dfs1(v, u); for (int a = 0; a <= K; ++ a) { int ww = 1; for (int b = 0; b <= a; ++ b) { dp[u][a] += (LL)C[a][b] * dp[v][a - b] % MOD * ww % MOD; dp[u][a] %= MOD; ww = (LL)ww * w % MOD; assert(dp[u][a] >= 0 && dp[u][a] < MOD); } } } } int tmp[MAXK]; void dfs2(int u, int f, int w) { memcpy(ret[u], dp[u], sizeof(dp[u])); if (f != -1) { for (int i = 0; i <= K; ++ i) { tmp[i] = 0; int ww = 1; for (int j = 0; j <= i; ++ j) { tmp[i] += (LL)C[i][j] * dp[u][i - j] % MOD * ww % MOD; tmp[i] %= MOD; ww = (LL)ww * w % MOD; } } ret[u][0] = N; for (int i = 1; i <= K; ++ i) { int ww = 1; for (int j = i; j >= 0; -- j) { assert(ret[f][j] >= 0 && ret[f][j] < MOD); assert(tmp[j] >= 0 && tmp[j] < MOD); int now = (ret[f][j] - tmp[j] + MOD) % MOD; assert(now >= 0 && now < MOD); ret[u][i] += (LL)C[i][j] * now % MOD * ww % MOD; ret[u][i] %= MOD; ww = (LL)ww * w % MOD; } } } for (int i = 0, v; i < (int)G[u].size(); ++ i) { v = G[u][i], w = W[u][i]; if (v == f) continue; dfs2(v, u, w); } } int main() { for (int i = 0; i < MAXK; ++ i) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; ++ j) { C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; C[i][j] %= MOD; } } while (scanf("%d%d", &N, &K) == 2) { for (int i = 0; i < N; ++ i) G[i].clear(), W[i].clear(); for (int i = 1; i < N; ++ i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); w %= MOD; if (w < 0) w += MOD; G[u].push_back(v); W[u].push_back(w); G[v].push_back(u); W[v].push_back(w); } dfs1(0, -1); dfs2(0, -1, -1); int ans = MOD; for (int i = 0; i < N; ++ i) { if (ret[i][K] < ans) ans = ret[i][K]; } if (K == 0) -- ans; printf("%d\n", ans); } return 0; }
52张扑克牌(A,2~10,J,Q,K各4张),桌子上已经有一些扑克牌排成一排,问剩下的扑克牌有多少种排列方式满足字典序小于桌上的牌。
枚举前缀的长度, 然后排列组合计算一下.
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MOD = 1e9 + 7; int fac[100], inv[100]; LL pow_mod(LL a, LL n, LL p) { LL ret = 1; for (a % p; n; n >>= 1) { if (n & 1) ret = ret * a % p; a = a * a % p; } return ret; } int cnt[13]; int gao() { int tot = 0; for (int i = 0; i < 13; ++ i) tot += cnt[i]; int ret = fac[tot]; for (int i = 0; i < 13; ++ i) ret = (LL)ret * inv[cnt[i]] % MOD; return ret; } int main() { char s[1000]; for (int i = 0; i < 100; ++ i) { fac[i] = i ? (LL)i * fac[i - 1] % MOD : 1; inv[i] = pow_mod(fac[i], MOD - 2, MOD); } while (scanf("%s", s) == 1) { int m = 0, a[52], len = strlen(s); for (int i = 0; i < len; ) { if (s[i] == 'A') a[m ++] = 0, ++ i; else if (s[i] == '1') a[m ++] = 9, i += 2; else if (s[i] == 'J') a[m ++] = 10, ++ i; else if (s[i] == 'Q') a[m ++] = 11, ++ i; else if (s[i] == 'K') a[m ++] = 12, ++ i; else if (s[i] >= '2' && s[i] <= '9') a[m ++] = s[i] - '1', ++ i; else assert(false); } assert(m >= 1 && m <= 52); for (int i = 0; i < 13; ++ i) cnt[i] = 4; for (int i = 0; i < m; ++ i) -- cnt[a[i]]; for (int i = 0; i < 13; ++ i) { assert(cnt[i] >= 0 && cnt[i] <= 4); } int ret = 0, rest = 52 - m; for (int i = 0; i < m; ++ i) { for (int c = 0; c < a[i]; ++ c) { if (cnt[c]) { -- cnt[c]; ret += gao(); if (ret >= MOD) ret -= MOD; ++ cnt[c]; } } -- cnt[a[i]]; -- rest; if (cnt[a[i]] < 0) break; else { if (rest == 0 && i + 1 < m) ++ ret; } } printf("%d\n", ret % MOD); } return 0; }
给你一个数\(n\),问有多少数\(k\)满足\(\binom{n}{k} \equiv 0 \mod 9\)。
数据规模:\(0 \le n \le 10^{1000}\)
考虑lucas定理, $\binom{N}{M} \equiv \prod\binom{n_i}{m_i} \mod 3$
若$\binom{N}{M}=0$那么至少存在一个$n_i,m_i$满足$n_i < m_i$
也就是说在三进制下$N,M$做减法不发生借位. 于是类似的我们可以猜想如果减法恰好产生两次借位, 那么这个组合数就是9的倍数.
然后用容斥做n+1-不发生借位的-只发生一次借位的.
import java.math.*; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); for (int T = cin.nextInt(); T > 0; -- T) { BigInteger N = cin.nextBigInteger(); BigInteger Three = BigInteger.valueOf(3); int digit[] = new int[3000]; int len = 0; BigInteger ret = N.add(BigInteger.ONE); while (!N.equals(BigInteger.ZERO)) { digit[len ++] = (int)N.mod(Three).longValue(); N = N.divide(Three); } BigInteger S[] = new BigInteger[len + 1]; S[len] = BigInteger.ONE; for (int i = len - 1; i >= 0; -- i) { S[i] = S[i + 1].multiply(BigInteger.valueOf(digit[i] + 1)); } ret = ret.subtract(S[0]); BigInteger tmp = BigInteger.ONE; for (int i = 0; i < len - 1; ++ i) { int sum = 0; if (digit[i + 1] == 1 && digit[i] == 0) sum = 2; if (digit[i + 1] == 1 && digit[i] == 1) sum = 1; if (digit[i + 1] == 2 && digit[i] == 0) sum = 4; if (digit[i + 1] == 2 && digit[i] == 1) sum = 2; ret = ret.subtract(S[i + 2].multiply(tmp).multiply(BigInteger.valueOf(sum))); tmp = tmp.multiply(BigInteger.valueOf(digit[i] + 1)); } System.out.println(ret); } } }
给你一个数\(n\),有多少直角三角形\((a,b,c\sqrt{89})\),其中\(a^2+b^2=89c^2, c \le n\)。求出所有这些三角形的平均周长
数据规模:\(1 \le n \le 2 \times 10^8\)
我们很容易查到关于勾股数的一个公式, 然后类似的对于这道题目我们也可以得到一个公式, 然后利用公式枚举所有可行的三角形.
设$(a,b,c)$为两两互质的数对, 并且$a^2+b^2=89c^2$, 然后有$(a,b,c)=(16uv+5(u^2-v^2), 10uv-8(u^2-v^2), u^2+v^2)$, 其中$u,v$一奇一偶并且互质. 用Stern–Brocot tree枚举$u,v$.
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1000000 + 10; LL S1, S2, S3, g; struct Node { int A, B, C, D; } S[MAXN]; string tostring(LL N) { char buf[1000]; sprintf(buf, "%lld", N); return (string)buf; } string blank(int n) { string ret = ""; for (int i = 0; i < n; ++ i) ret += " "; return ret; } string dash(int n) { string ret = ""; for (int i = 0; i < n; ++ i) ret += "-"; return ret; } int main() { int N, top; while (scanf("%d", &N) == 1) { S1 = S2 = S3 = top = 0; // deal with c = 1 S3 = N; S1 = (LL)N * (N + 1) * 13 / 2; S2 = (LL)N * (N + 1) / 2; S[++ top] = (Node){0, 1, 1, 1}; while (top) { int u = S[top].A + S[top].B, v = S[top].C + S[top].D; if (u * u + v * v > N) { -- top; continue; } if ((u ^ v) & 1) { int e = u * v, f = v * v - u * u, c = v * v + u * u; int a = e * 16 + f * 5, b = abs(e * 10 - f * 8); LL g = N / c, q = g * (g + 1) >> 1; if (a % 89) { S3 += g; S1 += a * q + b * q; S2 += c * q; } a = abs(e * 16 - f * 5), b = e * 10 + f * 8; if (a % 89) { S3 += g; S1 += a * q + b * q; S2 += c * q; } } S[top + 1] = (Node){S[top].A, S[top].C, u, v}; S[top].A = u; S[top].C = v; ++ top; } LL I1 = S1 / S3, N1 = S1 % S3, D1 = S3; LL I2 = S2 / S3, N2 = S2 % S3, D2 = S3; g = max(1ll, __gcd(N1, D1)); N1 /= g, D1 /= g; g = max(1ll, __gcd(N2, D2)), N2 /= g, D2 /= g; string s[3] = {"", "", ""}; s[0] += blank(tostring(I1).size()); s[1] += tostring(I1); s[2] += blank(tostring(I1).size()); if (N1) { s[0] += blank(tostring(D1).size() - tostring(N1).size()) + tostring(N1); s[1] += dash(tostring(D1).size()); s[2] += tostring(D1); } s[0] += " ", s[1] += " + ", s[2] += " "; if (I2 != 1 || (I2 == 1 && N1)) { s[0] += blank(tostring(I2).size()); s[1] += tostring(I2); s[2] += blank(tostring(I2).size()); if (N2) { s[0] += blank(tostring(D2).size() - tostring(N2).size()) + tostring(N2); s[1] += dash(tostring(D2).size()); s[2] += tostring(D2); } s[0] += " ", s[1] += " x ", s[2] += " "; } s[0] += " __", s[1] += "V89", s[2] += " "; s[0] = "*" + s[0] + "*"; s[1] = "*" + s[1] + "*"; s[2] = "*" + s[2] + "*"; for (int i = 0; i < (int)s[0].size(); ++ i) cout << "*"; cout << endl; cout << s[0] << endl; cout << s[1] << endl; cout << s[2] << endl; for (int i = 0; i < (int)s[0].size(); ++ i) cout << "*"; cout << endl; cout << endl; } return 0; }
给你一个数组\(a_1, a_2, \dots, a_n\),每次取出最大值\(x\),取出最小值\(y\),把\(x,y\)替换成\(x-y\),问最终这个数组会变成什么数。
数据规模:\(1 \le n \le 10, |a_i| \le 10^5\)
暴力模拟即可.
#include <bits/stdc++.h> using namespace std; int A[20], N; int main() { int T; scanf("%d", &T); while (T --) { scanf("%d", &N); for (int i = 0; i < N; ++ i) { scanf("%d", A + i); } while (1) { int i = 0, j = 0; for (int k = 0; k < N; ++ k) { if (A[k] > A[i]) i = k; if (A[k] < A[j]) j = k; } if (A[i] == A[j]) break; int t = A[i] - A[j]; A[i] = A[j] = t; } printf("%d\n", A[0]); } return 0; }
给你三个函数\(A(x) = c \wedge x, E(x) = c \oplus x, O(x) = c \vee x\),然后问你对于每个函数有多少\(x\)满足:
- \(L \le x \le R\)
- \(x\)二进制表示中1的个数和0(包括前导0)的个数之差小于等于\(k\)
数据规模:\(0 \le L \le R < 2^{32}, 0 \le c < 2^{32}, 0 \le k \le 32\)
很扎实的数位dp, 将区间问题转化为前缀相减, 注意要用long long, 应该会爆unsigned int.
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL dp[40][40][2]; LL L, R, C, N; int K; LL solve1(int i, int k, int e) { // AND if (dp[i][k][e] != -1) return dp[i][k][e]; if (i == 33) return dp[i][k][e] = (abs(32 - 2 * k) <= K); int pos = 32 - i, bit = (N >> pos) & 1; int low = 0, upp = e ? 1 : bit; LL ret = 0; if (((C >> pos) & 1) == 0) upp = 0; for (int d = low; d <= upp; ++ d) { ret += solve1(i + 1, k + d, e | (d < bit)); } return dp[i][k][e] = ret; } LL gao1(LL n) { // AND if (n < 0) return 0; memset(dp, -1, sizeof(dp)); N = n; return solve1(0, 0, 0); } LL solve2(int i, int k, int e) { // XOR if (dp[i][k][e] != -1) return dp[i][k][e]; if (i == 33) return dp[i][k][e] = (abs(32 - 2 * k) <= K); int pos = 32 - i, bit = (N >> pos) & 1; int low = 0, upp = e ? 1 : bit; LL ret = 0; for (int d = low; d <= upp; ++ d) { ret += solve2(i + 1, k + d, e | (d < bit)); } return dp[i][k][e] = ret; } LL gao2(LL n) { // XOR if (C != 0 || n < 0) return 0; memset(dp, -1, sizeof(dp)); N = n; return solve2(0, 0, 0); } LL solve3(int i, int k, int e) { // OR if (dp[i][k][e] != -1) return dp[i][k][e]; if (i == 33) return dp[i][k][e] = (abs(32 - k * 2) <= K); int pos = 32 - i, bit = (N >> pos) & 1; int low = 0, upp = e ? 1 : bit; LL ret = 0; if (((C >> pos) & 1) == 1) low = 1; for (int d = low; d <= upp; ++ d) { ret += solve3(i + 1, k + d, e | (d < bit)); } return dp[i][k][e] = ret; } LL gao3(LL n) { // OR if (n < 0) return 0; memset(dp, -1, sizeof(dp)); N = n; return solve3(0, 0, 0); } int main() { int T; scanf("%d", &T); for (int cas = 1; cas <= T; ++ cas) { scanf("%lld%lld%lld%d", &L, &R, &C, &K); LL ret1 = gao1(R) - gao1(L - 1); LL ret2 = gao2(R) - gao2(L - 1); LL ret3 = gao3(R) - gao3(L - 1); printf("Case %d: %lld %lld %lld\n", cas, ret1, ret2, ret3); } return 0; }
给你一列数\(a_1,a_2,\dots,a_n\),每次可以选择两个数\(a_i,a_j\),把他们都变成\(\gcd(a_i,a_j)\)。要求用不超过\(5n\)次操作把所有数变成1,或者输出-1表示不行。
数据规模:\(1 \le N \le 10^5, 1 \le a_i \le 10^9\)
先求出所有数的gcd, 判断是否等于1, 然后用1和所有数求一遍gcd就好了.
#include <bits/stdc++.h> using namespace std; const int MAXN = 100000 + 10; int A[MAXN], N; bool check() { int ret = A[1]; for (int i = 2; i <= N; ++ i) ret = __gcd(ret, A[i]); return (ret == 1); } int main() { int cas = 0; while (scanf("%d", &N) == 1) { assert(1 <= N && N <= 100000); for (int i = 1; i <= N; ++ i) { scanf("%d", A + i); assert(1 <= A[i] && A[i] <= 1000000000); } printf("Case %d: ", ++ cas); if (check()) { printf("%d\n", 2 * N - 2); for (int i = 1; i < N; ++ i) printf("%d %d\n", i, i + 1); for (int i = 1; i < N; ++ i) printf("%d %d\n", i, N); } else puts("-1"); puts(""); } return 0; }
有一个\(n \times m\)的格子,每个格子上有字母(A-Z),障碍物(#),没东西(.)。给你\(q\)个字符串,现在你要从某个点出发。如果某个格子上有字母你可以加到你手上的字符串末尾(一开始是空串)。如果那\(q\)个字符串其中一个是你手中字符串的子串,那么你就成功了。问最少成功步数,或者判定无法达到。
数据规模:\(1 \le n, m \le 20, 1 \le q \le 200\)
有两个做法自动机上dp, 或者直接暴力搞.
我们每个字符串单独处理,假设当前处理S,长度为L,队列中的字符串为Q
注意到如果S出现在队列字符串Q中,那么S必定是Q的后缀,并且S只是Q的后缀(否则Q的长度可以变得更小)
假设起点是(sx, sy),那么存在一个位置(sx', sy'),从(sx', sy')开始走L步能够达成S
于是Q的长度必定是L + |sx - sx'| + |sy - sy'|,我们要Q长度最小,只要这个|sx - sx'| + |sy - sy'|最小
然后这个|sx - sx'| + |sy - sy'|最小可以用dp搞定
设dp[x][y][l]表示当前点在(x,y),已经得到子串S[1..l]的最小步数
转移很简单,就不说了,时间复杂度O(NML)
这个字符串S对应的最少步数就是L + min{dp[x][y][L]}
于是我们只要每个字符串都按上述方法处理就好了,时间复杂度O(NM ∑len)
#include <bits/stdc++.h> using namespace std; const int SIZE = 30, MAXN = 60; const int inf = 1e9; const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; char grid[SIZE][SIZE], word[MAXN]; bool vis[SIZE][SIZE]; int dp[2][SIZE][SIZE], dis[SIZE][SIZE]; int N, M, sx, sy; struct Node { int x, y; Node() {} Node(int x, int y) : x(x), y(y) {} }; inline bool fit(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M; } void spfa(queue<Node> &Q, int dp[SIZE][SIZE]) { while (!Q.empty()) { int x = Q.front().x, y = Q.front().y; Q.pop(); vis[x][y] = false; for (int k = 0; k < 4; ++ k) { int xx = x + dx[k], yy = y + dy[k]; if (!fit(xx, yy) || grid[xx][yy] != '.') continue; if (dp[xx][yy] > dp[x][y] + 1) { dp[xx][yy] = dp[x][y] + 1; if (!vis[xx][yy]) { vis[xx][yy] = true; Q.push(Node(xx, yy)); } } } } } void bfs() { queue<Node> Q; for (int x = 0; x < N; ++ x) for (int y = 0; y < M; ++ y) dis[x][y] = inf; Q.push(Node(sx, sy)); dis[sx][sy] = 0; while (!Q.empty()) { int x = Q.front().x, y = Q.front().y; Q.pop(); for (int k = 0; k < 4; ++ k) { int xx = x + dx[k], yy = y + dy[k]; if (!fit(xx, yy) || grid[xx][yy] == '#') continue; if (dis[xx][yy] == inf) { dis[xx][yy] = dis[x][y] + 1; Q.push(Node(xx, yy)); } } } } int solve(char word[]) { int L = strlen(word), now = 0, next; for (int i = 0; i < N; ++ i) { for (int j = 0; j < M; ++ j) { if (word[0] == grid[i][j]) dp[0][i][j] = dis[i][j]; else dp[0][i][j] = inf; } } for (int i = 1; i < L; ++ i, now ^= 1) { queue<Node> Q; next = now ^ 1; for (int x = 0; x < N; ++ x) for (int y = 0; y < M; ++ y) { dp[next][x][y] = inf; vis[x][y] = false; } for (int x = 0; x < N; ++ x) { for (int y = 0; y < M; ++ y) { if (dp[now][x][y] != inf) { Q.push(Node(x, y)); vis[x][y] = true; if (word[i] == grid[x][y]) dp[next][x][y] = dp[now][x][y]; } } } spfa(Q, dp[now]); for (int x = 0; x < N; ++ x) { for (int y = 0; y < M; ++ y) { if (dp[now][x][y] == inf) continue; for (int k = 0; k < 4; ++ k) { int xx = x + dx[k], yy = y + dy[k]; if (!fit(xx, yy)) continue; if (word[i] == grid[xx][yy]) { dp[next][xx][yy] = min(dp[next][xx][yy], dp[now][x][y] + 1); } } } } } int ret = inf; for (int x = 0; x < N; ++ x) { for (int y = 0; y < M; ++ y) { ret = min(ret, dp[now][x][y]); } } return ret; } int main() { int T; scanf("%d", &T); while (T --) { scanf("%d%d", &N, &M); sx = -1; for (int i = 0; i < N; ++ i) { scanf("%s", grid[i]); for (int j = 0; j < M; ++ j) { if (grid[i][j] == '@'){ assert(sx == -1); sx = i, sy = j; grid[i][j] = '.'; } } } bfs(); assert(sx != -1); int ret = inf, Q; scanf("%d", &Q); while (Q --) { scanf("%s", word); int tmp = solve(word); ret = min(ret, tmp); } if (ret >= inf) ret = -1; printf("%d\n", ret); } return 0; }
已知: \[G(X, Y, N) = \sum_{i=0}^{N}{N \choose (i,N)}X^{N-(i,N)} Y^{i}\]
计算: \(Fibonacci(G(X, Y, N)) \mod 961749331\)
数据规模:\(1 \le X,Y,N \le 10^9\)
一些常用的数论算法的大合集. 具体做法参考下面ppt
http://zimpha.is-programmer.com/user_files/zimpha/File/Solutiuon%20-%20Ginomial%20Theorem.ppt
#include <cmath> #include <vector> #include <cstdio> #include <cassert> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; typedef long long LL; const LL MOD = 961749331; const LL s5 = 169508191, i5 = 803301103; const LL u = (1 + s5) / 2, v = 1 - u + MOD; const int prime[6] = {2, 3, 5, 17, 29, 65027}; const int MAXN = 100000; LL f[6][MAXN], g[6][MAXN], S[MAXN]; vector<int> D; LL pow_mod(LL a, LL n, LL p) { LL ret = 1; for (a %= p; n; n >>= 1, a = a * a % p) { if (n & 1) ret = ret * a % p; } return ret; } void getReady() { for (int t = 0; t < 6; ++ t) { f[t][0] = g[t][0] = 1; int p = prime[t]; for (int i = 1; i <= p; ++ i) { f[t][i] = f[t][i - 1] * i % p; g[t][i] = pow_mod(f[t][i], p - 2, p); } } } LL lucas(LL n, LL m, LL p, LL inv[], LL fac[]) { if (n == 0 && m == 0) return 1; LL a = n % p, b = m % p; if (b > a) return 0; return lucas(n / p, m / p, p, inv, fac) * fac[a] % p * inv[b] * inv[a - b] % p; } //G(X, Y, P) % p LL getGXYNP(LL X, LL Y, LL N, LL p, LL inv[], LL fac[]) { X %= p; Y %= p; for (int i = D.size() - 1; i >= 0; -- i) { LL d = D[i], n = N / d, q = pow_mod(Y, d, p); if (q == 0) S[i] = 0; else if (q == 1) S[i] = n % p; else { S[i] = q * pow_mod(q - 1, p - 2, p) % p; S[i] = S[i] * (pow_mod(q, n, p) - 1 + p) % p; assert(S[i] >= 0); } for (int j = i + 1; j < (int)D.size(); ++ j) { if (D[j] % d == 0) { S[i] -= S[j]; if (S[i] < 0) S[i] += p; } } } LL ret = 1; for (int i = 0; i < (int)D.size(); ++ i) { LL d = D[i], tmp = lucas(N, d, p, inv, fac); tmp = tmp * pow_mod(X, N - d, p) % p * S[i] % p; ret += tmp; if (ret >= p) ret -= p; assert(ret >= 0); } return ret; } void exgcd(LL a, LL b, LL &g, LL &x, LL &y) { if (!b) x = 1, y = 0, g = a; else { exgcd(b, a % b, g, y, x); y -= x * (a / b); } } //G(X, Y, N) % phi(961749331) LL solveGXYN(LL X, LL Y, LL N) { D.clear(); for (int i = 1; i * i <= N; ++ i) { if (N % i == 0) { D.push_back(i); if (i * i != N) D.push_back(N / i); } } sort(D.begin(), D.end()); LL M = MOD - 1, ret = 0; for (int i = 0; i < 6; ++ i) { LL x, y, gg, tm = M / prime[i]; exgcd(tm, prime[i], gg, x, y); LL now = getGXYNP(X, Y, N, prime[i], g[i], f[i]); x %= M; if (x < 0) x += M; ret = (ret + tm * x % M * now % M) % M; assert(ret >= 0); } return ret; } int main() { int X, Y, N; getReady(); while (scanf("%d%d%d", &X, &Y, &N) == 3) { LL n = solveGXYN(X, Y, N); LL ret = pow_mod(u, n, MOD) - pow_mod(v, n, MOD); ret += MOD; ret %= MOD; assert(ret >= 0); ret = ret * i5 % MOD; printf("%lld\n", ret); } return 0; }
有一个长方体,中间有些地方被挖空了。然后给定一个转轴,问这个图形的转动惯量是多少。
数据规模:坐标绝对值小于等于1000
利用大学物理学过的转动惯量公式搞, 精度需要注意.
#include <cstdio> #include <map> #include <cmath> using namespace std; long double a,b,c; const int MAXN = 110; int Sx,Sy,Sz; long double tri(long double x) { return x*x*x; } long double sqr(long double x) { return x*x; } long double fxx(int sx,int tx,int sy,int ty,int sz,int tz) { return ((tri(tx) - tri(sx))/3.0)*(ty - sy)*(tz - sz); //return ((tri(tx)*ty*tz - tri(sx)*sy*sz)/3.0); } long double fxy(int sx,int tx,int sy,int ty,int sz,int tz) { return ((sx + tx)*(sy + ty)/4.0 ) * (tx - sx)*(ty - sy) * (tz - sz); //return ((sqr(tx)*sqr(ty) - sqr(sx)*sqr(sy))/4.0)*(tz - sz); //return ((sqr(tx)*sqr(ty)*tz - sqr(sx)*sqr(sy)*sz)/4.0); //return ((sqr(tx) - sqr(sz))*(sqr(ty) - sqr(sy))/4.0)*(tz - sz); } long double calc(int sx,int sy,int sz,int tx,int ty,int tz) { long double ret = (sqr(b) + sqr(c))*(fxx(sx,tx,sy,ty,sz,tz)); ret += (sqr(c) + sqr(a))*(fxx(sy,ty,sx,tx,sz,tz)); ret += (sqr(a) + sqr(b))*(fxx(sz,tz,sx,tx,sy,ty)); ret -= 2*a*b*fxy(sx,tx,sy,ty,sz,tz); ret -= 2*b*c*fxy(sy,ty,sz,tz,sx,tx); ret -= 2*a*c*fxy(sx,tx,sz,tz,sy,ty); return ret; } int n,T; int dsx[MAXN],dsy[MAXN],dsz[MAXN],dtx[MAXN],dty[MAXN],dtz[MAXN]; int idx[MAXN*2],idy[MAXN*2],idz[MAXN*2],ndx,ndy,ndz; map<int,int> mapx,mapy,mapz; bool gao[MAXN*2][MAXN*2][MAXN*2]; int main() { scanf("%d",&T); while(T--) { scanf("%d%d%d%d%d%d",dsx,dsy,dsz,dtx,dty,dtz); scanf("%d%d%d",&Sx,&Sy,&Sz); long double l = sqrt(sqr(Sx)+sqr(Sy)+sqr(Sz)); a = Sx/l; b = Sy/l; c = Sz/l; scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d%d%d%d%d%d",dsx+i,dsy+i,dsz+i,dtx+i,dty+i,dtz+i); if (dsx[i] < dsx[0]) dsx[i] = dsx[0]; if (dsy[i] < dsy[0]) dsy[i] = dsy[0]; if (dsz[i] < dsz[0]) dsz[i] = dsz[0]; if (dtx[i] > dtx[0]) dtx[i] = dtx[0]; if (dty[i] > dty[0]) dty[i] = dty[0]; if (dtz[i] > dtz[0]) dtz[i] = dtz[0]; } mapx.clear(); mapy.clear(); mapz.clear(); for(int i = 0;i <= n;i++) { mapx[dsx[i]] = 0; mapx[dtx[i]] = 0; mapy[dsy[i]] = 0; mapy[dty[i]] = 0; mapz[dsz[i]] = 0; mapz[dtz[i]] = 0; } ndx = 0; for(map<int,int>::iterator it = mapx.begin();it != mapx.end();it++) { it->second = ndx; idx[ndx++] = it->first; } ndx--; ndy = 0; for(map<int,int>::iterator it = mapy.begin();it != mapy.end();it++) { it->second = ndy; idy[ndy++] = it->first; } ndy--; ndz = 0; for(map<int,int>::iterator it = mapz.begin();it != mapz.end();it++) { it->second = ndz; idz[ndz++] = it->first; } ndz--; for(int i = 0;i < ndx;i++) for(int j = 0;j < ndy;j++) for(int k = 0;k < ndz;k++) gao[i][j][k] = true; for(int i = 1;i <= n;i++) { dsx[i] = mapx[dsx[i]]; dsy[i] = mapy[dsy[i]]; dsz[i] = mapz[dsz[i]]; dtx[i] = mapx[dtx[i]]; dty[i] = mapy[dty[i]]; dtz[i] = mapz[dtz[i]]; for(int ii = dsx[i];ii < dtx[i];ii++) for(int jj = dsy[i];jj < dty[i];jj++) for(int kk = dsz[i];kk < dtz[i];kk++) gao[ii][jj][kk] = false; } long double ans = 0; for(int i = 0;i < ndx;i++) for(int j = 0;j < ndy;j++) for(int k = 0;k < ndz;k++) if (gao[i][j][k]) ans += calc(idx[i],idy[j],idz[k],idx[i+1],idy[j+1],idz[k+1]); printf("%.20Lf\n",ans); } return 0; }
August | ||||||
---|---|---|---|---|---|---|
Sun | Mon | Tue | Wed | Thu | Fri | Sat |
28 | 29 | 30 | 31 | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Sun, 11 Jan 2015 20:35:26 +0800
Fibnacci->Fibonacci
Mon, 12 Jan 2015 01:55:38 +0800
@random: thx
Sun, 08 Mar 2015 22:43:42 +0800
请问C题怎么做= =,已崩溃