problem1
如果decisions的大小为0,那么每一轮都是$N$个人。答案为0.
否则,如果答案不为0,那么概率最大的一定是一开始票数最多的人。因为这个人每一轮都在可以留下来的人群中。
假设第一轮之后剩下$r_{1}$个人,那么第二轮之后将剩下$r_{2}=N$%$r_{1}$个人。不妨设$r_{1}<N$。第一轮能够使得$r_{1}$个人的票数答案一样多且最多(设这个票数为$x$),那么这个x一定是大于等于单纯由decisions决定出的最大值。而现在$r_{1}<N$了,所以必然现在能投出的最大值还是大于等于第一轮的最大值。最后结果是:一些人的票数是$N/r_{1}$,另外一些是$N/r_{1}+1$,那么后一部分人将留下来到下一轮。
同理第$k$轮之后剩下$r_{k}=N$%$r_{k-1}$个人,直到剩下一个人。当出现$N$%$r_{i}=0$时,说明出现循环,答案为0。
有解的话,答案为$\frac{r_{2}}{r_{1}}*\frac{r_{3}}{r_{2}}*...*\frac{r_{k}}{r_{k-1}}=\frac{r_{k}}{r_{1}}=\frac{1}{r_{1}}$
problem2
首先,最后的图形的结果不会超出(-27,0)到(27,81)这个范围。
由于给出的范围都是整数,那么每次用给出的区间$R$与当前图形能扩展出的最大区间$R_{i}$比较,如果$R$能包含$R_{i}$,那么直接计算即可。否则可将当前线段继续增长,出现三个小区间,继续匹配即可。可以看出,最后最小的区间的大小为$1$x$1$。
对于一个线段$p_{1}p_{2}$,设还能增长$t$次,$L=|p_{1}p_{2}|$,那么最后的长度为$L(1+\frac{2}{3}t)$
problem3
$p_{5}$和$p_{7}$的个数就是5和7的个数。剩下的数字1,2,3,4,6,8,9出现的次数都不能确定。
可以枚举2,4,8出现的次数,这样根据$p_{2}$可以确定6出现的次数,再枚举9出现的次数,然后根据$p_{3}$以及6和9的个数可以确定3的个数,最后根据$S$可以确定1的个数。假设数字$i$出现的个数为$c_{i}$,令总位数$n=\sum_{i=1}^{9}c_{i}$。那么假设最后的某一位为数字$i$的方案数有$f(i)=\frac{(n-1)!}{c_{1}c_{2}...(c_{i}-1)...c_{8}c_{9}}$。然后数字$i$可以在第$0$位到第$n-1$位的任何一位,那么数字$i$对答案的贡献位$g(i)=f(i)*(1+10^{1}+...+10^{n-1})$
code for problem1
public class MafiaGame { public double probabilityToLose(int N, int[] decisions) { int[] c = new int[N]; for (int x : decisions) { ++ c[x]; } int mx = 0; for (int x : c) { mx = Math.max(mx, x); } if (mx == 0) { return 0; } int tot = N - decisions.length; int r = 0; for (int i = 0; i < N; ++ i) { if (c[i] <= mx - 1) { tot -= mx - 1 - c[i]; } else { r += 1; } } if (tot > 0) { r += tot; } double result = 1.0 / r; while (r != 1) { if (N % r == 0) { return 0; } r = N % r; } return result; }}
code for problem2
public class FractalPicture { static class Point { int x, y; Point() {} Point(int x, int y) { this.x = x; this.y = y; } } static class Rect { int x1, x2, y1, y2; Rect() {} Rect(int x1, int y1, int x2, int y2) { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } Rect intersect(Rect a) { return new Rect(Math.max(x1, a.x1), Math.max(y1, a.y1), Math.min(x2, a.x2), Math.min(y2, a.y2)); } boolean contains(Rect r) { return x1 <= r.x1 && r.x2 <= x2 &&y1 <= r.y1 && r.y2 <= y2; } } static Rect extend(Point p1, Point p2) { if (p1.x == p2.x) { int y1 = Math.min(p1.y, p2.y); int y2 = Math.max(p1.y, p2.y); int detx = Math.max(1, (y2 - y1) / 3); return new Rect(p1.x - detx, y1, p1.x + detx, y2); } else { int x1 = Math.min(p1.x, p2.x); int x2 = Math.max(p1.x, p2.x); int dety = Math.max(1, (x2 - x1) / 3); return new Rect(x1, p1.y - dety, x2, p1.y + dety); } } static int length(Point p1, Point p2) { if (p1.x == p2.x) { return Math.abs(p1.y - p2.y); } return Math.abs(p1.x - p2.x); } public double getLength(int x1, int y1, int x2, int y2) { Point p1 = new Point(0, 0); Point p2 = new Point(0, 81); Rect r = new Rect(x1, y1, x2, y2).intersect(extend(p1, p2)); return dfs(r, p1, p2, 499); } static int segIntersectSeg(int L1, int R1, int L2, int R2) { return Math.max(0, Math.min(R1, R2) - Math.max(L1, L2)); } static int rectIntersectSegment(Rect i, Point p1, Point p2) { assert i.x1 <= i.x2 && i.y1 <= i.y2; if (p1.x == p2.x) { int x = p1.x; int y1 = Math.min(p1.y, p2.y); int y2 = Math.max(p1.y, p2.y); if (i.x1 <= x && x <= i.x2) { return segIntersectSeg(i.y1, i.y2, y1, y2); } else { return 0; } } else { int y = p1.y; int x1 = Math.min(p1.x, p2.x); int x2 = Math.max(p1.x, p2.x); if (i.y1 <= y && y <= i.y2) { return segIntersectSeg(i.x1, i.x2, x1, x2); } else { return 0; } } } static double calculate(Point p1, Point p2, int t) { return length(p1, p2) * (1.0 + t * 2.0 / 3.0); } static double calculateUnit(Rect r, Point p1, Point p2, int t) { double tot = calculate(p1, p2, t); if (p1.x == p2.x) { int x = p1.x; int y1 = Math.min(p1.y, p2.y); int y2 = Math.max(p1.y, p2.y); if (r.x1 <= x && x <= r.x2 && r.y1 <= y1 && y2 <= r.y2) { if (r.x1 == x || r.x2 == x) { return (tot - 1) * 0.5 + 1; } return tot; } return 0; } else { int y = p1.y; int x1 = Math.min(p1.x, p2.x); int x2 = Math.max(p1.x, p2.x); if (r.y1 <= y && y <= r.y2 && r.x1 <= x1 && x2 <= r.x2) { if (r.y1 == y || r.y2 == y) { return (tot - 1) * 0.5 + 1; } return tot; } return 0; } } static Point[] explode(Point p1, Point p2) { if (p1.x == p2.x) { int len = p2.y - p1.y; Point pp1 = new Point(p1.x, p1.y + len / 3 * 2); Point pp2 = new Point(p1.x - len / 3, pp1.y); Point pp3 = new Point(p1.x + len / 3, pp1.y); return new Point[]{pp1, pp2, pp3}; } else { int len = p2.x - p1.x; Point pp1 = new Point(p1.x + len / 3 * 2, p1.y); Point pp2 = new Point(pp1.x, p1.y - len / 3); Point pp3 = new Point(pp1.x, p1.y + len / 3); return new Point[]{pp1, pp2, pp3}; } } double dfs(Rect r, Point p1, Point p2, int t) { if (r.x1 > r.x2 || r.y1 > r.y2) { return 0; } if (t == 0) { return rectIntersectSegment(r, p1, p2); } if (r.contains(extend(p1, p2))) { return calculate(p1, p2, t); } if (length(p1, p2) == 1) { return calculateUnit(r, p1, p2, t); } Point[] ps = explode(p1, p2); double result = rectIntersectSegment(r, p1, ps[0]); result += dfs(r, ps[0], ps[1], t - 1); result += dfs(r, ps[0], ps[2], t - 1); result += dfs(r, ps[0], p2, t - 1); return result; }}
code for problem3
import java.util.*;import java.math.*;import static java.lang.Math.*;public class ProductAndSum { final static int mod = 500500573; public int getSum(int p2, int p3, int p5, int p7, int S) { long[] p = new long[S + 1]; long[] q = new long[S + 1]; p[0] = q[0] = 1; for (int i = 1; i <= S; ++ i) { p[i] = p[i - 1] * i % mod; q[i] = pow(p[i], mod - 2); } long[] f = new long[S + 1]; f[0] = 1; for (int i = 1, b = 1; i <= S; ++ i) { b = (int)(b * 10L % mod); f[i] = (f[i - 1] + b) % mod; } int[] c = new int[10]; c[5] = p5; c[7] = p7; long result = 0; for (c[2] = 0; c[2] <= p2; ++ c[2]) { for (c[4] = 0; c[4] * 2 + c[2] <= p2; ++ c[4]) { for (c[8] = 0; c[8] * 3 + c[4] * 2 + c[2] <= p2; ++ c[8]) { c[6] = p2 - c[2] - c[4] * 2 - c[8] * 3; for (c[9] = 0; c[9] * 2 +c[6] <= p3; ++ c[9]) { c[3] = p3 - c[6] - c[9] * 2; c[1] = S; for (int i = 2; i <= 9; ++ i) { c[1] -= c[i] * i; } if (c[1] < 0) { continue; } int n = 0; for (int i = 1; i <= 9; ++ i) { n += c[i]; } long k = p[n - 1]; for (int i = 1; i <= 9; ++ i) { k = k * q[c[i]] % mod; } for (int i = 1; i <= 9; ++ i) { if (c[i] != 0) { result += k * p[c[i]] % mod * q[c[i] - 1] % mod * f[n - 1] % mod * i % mod; result %= mod; } } } } } } return (int)result; } static long pow(long a, long b) { a %= mod; long result = 1; while (b > 0) { if (b % 2 == 1) { result = result * a % mod; } a = a * a % mod; b >>= 1; } return result; }}