## 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
Download:https://oi.qizy.tech/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; }
【日常小测】航海舰队
相关链接
题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_day1-statements.pdf
官方题解:https://oi.qizy.tech/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
【日常小测】魔术卡
相关链接
题目传送门:https://oi.qizy.tech/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; }