## 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|$
Category: 数论
莫比乌斯反演与容斥原理
退役前一直想把莫比乌斯反演与容斥原理统一在一起,奈何自己水平不足,只能作罢。
这次把《组合数学》、《具体数学》、《初等数论》的相关内容读了一遍,总算是完成了这个遗愿:
mobius_and_inclusion_exclusion_principle
Download:http://oi.cyo.ng/wp-content/uploads/2018/03/mobius_and_inclusion_exclusion_principle.pdf
拓展阅读1:http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion
拓展阅读2:http://vfleaking.blog.uoj.ac/blog/87
【BZOJ 4589】Hard Nim
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4589
解题报告
我们考虑用SG函数来暴力DP
显然可以用FWT来优化多项式快速幂
总的时间复杂度:$O(n \log n)$
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]; inline int read() { 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] 成绩比较
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4559
神犇题解:http://blog.lightning34.cn/?p=286
解题报告
仍然是广义容斥原理
可以推出$\alpha(x)={{n-1}\choose{x}} \prod\limits_{i=1}^{m}{{{n-1-x}\choose{R_i-1}}\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}}$
我们发现唯一的瓶颈就是求$f(i)=\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}$
但我们稍加观察不难发现$f(i)$是一个$n$次多项式,于是我们可以用拉格朗日插值来求解
于是总的时间复杂度:$O(mn^2)$
Code
这份代码是$O(mn^2 \log 10^9+7)$的
实现得精细一点就可以把$\log$去掉
#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]; inline int read() { 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() { n = read(); m = read(); K = read(); for (int i=1;i<=m;i++) { u[i] = read(); } for (int i=1;i<=m;i++) { r[i] = read(); } //预处理组合数 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!
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
神犇题解:https://oi.men.ci/bzoj-4318/
解题报告
设$p_i$为第$i$个操作成功的概率
设$E_{(i,x^3)}$为以第$i$个位置为结尾,$($极长$1$的长度$x)^3$的期望
$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)$
然后就可以直接维护,然后再根据期望的线性加入答案就可以辣!
时间复杂度:$O(n)$
另外,似乎直接算贡献也可以?
可以参考:http://blog.csdn.net/PoPoQQQ/article/details/49512533
Code
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { 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() { int n=read(); 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
相关链接
题目传送门:http://agc015.contest.atcoder.jp/tasks/agc015_f
解题报告
我们写出使答案最大且值最小的序列,不难发现这是一个斐波那契数列
进一步发现,这条主链的每一个点只会引申出一条支链,且支链不会再分
所以我们可以暴力算出了$\log n$条链,共$\log ^ 2 n$对数,然后暴力算贡献
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]; inline LL read() { 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--) { LL A = read(), B = read(); solve(min(A, B), max(A, B)); } return 0; }
【日常小测】航海舰队
相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_day1-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_day1-solutions.pdf
解题报告
之前在BZOJ上看过这道题,然后当时嫌麻烦没有写
今天刚好考到,然后就被细节给搞死了_(:з」∠)_
一句话题解就是:用FFT做矩阵匹配
详细一点的话,大概就是:
先用FFT做一遍0/1矩阵匹配,求出能放阵型的位置
然后BFS出能到达的位置
最后再做一遍FFT求出每个点被覆盖了多少次
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
【日常小测】魔术卡
相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/20170614-statement.pdf
题目大意
给你$m(m \le 10^3)$种,第$i$种有$a_i$张,共$n(n = \sum\limits_{i = 1}^{m}{a_i} \le 5000)$张卡
现在把所有卡片排成一排,定义相邻两个卡片颜色相同为一个魔术对
询问恰好有$k$个魔术对的本质不同的排列方式有多少种,对$998244353$取模
定义本质不同为:至少有一位上的颜色不同
解题报告
一看就需要套一个广义容斥原理
于是问题变为求“至少有$x$个魔术对的方案数”
于是我们可以钦定第$i$种卡片组成了$j$个魔术对
然后用一个$O(n^2)$的$DP$来求出至少有$x$个魔术对的方案数
为了方便去重,我们先假设相同颜色的卡片有编号,最后再依次用阶乘除掉
考试的时候就是这里没有处理好,想的是钦定的时候直接去重,但这样块与块之间的重复就搞不了,于是$GG$了
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]; inline int read() { 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); m = read(); n = read(); K = read(); for (int i = 1; i <= m; i++) { a[i] = read(); } 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】上帝与集合的正确用法
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3884
官方题解:http://blog.csdn.net/popoqqq/article/details/43951401
解题报告
根据欧拉定理有:$a^x \equiv a^{x \% \varphi (p) + \varphi (p)} \mod p$
设$f(p)=2^{2^{2 \cdots }} \mod p$
那么有$f(p) = 2^{f(\varphi(p)) + \varphi(p)} \mod p$
如果$p$是偶数,则$\varphi(p) \le \frac{p}{2}$
如果$p$是奇数,那么$\varphi(p)$一定是偶数
也就是说每进行两次$\varphi$操作,$p$至少除$2$
所以只会递归进行$\log p$次
总时间复杂度:$O(T\sqrt{p} \log p)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { 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) { printf("%d\n", f(read())); } return 0; }
【日常小测】最长路径
相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf
解题报告
首先我们要熟悉竞赛图的两个结论:
- 任意一个竞赛图一定存在哈密尔顿路径
- 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通
现在考虑把强连通分量缩成一个点,并把新点按照哈密尔顿路径排列
那么$1$号点可以到达的点数就是$1$号点所在的$SCC$的点数加上$1$号点可以到达的其他$SCC$点数和
设$f_i$为$i$个点带标号竞赛图的个数
设$g_i$为$i$个点带标号强连通竞赛图的个数
有$f_i = 2^{\frac{n(n-1)}{2}}$
又有$g_i = f_i – \sum\limits_{j = 1}^{i – 1}{{{i}\choose{j}} g_j f_{i – j}}$
于是我们枚举$1$号点所在$SCC$的点数$i$和$1$号点可到达的其他$SCC$的点数和$j$
$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]; inline int read() { 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); n = read(); MOD = read(); 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
相关链接
题目传送门:http://codeforces.com/contest/749/problem/E
官方题解:http://codeforces.com/blog/entry/49186
解题报告
考虑从期望的定义下手
就是要求所有区间的逆序对的和
于是我们枚举右端点,然后算贡献
用$BIT$来维护,时间复杂度:$O(n \log n)$
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]; inline int read() { 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() { n = read(); for (int i = 1; i <= n; i++) { p[i] = read(); } 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
相关链接
题目传送门:http://codeforces.com/contest/812/problem/E
官方题解:http://codeforces.com/blog/entry/52318
解题报告
我们发现,如果操作同叶子结点的深度奇偶性不同的结点
那么对手总可以操作刚刚你操作的那些苹果
所以结果只与深度同叶子结点奇偶性相同的点有关
更进一步观察发现,实质上就是这些点组成的$NIM$游戏
于是乘一乘、加一加就好了
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]; int head[N], nxt[N], to[N], cnt[M]; inline int read() { 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]++; to[++E] = v; nxt[E] = head[u]; head[u] = E; } 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 n = read(); for (int i = 1; i <= n; i++) { v[i] = read(); } for (int i = 2; i <= n; i++) { AddEdge(read(), 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)
相关链接
题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
解题报告
这题告诉我们,这类题可以高斯消元做
裸做是$O(n^3)$的,非常不科学
这题我们发掘性质,如果从叶子开始一层一层往上消,高斯消元那一块可以做到$O(n)$
然后再算上逆元的话,总的时间复杂度:$O(n \log n)$
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]; inline int read() { 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; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } 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 n = read(); for (int i = 1; i < n; ++i) { int u = read(), v = read(); AddEdge(u + 1, v + 1, read()); } 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
相关链接
题目传送门:http://poj.org/problem?id=3922
神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2012/12/19/2825539.html
解题报告
根据$k = 1$的情况,我们发现在二进制下,我们取走最低位的$1$,对手取不走较高位的$1$
所以如果不是二的整次幂,那么先手必胜
再来看看$k = 2$的情况
根据$HINT$我们把每个整数拆成若干个不同、不相邻的斐波那契数之和,表示成二进制状态
之后跟据$k = 1$时的推论,我们取走最低位的$1$,对手不能直接取走较高位的$1$
先在我们看我们依赖拆分数列的哪些性质:
存在一种拆分使得选中的项的任意相邻两项超过$k$倍
于是我们尝试构造拆分数列$a_i$
我们设$b_i$为$a_1 \to a_i$能拼出的极长的前缀长度
不难发现$a_i = b_{i-1}+1, b_i=a_i+b_j$,其中$j$尽可能大,且$a_j k < a_i$
于是这题就做完啦
似乎这个问题还是博弈论里的一个经典问题,叫”$k$倍动态减法问题”
似乎某年国家集训队论文里还提出了另外的算法,对于某些数据会更优
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]; inline int read() { 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) { n = read(); k = read(); 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
相关链接
题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14595&rd=16883
解题报告
不难发现,这就是统计括号匹配的方案数
不会的同学可以先去切BZOJ 3622
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: };