The 15th Zhejiang University Programming Contest

ZOJ Monthly, January 2015

zimpha posted @ Sun, 11 Jan 2015 17:18:20 +0800 in ZOJ , 2026 readers

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: 妈呀, 拖延了两个月才写题解.. 多不好意思.

Problem A Nuclear Power Plant

有一棵树，记$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;
}

Problem B Cards

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;
}

Problem C Cirno's Perfect Math Class

给你一个数$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);
        }
    }
}

Problem D Unlucky Right Triangle

给你一个数$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;
}

Problem E Easy Task

给你一个数组$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;
}

Problem F Fixed Point

给你三个函数$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;
}

Problem G GCD Reduce

给你一列数$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;
}

Problem H Collect Chars

有一个$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;
}

Problem I Ginomial Theorem

已知: \[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;
}

Problem J You need Medicine

有一个长方体，中间有些地方被挖空了。然后给定一个转轴，问这个图形的转动惯量是多少。

数据规模：坐标绝对值小于等于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;
}