## 一位在退学边缘疯狂试探的学渣为了高代不挂科做出的最终努力

33281378432849
## 1. 爪形行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&1& \cdots &1\\ 1&{{x_2}}& \cdots &0\\ \vdots & \vdots & \ddots &0\\ 1&0&0&{{x_n}} \end{array}} \right|$

## 2. 两三角型行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&b& \cdots &b\\ b&{{x_2}}& \cdots &b\\ \vdots & \vdots & \ddots &b\\ b&b&b&{{x_n}} \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}} {{x_1}}&b&b& \cdots &b\\ a&{{x_2}}&b& \cdots &b\\ a&a&{{x_3}}& \cdots &b\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&a&a& \cdots &{{x_n}} \end{array}} \right|$
3. 求${D_n} = \left| {\begin{array}{*{20}{c}} d&b&b& \cdots &b\\ c&x&a& \cdots &a\\ c&a&x& \cdots &a\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c&a&a& \cdots &x \end{array}} \right|$

## 3. 两条线型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1}}&{{b_1}}&0& \cdots &0\\ 0&{{a_2}}&{{b_2}}& \cdots &0\\ 0&0&{{a_3}}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{b_n}}&0&0& \cdots &{{a_n}} \end{array}} \right|$

## 4. 范德蒙德型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1^n}}&{{a_1^{n-1}b_1}}& \cdots &a_1b_1^{n-1}&b_1^n\\ a_2^n&a_2^{n-1}b_2&\cdots & a_2b_2^{n-1} &b_2^n\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-1}b_n & \cdots & a_nb_n^{n-1}& b_n^n \\ a_{n+1}^n&a_{n+1}^{n-1}b_{n+1}&\cdots&a_{n+1}b_{n+1}^{n-1} &b_{n+1}^n \end{array}} \right|$

## 5. Hessenberg型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&2&3& \cdots &n\\ 1&{ - 1}&0& \cdots &0\\ 0&2&{ - 2}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &{1 - n} \end{array}} \right|$

## 6. 三对角型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} a&b&0& \cdots &0\\ c&a&b& \cdots &0\\ 0&c&a& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &a \end{array}} \right|$

## 7. 各行元素和相等型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {1 + {x_1}}&{{x_1}}&{{x_1}}& \cdots &{{x_1}}\\ {{x_2}}&{1 + {x_2}}&{{x_2}}& \cdots &{{x_2}}\\ {{x_3}}&{{x_3}}&{1 + {x_3}}& \cdots &{{x_3}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{x_n}}&{{x_n}}&{{x_n}}& \cdots &{1 + {x_n}} \end{array}} \right|​$

## 8. 相邻两行对应元素相差K倍型行列式

1. 求${D_n} = \left| {\begin{array}{*{20}{c}} 0&1&2& \cdots &{n - 1}\\ 1&0&1& \cdots &{n - 2}\\ 2&1&0& \cdots &{n - 3}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n - 1}&{n - 2}&1& \cdots &0 \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&a&{{a^2}}& \cdots &{{a^{n - 1}}}\\ {{a^{n - 1}}}&1&a& \cdots &{{a^{n - 2}}}\\ {{a^{n - 2}}}&{{a^{n - 1}}}&1& \cdots &{{a^{n - 3}}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&{{a^2}}&{{a^3}}& \cdots &1 \end{array}} \right|$


## 莫比乌斯反演与容斥原理

mobius_and_inclusion_exclusion_principle

## 【BZOJ 4589】Hard Nim

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (; t; t >>= 1, w = (LL)w * w % MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
for (int d = 1; d < len; d <<= 1) {
for (int i = 0; i < len; i += d << 1) {
for (int j = 0; j < d; j++) {
int t1 = a[i + j], t2 = a[i + j + d];
if (opt == 1) {
a[i + j] = (t1 + t2) % MOD;
a[i + j + d] = (t1 - t2) % MOD;
} else {
a[i + j] = (LL)(t1 + t2) * REV % MOD;
a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
}
}
}
}
}

int main() {
for (int n, m; ~scanf("%d %d", &n, &m); ) {
memset(arr, 0, sizeof(arr));
for (int i = 2; i <= m; i++) {
if (!vis[i]) {
arr[i] = 1;
for (int j = i << 1; 0 <= j && j <= m; j += i) {
vis[j] = 1;
}
}
}
int len = 1;
for (; len <= m; len <<= 1);
FWT(arr, len);
for (int i = 0; i < len; i++) {
arr[i] = Pow(arr[i], n);
}
FWT(arr, len, -1);
printf("%d\n", (arr[0] + MOD) % MOD);
}
return 0;
}


## 【BZOJ 4599】[JLOI2016] 成绩比较

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
int ret = 0;
for (int i=1;i<=len;i++) {
int tmp = ff[i];
for (int j=1;j<=len;j++) {
if (i == j) continue;
tmp = (LL)tmp * (x - xx[j]) % MOD;
tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
}
ret = (ret + tmp) % MOD;
}
return (ret + MOD) % MOD;
}

int main() {
for (int i=1;i<=m;i++) {
}
for (int i=1;i<=m;i++) {
}
//预处理组合数
C[0][0] = 1;
for (int i=1;i<=n;i++) {
C[i][0] = 1;
for (int j=1;j<=i;j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
//拉格朗日插值
for (int w=1;w<=m;w++) {
for (int i=1;i<=n+1;i++) {
f[i] = 0; h[i] = i;
for (int j=1;j<=i;j++) {
f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
}
}
g[w] = LagrangePolynomial(u[w], n+1, f, h);
}
//广义容斥原理
int ans = 0;
for (int i=K,t=1;i<=n;i++,t*=-1) {
alpha[i] = C[n-1][i];
for (int j=1;j<=m;j++) {
alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
}
ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}


## 【BZOJ 4318】OSU!

### 解题报告

$E_{(i,x^2)}，E_{(i,x)}$分别表示$x^2,x$的期望

$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$

$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
double e1=0,e2=0,e3=0,ans=0,p;
for (int i=1;i<=n;i++) {
scanf("%lf",&p);
ans += e3 * (1 - p);
e3 = p * (e3 + 3 * e2 + 3 * e1 + 1);
e2 = p * (e2 + 2 * e1 + 1);
e1 = p * (e1 + 1);
}
printf("%.1lf\n",ans+e3);
return 0;
}


## 【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int LOG = 100;

vector<pair<LL, LL> > num[LOG];

char c = getchar(); LL ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void solve(LL A, LL B) {
if (A < num[2][0].first || B < num[2][0].second) {
printf("1 %d\n", A * B % MOD);
return;
}
for (int i = 2; i < LOG; i++) {
if (A < num[i + 1][0].first || B < num[i + 1][0].second) {
int cnt = 0;
for (int j = 0; j < (int)num[i].size(); j++) {
LL a = num[i][j].first, b = num[i][j].second;
cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD;
cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD;
}
printf("%d %d\n", i, cnt);
return;
}
}
}

inline void prework() {
num[0] = vector<pair<LL,LL> >{make_pair(1, 1)};
for (int i = 1; i < LOG; i++) {
for (int j = 0; j < (int)num[i - 1].size(); ++j) {
LL a = num[i - 1][j].first, b = num[i - 1][j].second;
num[i].push_back(make_pair(b, a + b));
}
LL a = num[i - 1][0].first, b = num[i - 1][0].second;
num[i].push_back(make_pair(a + b, 2 * a + b));
}
}

int main() {
prework();
for (int T = read(); T; T--) {
solve(min(A, B), max(A, B));
}
return 0;
}


## 【日常小测】航海舰队

### Code

#include<bits/stdc++.h>
#define LL long long
#define CP complex<double>
using namespace std;

const int N = 709;
const int M = 5000000;
const double EPS = 0.5;
const double PI = acos(-1);

char mp[N][N];
int n, m, vis[M], sfe[M];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
CP a[M], b[M], c[M];

inline void FFT(CP *arr, int len, int ty) {
static int pos[M], init = 0;
if (init != len) {
for (int i = 1; i < len; ++i) {
pos[i] = (pos[i >> 1] >> 1) | ((i & 1)? (len >> 1): 0);
}
init = len;
}
for (int i = 0; i < len; i++) {
if (pos[i] < i) {
swap(arr[i], arr[pos[i]]);
}
}
for (int i = 1; i < len; i <<= 1) {
CP wn(cos(PI / i), sin(PI / i) * ty);
for (int j = 0; j < len; j += i + i) {
CP w(1, 0);
for (int k = 0; k < i; k++, w *= wn) {
CP tmp = arr[j + i + k] * w;
arr[j + i + k] = arr[j + k] - tmp;
arr[j + k] = arr[j + k] + tmp;
}
}
}
if (ty == -1) {
for (int i = 0; i < len; i++) {
arr[i] /= len;
}
}
}

inline void BFS(int sx, int sy, int lx, int ly) {
vis[sy * n + sx] = 1;
queue<pair<int, int> > que;
for (que.push(make_pair(sx, sy)); !que.empty(); que.pop()) {
int x = que.front().first;
int y = que.front().second;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx + lx - 1 < n && 0 <= ny && ny + ly - 1 < m && sfe[ny * n + nx] && !vis[ny * n + nx]) {
que.push(make_pair(nx, ny));
vis[ny * n + nx] = 1;
}
}
}
}

int main() {
freopen("sailing.in", "r", stdin);
freopen("sailing.out", "w", stdout);
cin >> m >> n;
int mnx = n, mny = m, mxx = 0, mxy = 0;
for (int j = 0; j < m; j++) {
scanf("%s", mp[j]);
for (int i = 0; i < n; i++) {
if (mp[j][i] == 'o') {
mnx = min(i, mnx);
mxx = max(i, mxx);
mny = min(j, mny);
mxy = max(j, mxy);
}
}
}
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
if (mp[j][i] == 'o') {
b[(j - mny) * n + i - mnx] = CP(1, 0);
} else if (mp[j][i] == '#') {
a[j * n + i] = CP(1, 0);
}
}
}
int cur = n * m, len = 1;
for (; len < cur * 2; len <<= 1);
for (int l = 0, r = cur - 1; l < r; ++l, --r) {
swap(b[l], b[r]);
}
FFT(a, len, 1);
FFT(b, len, 1);
for (int i = 0; i < len; i++) {
a[i] *= b[i];
}
FFT(a, len, -1);
for (int i = 0; i < cur; i++) {
if (a[i + cur - 1].real() < EPS) {
sfe[i] = 1;
}
}
BFS(mnx, mny, mxx - mnx + 1, mxy - mny + 1);
memset(b, 0, sizeof(b));
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
c[j * n + i] = vis[j * n + i]? CP(1, 0): CP(0, 0);
b[(j - mny) * n + i - mnx] = mp[j][i] == 'o'? CP(1, 0): CP(0, 0);
}
}
FFT(c, len, 1);
FFT(b, len, 1);
for (int i = 0; i < len; i++) {
c[i] *= b[i];
}
FFT(c, len, -1);
int ans = 0;
for (int i = 0; i < cur; i++) {
ans += c[i].real() > EPS;
}
printf("%d\n", ans);
return 0;
}


—————————— UPD 2017.6.30 ——————————
B站题号：4624

## 【日常小测】魔术卡

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const int MOD = 998244353;

int n, m, K, a[N], pw[N], inv[N], f[N][N], C[N][N];

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (; t; t >>= 1, w = (LL)w * w % MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

int main() {
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
for (int i = 1; i <= m; i++) {
}
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= n; j++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
pw[0] = inv[0] = 1;
for (int i = 1; i <= n; i++) {
pw[i] = (LL)pw[i - 1] * i % MOD;
inv[i] = Pow(pw[i], MOD - 2);
}
f[0][0] = 1;
for (int i = 1, pre_sum = 0; i <= m; i++) {
pre_sum += a[i] - 1;
for (int j = 0; j <= pre_sum; j++) {
for (int k = min(a[i] - 1, j); ~k; k--) {
f[i][j] = (f[i][j] + (LL)f[i - 1][j - k] * C[a[i]][k] % MOD * pw[a[i] - 1] % MOD * inv[a[i] - 1 - k]) % MOD;
}
}
}
int ans = 0;
for (int i = K, ff = 1; i < n; i++, ff *= -1) {
f[m][i] = (LL)f[m][i] * pw[n - i] % MOD;
ans = (ans + (LL)ff * C[i][K] * f[m][i]) % MOD;
}
for (int i = 1; i <= m; i++) {
ans = (LL)ans * inv[a[i]] % MOD;
}
printf("%d\n", (ans + MOD) % MOD);
return 0;
}


## 【BZOJ 3884】上帝与集合的正确用法

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline int get_phi(int x) {
int ret = x;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
ret = ret / i * (i - 1);
while (x % i == 0) {
x /= i;
}
}
}
return x == 1? ret: ret / x * (x - 1);
}

inline int Pow(int w, int t, int MOD) {
int ret = 1;
for (; t; t >>= 1, w = (LL)w * w % MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline int f(int p) {
if (p == 1) {
return 0;
} else {
int phi = get_phi(p);
return Pow(2, f(phi) + phi , p);
}
}

int main() {
for (int i = read(); i; --i) {
}
return 0;
}


## 【日常小测】最长路径

### 解题报告

1. 任意一个竞赛图一定存在哈密尔顿路径
2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

int main() {
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
pw[0] = 1;
for (int i = 1; i < n * n; i++) {
pw[i] = (pw[i - 1] << 1) % MOD;
}
C[0][0] = 1;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= n; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
f[0] = g[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = g[i] = pw[i * (i - 1) >> 1];
for (int j = 1; j < i; j++) {
g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
}
}
for (int x = 1; x <= n; x++) {
int ans = 0;
for (int i = 1; i <= x; i++) {
ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
}
printf("%d\n", ans > 0? ans: ans + MOD);
}
return 0;
}


## 【Codeforces 749E】Inversions After Shuffle

### Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 100009;

int n, p[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

class Fenwick_Tree{
double sum[N];
public:
inline void init() {
memset(sum, 0, sizeof(sum));
}
inline void modify(int p, int d = 1) {
for (int i = p; i <= n; i += lowbit(i)) {
sum[i] += d;
}
}
inline double query(int p) {
double ret = 0;
for (int i = p; i; i -= lowbit(i)) {
ret += sum[i];
}
return ret;
}
}BIT;

int main() {
for (int i = 1; i <= n; i++) {
}
double ans = 0, psm = 0;
for (int i = n; i; i--) {
ans += BIT.query(p[i]);
BIT.modify(p[i]);
}
ans *= n * (n + 1ll);
BIT.init();
for (int i = 1; i <= n; i++) {
LL t1 = BIT.query(p[i]);
LL t2 = i * (i - 1ll) / 2 - t1;
ans += (psm += t1 - t2);
BIT.modify(p[i], i);
}
printf("%.15lf\n", ans / n / (n + 1));
return 0;
}


## 【Codeforces 812E】Sagheer and Apple Tree

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 10000009;

int n, prt, tot, dep[N], v[N], in[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void AddEdge(int u, int v) {
static int E = 1; in[v]++; in[u]++;
}

void DFS(int w) {
for (int i = head[w]; i; i = nxt[i]) {
dep[to[i]] = dep[w] + 1;
DFS(to[i]);
}
}

int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
for (int i = 1; i <= n; i++) {
}
for (int i = 2; i <= n; i++) {
}
DFS(1);
for (int i = 2; i <= n; ++i) {
if (in[i] == 1) {
prt = (dep[i] & 1);
break;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if ((dep[i] & 1) == prt) {
ans ^= v[i];
}
}
LL vout = 0;
tot = n;
for (int i = 1; i <= n; i++) {
if ((dep[i] & 1) == prt) {
cnt[v[i]]++;
--tot;
}
}
for (int i = 1; i <= n; i++) {
if ((dep[i] & 1) != prt) {
int tt = ans ^ v[i];
if (tt < M) {
vout += cnt[tt];
}
}
}
if (!ans) {
vout += tot * (tot - 1ll) / 2;
vout += (n - tot) * (n - tot - 1ll) / 2;
}
cout<<vout<<endl;
return 0;
}


## 【Codeforces 802L】Send the Fool Further! (hard)

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 200009;
const int MOD = 1000000007;

int n, head[N], nxt[M], to[M], cost[M];
int a[N], b[N], fa[N], d[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void AddEdge(int u, int v, int c) {
static int E = 1;
d[u]++; d[v]++;
cost[E + 1] = cost[E + 2] = c;
}

inline int REV(int x) {
int ret = 1, t = MOD - 2;
for (; t; x = (LL)x * x % MOD, t >>= 1) {
if (t & 1) {
ret = (LL)ret * x % MOD;
}
}
return ret;
}

void solve(int w, int f) {
if (d[w] > 1) {
a[w] = -1;
for (int i = head[w]; i; i = nxt[i]) {
b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD;
if (to[i] != f) {
solve(to[i], w);
}
}
if (w != f) {
b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD;
a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD;
}
}
}

int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
for (int i = 1; i < n; ++i) {
}
solve(1, 1);
int ans = (LL)b[1] * REV(MOD - a[1]) % MOD;
ans = (ans + MOD) % MOD;
cout<<ans<<endl;
return 0;
}


## 【POJ 3922】A simple stone game

### Code

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

const int N = 10000000;

int n,k,x,y,a[N],b[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
for (int t = 1, T = read(); t <= T; ++t) {
a[0] = b[0] = x = y = 0;
while (a[x] < n) {
a[x + 1] = b[x] + 1;
for (++x; (LL)a[y + 1] * k < a[x]; ++y);
b[x] = y? b[y] + a[x]: a[x];
}
if (a[x] == n) {
printf("Case %d: lose\n", t);
} else {
int ans = 0;
for (; n && x; --x) {
if (n >= a[x]) {
n -= a[x];
ans = a[x];
}
}
printf("Case %d: %d\n", t, ans);
}
}
return 0;
}


## 【TopCoder SRM714】ParenthesisRemoval

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3000;
const int MOD = 1000000007;

int n,ans;
char s[N];

class ParenthesisRemoval {
public:
int countWays(string ss) {
n = ss.size();
for (int i=0;i<ss.size();i++) {
s[i] = ss[i];
}
ans = 1;
for (int i=0,pfx=0;i<n;i++) {
if (s[i] == '(') {
++pfx;
} else {
ans = (LL)ans * (pfx--) % MOD;
}
}
return ans;
}
private:
};