## 题目描述

$n$ black and white balls were put into a bag. Petya doesn’t know exactly how many black balls are there among them. He knows, however, that there are $0, 1, \ldots, n$ black balls among all balls in the bag with equal probability.
Petya took $l$ balls from the bag at random, and $l_1$ of them turned out black, while $l_2$ other turned out white ($l_1+l_2=l$). Now he wants to predict how many black balls were there initially in the bag. Of course, if $l \lt n$, he can’t be sure in his prediction, but he wants to predict a segment $[a, b]$, such that the amount $k$ of black balls belongs to it with probability at least $p$.
You are given $n, l_1, l_2$ and $p$, and you must find such $a$ and $b$ that $b-a$ is minimal possible. If there are several such pairs $(a, b)$, choose the one with the smallest $a$.

## 算法分析

$$P(B_i|A)={P(B_i)P(A|B_i) \over \sum_{j=0}^n P(B_j)P(A|B_j)}$$

$$P(B_i)={1 \over n+1}, \; P(A|B_i)={{i \choose l_1}{n-i \choose l_2} \over {n \choose l}}$$

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 55;
double a[N];

double get_c(int n, int m) {
if (n < m)
return 0;
double ret = 1;
for (int i = 0; i < m; ++i)
ret *= 1. * (n - i) / (m - i);
return ret;
}

int main() {
int n, l1, l2, p;
scanf("%d%d%d%d", &n, &l1, &l2, &p);
double b = 0;
for (int i = 0; i <= n; ++i)
b += a[i] = 1. / (n + 1) * get_c(i, l1) * get_c(n - i, l2) / get_c(n, l1 + l2);
for (int i = 1; i <= n + 1; ++i)
for (int j = 0; j + i - 1 <= n; ++j) {
double sum = 0;
for (int k = j; k <= j + i - 1; ++k)
sum += a[k];
if (sum / b * 100 + 1e-12 >= p)
return printf("%d %d\n", j, j + i - 1), 0;
}
return 0;
}


## 题目描述

Dr. Ceizenp’ok from planet i1c5l became famous across the whole Universe thanks to his recent discovery – the Ceizenpok’s formula. This formula has only three arguments: $n, k$ and $m$, and its value is a number of $k$-combinations of a set of $n$ modulo $m$.
While the whole Universe is trying to guess what the formula is useful for, we need to automate its calculation.

## 算法分析

$$x={n \choose k}, \; m=p_1^{a_1}p_2^{a_2} \cdots p_q^{a_q}$$

$$\left\{ \begin{array}{c} x \equiv r_1 \pmod{p_1^{a_1}} \\ x \equiv r_2 \pmod{p_2^{a_2}} \\ \cdots \\ x \equiv r_q \pmod{p_q^{a_q}} \end{array} \right.$$

$${n \choose k}={n! \over k!(n-k)!}$$

$$f(n)=n! \bmod p_i^{a_i}$$

$$f(n)=\left(f\left(\left\lfloor{n \over p_i}\right\rfloor\right)\cdot p_i^{\lfloor n/p_i \rfloor}\cdot\left(\prod_{i \in [1, p_i^{a_i}], \; p_i\not\mid i}i\right)^{\lfloor n/p_i^{a_i} \rfloor}\cdot\prod_{i \in [1, n \bmod p_i^{a_i}], \; p_i\not\mid i}i\right)\bmod p_i^{a_i}$$

## 代码

/*
* Your lucky number has been disconnected.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

int power(int a, int b, int m) {
int ret = 1;
for (; b; b >>= 1)
b & 1 && ((ret *= a) %= m), (a *= a) %= m;
return ret;
}

void ex_gcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return;
}
ex_gcd(b, a % b, y, x), y -= a / b * x;
}

int get_inv(int a, int b) {
int x, y;
ex_gcd(a, b, x, y);
return (x + b) % b;
}

int get_fac(int n, int p, int k) {
int m = power(p, k, 1e9), ret = 1;
for (; n; n /= p) {
if (n / m) {
int rec = 1;
for (int i = 2; i < m; ++i)
if (i % p)
(rec *= i) %= m;
(ret *= power(rec, n / m, m)) %= m;
}
for (int i = n % m; i > 1; --i)
if (i % p)
(ret *= i) %= m;
}
return ret;
}

int calc(int N, int K, int M, int p, int k) {
int a = get_fac(N, p, k), b = get_fac(K, p, k), c = get_fac(N - K, p, k),
cnt = 0;
for (int i = N; i; i /= p)
cnt += i / p;
for (int i = K; i; i /= p)
cnt -= i / p;
for (int i = N - K; i; i /= p)
cnt -= i / p;
int m = power(p, k, 1e9),
ret = a * get_inv(b, m) % m * get_inv(c, m) % m * power(p, cnt, m) % m;
return ret * (M / m) % M * get_inv(M / m, m) % M;
}

signed main() {
int N, K, M, ans = 0;
scanf("%lld%lld%lld", &N, &K, &M);
for (int i = 2, t = M; t > 1; ++i)
if (!(t % i)) {
int k = 0;
for (; !(t % i); ++k, t /= i)
;
(ans += calc(N, K, M, i, k)) %= M;
}
printf("%lld\n", ans);
return 0;
}


## 算法分析1

$$f(x)=\sum_{i=1}^n {\prod_{j \in [1, n] \land j \neq i} (x-x_j) \over \prod_{j \in [1, n] \land j \neq i} (x_i-x_j)}y_i$$

## 代码1

#include <cstdio>

#define int long long

void read(int &n) {
char c; while ((c = getchar()) < '0' || c > '9') ; n = c - '0';
while ((c = getchar()) >= '0' && c <= '9') (n *= 10) += c - '0';
}

static const int K = 50005;
static const int MOD = 1000000007;
int n, k, a[K], p[K], q[K], inv[K], base[K];

int power(int a, int b) {
int ret = 1; a %= MOD, b %= MOD - 1;
while (b) b & 1 && ((ret *= a) %= MOD), (a *= a) %= MOD, b >>= 1;
return ret;
}

int calc(int n) {
if (n <= k + 2) return a[n]; n %= MOD;
int w = power(base[k + 2], MOD - 2), ans = 0;
p[0] = q[k + 3] = 1;
for (int i = 1; i <= k + 2; ++ i) p[i] = p[i - 1] * (n - i) % MOD;
for (int i = k + 2; i; -- i) q[i] = q[i + 1] * (n - i) % MOD;
for (int i = 1; i <= k + 2; ++ i) (ans += a[i] * w % MOD * p[i - 1] % MOD * q[i + 1]) %= MOD, w = w * (i - k - 2) % MOD * inv[i] % MOD;
return (ans + MOD) % MOD;
}

signed main() {
int T; read(T), base[1] = 1;
for (int i = 1; i < K; ++ i) inv[i] = power(i, MOD - 2);
for (int i = 2; i < K; ++ i) base[i] = base[i - 1] * (MOD + 1 - i) % MOD;
while (T --) {
read(n), read(k);
for (int i = 1; i < k + 3; ++ i) a[i] = (a[i - 1] + power(i, k)) % MOD;
printf("%lld\n", calc(n));
}
return 0;
}


## 算法分析2

$$\sum_{i=1}^n i^k={1 \over k+1} \sum_{i=0}^k (-1)^i {k+1 \choose i} B_in^{k+1-i}$$

$$\sum_{i=0}^{\infty} B_i{x^i \over i!}={x \over e^x-1}={x \over \sum_{i=1}^{\infty} {x^i \over i!}}={1 \over \sum_{i=0}^{\infty} {x^i \over (i+1)!}}$$

## 代码2

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 200000;
static int const MOD = 1000000007;
static int const M = 31622;
static double const PI = acos(-1);
int b[N], rev[N], fac[N], inv[N];
class complex {
private:
double x, y;

public:
complex(double _x = 0, double _y = 0) : x(_x), y(_y) {}
double real() { return x; }
friend complex operator+(complex const &a, complex const &b) {
return complex(a.x + b.x, a.y + b.y);
}
friend complex operator-(complex const &a, complex const &b) {
return complex(a.x - b.x, a.y - b.y);
}
friend complex operator*(complex const &a, complex const &b) {
return complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
} wn[N], A[N], B[N], C[N], D[N], E[N], F[N], G[N];

int power(int a, int b) {
int ret = 1;
for (; b; b >>= 1)
b & 1 && ((ret *= a) %= MOD), (a *= a) %= MOD;
return ret;
}

int init(int m) {
int n = 1, l = 0;
for (; n <= m; n <<= 1, ++l)
;
for (int i = 1; i < n; ++i)
rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
for (int i = 0; i < n >> 1; ++i)
wn[i] = complex(cos(2 * PI / n * i), sin(2 * PI / n * i));
return n;
}

void fft(complex *a, int n, bool inv = 0) {
for (int i = 0; i < n; ++i)
if (i < rev[i])
std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; j += i << 1)
for (int k = 0; k < i; ++k) {
complex x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
a[j + k] = x + y, a[j + k + i] = x - y;
}
if (inv) {
std::reverse(a + 1, a + n);
for (int i = 0; i < n; ++i)
a[i] = a[i].real() / n;
}
}

int get_mod(double t) {
return (int)(fmod(t, MOD) + MOD + 0.5) % MOD;
}

void get_inv(int *f, int *g, int n) {
if (n == 1)
return void(g[0] = power(f[0], MOD - 2));
get_inv(f, g, n + 1 >> 1);
int len = init(n << 1);
for (int i = 0; i < n + 1 >> 1; ++i)
A[i] = g[i] / M, B[i] = g[i] % M;
for (int i = n + 1 >> 1; i < len; ++i)
A[i] = B[i] = 0;
for (int i = 0; i < n; ++i)
C[i] = f[i] / M, D[i] = f[i] % M;
for (int i = n; i < len; ++i)
C[i] = D[i] = 0;
fft(A, len), fft(B, len), fft(C, len), fft(D, len);
for (int i = 0; i < len; ++i) {
E[i] = 0 - A[i] * C[i];
F[i] = 0 - A[i] * D[i] - B[i] * C[i];
G[i] = 2 - B[i] * D[i];
}
fft(E, len, 1), fft(F, len, 1), fft(G, len, 1);
for (int i = 0; i < n; ++i) {
int x = get_mod(E[i].real()) * M % MOD * M % MOD;
int y = get_mod(F[i].real()) * M % MOD;
int z = get_mod(G[i].real());
int w = (x + y + z) % MOD;
C[i] = w / M, D[i] = w % M;
}
for (int i = n; i < len; ++i)
C[i] = D[i] = 0;
fft(C, len), fft(D, len);
for (int i = 0; i < len; ++i) {
E[i] = A[i] * C[i];
F[i] = A[i] * D[i] + B[i] * C[i];
G[i] = B[i] * D[i];
}
fft(E, len, 1), fft(F, len, 1), fft(G, len, 1);
for (int i = 0; i < n; ++i) {
int x = get_mod(E[i].real()) * M % MOD * M % MOD;
int y = get_mod(F[i].real()) * M % MOD;
int z = get_mod(G[i].real());
g[i] = (x + y + z) % MOD;
}
}

int get_c(int n, int m) {
return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

signed main() {
int T;
fac[0] = 1;
for (int i = 1; i < N; ++i)
fac[i] = fac[i - 1] * i % MOD;
inv[N - 1] = power(fac[N - 1], MOD - 2);
for (int i = N - 1; i; --i)
inv[i - 1] = inv[i] * i % MOD;
get_inv(inv + 1, b, 50001);
for (int i = 0; i < 50001; ++i)
(b[i] *= fac[i]) %= MOD;
for (scanf("%lld", &T); T--;) {
int n, k, ans = 0;
scanf("%lld%lld", &n, &k), n %= MOD;
for (int i = k, f = k & 1 ? -1 : 1, p = n; ~i; --i, f = -f, (p *= n) %= MOD)
ans += (MOD + f) * get_c(k + 1, i) % MOD * b[i] % MOD * p % MOD;
printf("%lld\n", ans % MOD * power(k + 1, MOD - 2) % MOD);
}
return 0;
}


## 题目描述

On Panda’s Birthday party, he received a strange present from Jason. The present is a black box with $4$ dices in it which is used to play a game. The dice in the box is unusual. Instead of the digits, only red or blue is painted on each side of the dice. Before the first round of the game, the box can repaint every side of every dice red or blue with equal probability. Then for each round of the game, the box will roll the $4$ dices and tell the player the number of red side facing up, which is the point the player get. Now, Panda has play it for two rounds and he tell you the point he has got for each round. Can you tell him the expected point he can get for next round.

## 算法分析

1. 对于一个骰子，它有$t$个面被染成红色的概率$P(x=t)={{6 \choose t} \over 2^6}={{6 \choose t} \over 64}$；
2. 扔一个骰子$n$次，其中有$k$次朝上的面是红色的概率为$\sum_{i=0}^6 P(x=i) \cdot {i^k(6-i)^{n-k} \over 6^n}$。

\begin{align} P(111|11)&={9 \over 14} \\ P(101|10)&={1 \over 2} \\ P(001|00)&={5 \over 14} \end{align}

$${p+q \over 2} \cdot {9 \over 14}+\left(4-{p+q \over 2}\right) \cdot {5 \over 14}={p+q+10 \over 7}$$

$${p+q-1 \over 2} \cdot {9 \over 14}+\left(4-{p+q+1 \over 2}\right) \cdot {5 \over 14}+{1 \over 2}={p+q+10 \over 7}$$

## Notes on Module

### 逆元

$$(a/(a, m))x \equiv b/(a, m) \pmod {m/(a, m)}$$

$$x \equiv (a/(a, m))^{-1} \times (b/(a, m)) \pmod {m/(a, m)}$$

$$x \equiv (a/(a, m))^{-1} \times (b/(a, m)) + (m/(a, m)) \times k \pmod m \; (0 \le k \lt (a, m))$$

### 费马小定理

\begin{align} x^{p-1} &\equiv 1 \pmod p \\ x^{-1} &\equiv x^{p-2} \pmod p \end{align}

$$x^{\varphi(m)} \equiv 1 \pmod m$$

### 线性同余方程组

\left\{ \begin{align} x &\equiv b_i \pmod {m_i} \\ ax &\equiv b_{i+1} \pmod {m_{i+1}} \end{align} \right.

$$a(tm_i+b_i) \equiv b_{i+1} \pmod {m_{i+1}}$$

$$atm_i \equiv b_{i+1}-ab_i \pmod {m_{i+1}}$$

### 中国剩余定理

$$\forall i \in [1, n], \; a_i=1 \land \forall i, j \in [1, n] \land i \neq j, \; (m_i, m_j)=1$$

$$x \equiv b \pmod {\prod m_i}$$

\begin{align} (a, b)\times(c, d)&=(ac, b+d) \\ (a, b)/(c, d)&=(ac^{-1}, b-d) \end{align}

### $n!$

$$((p-1)!)^{n/p} \times (n \bmod p)!$$

### ${n \choose k} \bmod p$

$$n=\sum n_ip^i \; (0 \le n_i \lt p), \; k=\sum k_ip^i \; (0 \le k_i \lt p)$$

$${n \choose k} \equiv \prod {n_i \choose k_i} \pmod p$$

$${n \choose k}={n! \over k!(n-k)!}$$

$$n!=a_1p^{e_1}, \; k!=a_2p^{e_2}, \; (n-k)!=a_3p^{e_3}$$

## 题目描述

Karen has just arrived at school, and she has a math test today!
The test is about basic addition and subtraction. Unfortunately, the teachers were too busy writing tasks for Codeforces rounds, and had no time to make an actual test. So, they just put one question in the test that is worth all the points.
There are $n$ integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.
Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.
The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.
Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?
Since this number can be quite large, output only the non-negative remainder after dividing it by $10^9+7$.

## 算法分析

\begin{align} n=1,\;&ans=a_1 \\ n=2,\;&ans=a_1+a_2 \\ n=3,\;&ans=a_1+2a_2-a_3 \\ n=4,\;&ans=a_1-a_2+a_3-a_4 \\ n=5,\;&ans=a_1+2a_3+a_5 \\ n=6,\;&ans=a_1+a_2+2a_3+2a_4+a_5+a_6 \\ n=7,\;&ans=a_1+2a_2+a_3+4a_4-a_5+2a_6-a_7 \\ n=8,\;&ans=a_1-a_2+3a_3-3a_4+3a_5-3a_6+a_7-a_8 \\ n=9,\;&ans=a_1+4a_3+6a_5+4a_7+a_9 \\ n=10,\;&ans=a_1+a_2+4a_3+4a_4+6a_5+6a_6+4a_7+4a_8+a_9+a_{10} \\ n=11,\;&ans=a_1+2a_2+3a_3+8a_4+2a_5+12a_6-2a_7+8a_8-3a_9+2a_{10}-a_{11} \\ n=12,\;&ans=a_1-a_2+5a_3-5a_4+10a_5-10a_6+10a_7-10a_8+5a_9-5a_{10}+a_{11}-a_{12} \end{align}

## 代码

#include <iostream>
#define MOD 1000000007
using namespace std;
long long n, t, r[3], ans, c[200001], a[200001];
void extend_gcd(long long a, long long b, long long &x, long long &y) {
if (!b) {
x = 1, y = 0;
return;
}
extend_gcd(b, a % b, y, x);
y -= a / b * x;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
t = (n - 1) / 4 << 1;
c[0] = 1;
for (int i = 0; i < t; ++i) {
long long x, y;
extend_gcd(i + 1, MOD, x, y);
c[i + 1] = c[i] * (t - i) % MOD * x % MOD;
if (c[i + 1] < 0) c[i + 1] += MOD;
}
for (int i = 0; i <= t; ++i) {
r[0] += c[i] * a[(i << 1) + 1] % MOD;
if (!(n & 1)) r[0] += c[i] * a[(i << 1) + 2] % MOD;
}
r[0] %= MOD;
if ((n - 1) % 4 < 2) cout << r[0] << endl;
else {
for (int i = 0; i <= t; ++i) {
r[1] += c[i] * a[(i << 1) + 2] % MOD;
if (!(n & 1)) r[1] -= c[i] * a[(i << 1) + 3] % MOD;
}
r[1] %= MOD;
for (int i = 0; i <= t; ++i) {
r[2] += c[i] * a[(i << 1) + 3] % MOD;
if (!(n & 1)) r[2] += c[i] * a[(i << 1) + 4] % MOD;
}
r[2] %= MOD;
if (n & 1) ans = (r[0] + (r[1] << 1) - r[2]) % MOD;
else ans = (r[0] - (r[1] << 1) - r[2]) % MOD;
if (ans < 0) ans += MOD;
cout << ans << endl;
}
return 0;
}


## 题目描述

There are $n$ lights aligned in a row. These lights are numbered $1$ to $n$ from left to right. Initially some of the lights are switched on. Shaass wants to switch all the lights on. At each step he can switch a light on (this light should be switched off at that moment) if there’s at least one adjacent light which is already switched on.
He knows the initial state of lights and he’s wondering how many different ways there exist to switch all the lights on. Please find the required number of ways modulo $1000000007$ ($10^9+7$).

## 算法分析

$$s_i= \begin{cases} 1, & i=1 \lor i=k \\ 2^{max(l_i-1, 0)}, & otherwise \end{cases}$$

$$f_1=1, \; f_i={t_i \choose l_i}s_if_{i-1}$$

## 代码

#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
long long n, m, ans, last, tot, a[1001], p[2001], c[2001][2001];
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> a[i];
}
sort(a + 1, a + m + 1);
p[0] = p[1] = 1;
for (int i = 2; i <= 2000; ++i) {
p[i] = (p[i - 1] << 1) % MOD;
}
for (int i = 0; i <= 2000; ++i) {
c[i][0] = c[i][i] = 1;
}
for (int i = 2; i <= 2000; ++i) {
for (int j = 1; j < i; ++j) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
}
ans = 1, last = a[1], tot = a[1] - 1;
for (int i = 2; i <= m; ++i) {
(ans *= p[a[i] - a[i - 1] - 1] * c[tot + a[i] - a[i - 1] - 1][tot] % MOD) %= MOD;
tot += a[i] - a[i - 1] - 1;
}
(ans *= c[tot + n - a[m]][tot]) %= MOD;
cout << ans << endl;
return 0;
}


## 题目描述

Memory and his friend Lexa are competing to get higher score in one popular computer game. Memory starts with score $a$ and Lexa starts with score $b$. In a single turn, both Memory and Lexa get some integer in the range $[-k, k]$ (i.e. one integer among $-k, -k+1, -k+2, …, -2, -1, 0, 1, 2, …, k-1, k$) and add them to their current scores. The game has exactly $t$ turns. Memory and Lexa, however, are not good at this game, so they both always get a random integer at their turn.
Memory wonders how many possible games exist such that he ends with a strictly higher score than Lexa. Two games are considered to be different if in at least one turn at least one player gets different score. There are $(2k+1)^{2t}$ games in total. Since the answer can be very large, you should print it modulo $10^9+7$. Please solve this problem for Memory.

## 算法分析

$$f_{i, j} = \sum_{|j-l| \le 2k} (2k+1-|j-l|)f_{i-1, l}$$
$j$的范围是$[-200000, 200000]$，暴力求$f_{i, j}$会超时。

## 代码

#include <iostream>
#define MOD 1000000007
using namespace std;
long long a, b, k, t, p, now, ans, f[2][500002], sign[2][500002];
int main()
{
cin >> a >> b >> k >> t;
sign[0][a - b + 250000] = 1;
sign[0][a - b + 250001] = -2;
sign[0][a - b + 250002] = 1;
for (int i = 0; i <= t; ++i, now ^= 1) {
p = f[now][0] = 0;
for (int j = 0; j < 500002; ++j) {
p += sign[now][j];
f[now][j] = p;
if (j) f[now][j] += f[now][j - 1];
f[now][j] %= MOD;
if (f[now][j] < 0) f[now][j] += MOD;
if (f[now][j]) {
sign[now ^ 1][j - (k << 1)] += f[now][j];
sign[now ^ 1][j + 1] -= f[now][j] << 1;
sign[now ^ 1][j + (k + 1 << 1)] += f[now][j];
}
sign[now][j] = f[now ^ 1][j] = 0;
}
}
for (int i = 250001; i < 500001; ++i) {
ans += f[now ^ 1][i];
}
cout << ans % MOD << endl;
return 0;
}