Posts

闲言 比赛链接：传送门 没有代码，放心食用。 A Find Subsequence （WA了一晚上，回来把树状数组重写了一下就过了？？？） 树状数组 + DP 令dp[i]表示前$i$个元素中，以a[i]结尾的只出现一次的子序列的数目。 a[i]在之前未出现过： $$dp[i]=1+\sum_{k=1}^{i-1}dp[k]$$ a[i]在之前出现过，考虑上一次出现的位置。显然当前位置使得上一次出现的位置之前的贡献变成$0$，同时处在区间$[last[a_i], i-1]$的贡献不改变。 $$dp[i]=\sum_{k=last[a_i]}^{i-1}dp[k]$$ dp[last[a[i]]]将变成0。 B operation ((a & b) + (a | b)) >> 1等价于(a + b) >> 1 最后一次合并可以等价为，将数组从中划分成两半，分别操作完后再合并 由于可能的答案很少，考虑枚举分割点记忆化搜索。 C 翻墙之旅 10.2组队训练有一样的题：Gym 103306A Alice Birthday SoSDP 令所有点构成的点集为$sn$，考虑一个包含点1的点集$s$，令f[s]表示使得$s$中只有一个连通分量的（点集内部的）删边方案数，cnt[s]表示点集$s$内的边数。在$s$中，点1一定能到达连通分量内的所有点，且此时外部的所有的边都可以选择删或者不删，那么该状态对$s$内的所有点的贡献即为$2^{cnt[sn-s]}\times f[s]$。 cnt[s]的计算不再赘述，关键讲f[s]： $s$内所有边的存在形式有$2^{cnt[s]}$种，减去有多个连通分量的情况即为只有一个连通分量的数目， $$2^{cnt[s]}-\sum_{s_0 \subset s} f[s_0]\times 2^{cnt[s-s_0]}$$ 使用SoSDP（子集DP）计算，为了避免重复计算，可以限定$s_0$中包含$s$的lowbit，或者其它的某点。 1 2 3 for (int s = 0; s < bit[n]; s++) for (int s0 = (s - 1) & s; s0; s0 = (s0 - 1) & s) if (s0 & (s & -s)) ....

一直没啥想写的，不过最近又看见一道和欧拉示性数公式相关的思维题，所以萌生出了写这篇博客的想法。 首先是关于平面图欧拉示性数公式的定义： 设$G$是一个连通的平面图，顶点的数目为$V$，边的数目为$E$，面的数目为$F$，则有$$V+F-E=2$$ 下面使用数学归纳法进行证明： 当$E=0$时，有$V=1,F=1$，等式显然成立。 假设当$E=k$时等式成立，下面考虑$E=k+1$的情形。 当图中无环时易知$V=k+2,F=1$，等式显然成立。 反之，我们设$e$为环中的一条边，那么对于图$G\setminus\set{e}$由假定知等式成立（即为$E=k$的情形，令其$V=v_0,F=f_0$，则$v_0+k-f_0=2$）。那么对于图$G$我们有$V=v_0,E=k+1,F=f_0+1$，因此等式也成立。 综上，由数学归纳法可知等式对于$E\geq0$的情形皆成立。 具体使用 声明 下面这种方法只在本人太闲了弄出来玩的，实际体验并不一定好。 简单来说就是固定了边数，在使点数尽可能小，从而使之面的数目最大化。 CSUST OJ 1066 被打脸的潇洒哥 题目描述 平面上有n个圆，求使这n个圆两两相交（即每两个圆之间恰好有两个交点）后最多能把平面划分成多少个区域。 对于圆这样的图形，我们不方便计算它的各项参数，可以直接将其边无限细分，即假定点数为$m$，则边也为$m$。由于$m$无穷大，两圆相交时并不会产生新的边，但是会减去重叠的两个点。 所以，当一共有$n$个圆时，图上的各项参数为 $$E=n\times m,V=n\times m-2\times {n \choose 2},F=2+E-V=2+n\times(n-1)$$ 1 2 3 4 5 6 7 8 9 int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); for (cin >> T; T--; ) { cin >> n; if (n == 0) {cout << 1 << '\n'; continue;} cout << 2 + (n - 1) * n << '\n'; } return 0; } HDU 2050 折线分割平面...

比赛链接 （ps: 写题请到Problems页面） 可能算详解？代码部分随缘写。 题解 A. NO GAMES NO LIFE 题目描述 共有$n$（偶数）堆棋子，第$i$堆初始为$1 \leq a_i \leq 100$，玩家每次必须选$\frac{n}{2}$堆棋子并使之减少正整数个，每次每堆减少的值可以不同。 Bai先手，Kong后手。玩家无法选择时失败。 基准思路： 谁先导致场上出现被取完的堆必定输掉游戏 如果选了1则必须减少到0 考虑数字1的数量，令$cnt[i]$为数字$i$的个数。 $cnt[1] > \frac{n}{2}$时玩家必选到1，必输 $1 \leq cnt[1] \leq \frac{n}{2}$可以增加1的数量使下家面临第一个局面，必胜 $cnt[1] = 0$时考虑2的数量 $cnt[2] > \frac{n}{2}$玩家必选到2，必然产生1，且个数不大于$\frac{n}{2}$，必输 $1 \leq cnt[2] \leq \frac{n}{2}$可以增加2的数量使下家面临上一个局面，必胜 $cnt[2] = 0$时考虑3的数量 $\dots$ 显然，问题只与最小值的数量有关。 B. 整除数 题目描述 找到最小的$n$位能被$m$整除的自然数 $n=1$时，直接输出0 找到最小的$n$位整数$10^{n-1}$，求最少还需多少使得其能被$m$整除，即$(m - 10^{n-1} % m) \mod m$，如果加上后位数不变则为答案，否则无解。 C. 网格图 题目描述 从$(0,0)$，每次你只可以往正东走，或者往正北走(即x，y坐标增大的方向)。但是你每次走的长度可以是任意正实数。这个网格上有$\mathit n$个景点，你可以经过任意个景点，问：以每个景点为终点时，分别能走出多少条不同路线。(当且仅当经过的景点不同时才被视为不同路线) 取模$1e9+7$. 由于是走正实数，某点左下方的所有景点都可以直接到达该点。 比较特殊的是与之处在同一行列的点，这里就只需加上到最近的那个点的方案数。 思路，按照$(x,y)$从小到大排序，只要保证到某点时，所有处于其左下方的点都已经更新答案，那么该点的方案就是它们求和再+1（从$(0,0)$直达）。 同时要维护行列点数目，每次更新答案后再更新即可。 D. 修机器 题目描述...

很抱歉的是，关于吉老师线段树历史最值问题本文尚并未涉及。 （开个新坑） 只是最近写题时觉得它让我对线段树的使用有了新的理解，故做记录。 我的理解 吉老师线段树不同于朴素线段树的地方在其维护方式，在维护区间最大（小）值的同时维护了严格次大（小）值。 这使其对某些问题有着几近玄学的复杂度。。。 一部分使用标记，另一部分使用暴力修改，单次修改变成了$O(\log^2 n)$。 初次看到时，我是真的无法接受，并且将其作为假算法略过了（顺带一提，我当时在写下面贴的模板题时考虑维护最大，最小值TLE了） 然后上次ccpc压力测试赛上又碰见了Lowbit，写的时候突然发觉这其实是个很朴素的想法，一部分考虑暴力从而减少整体的复杂度（算是均摊？）。 线段树维护值时怎么就不能用呢？ 题目 HDU5306 Gorgeous Sequence 题目描述 x y t: For every $x≤i≤y$, we use min(ai,t) to replace the original ai’s value. x y: Print the maximum value of ai that $x≤i≤y$. x y: Print the sum of ai that $x≤i≤y$. 知道思路后，题目就太板子了，懒得重写了（将就看，不会真有人看吧，不会吧，不会吧） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 #include <cstdio> typedef long long i64; #define gc() (p1 == p2 ?...

$\text{Baby Step/Giant Step Algorithm}$ 用于解决这样一类同余方程的方法 $$a^x \equiv b\pmod c$$ 结合原根的知识还能解决模数有原根的$N$次剩余问题 $$x^n \equiv b\pmod c$$ 基础问题 $a^x\equiv b\pmod c$ 具体来说，BSGS的思路就是分块预处理+hash。 下面分情况讨论： Case gcd(a,c) == 1 由欧拉定理可知$x$的取值范围不会大于$\varphi(c)$，我们直接取$x<c$即可。 $a,c$互素时，存在$a$在模$c$意义下的逆元。 令分块的大小为$\lceil\sqrt c\rceil$，即我们将解的形式限定为$x=A\times\lceil\sqrt c\rceil - B,A,B\in[0,\lceil\sqrt c\rceil]$，直接将$a^B$的部分放到同余式右侧。 现在需要解决的问题变成： $$a^{A\times\lceil\sqrt c\rceil}\equiv b\times a^{B}\pmod c$$ 首先预处理，枚举$b\times a^B$的取值，并将其存下来(hash) 枚举$A$的取值，并查看是否存在对应的$B$是得两侧相等。 得到结果，或者无解。 Case gcd(a,c) != 1 一个比较好的想法是，我们将其转换成互素的情况。 由于$ax\equiv b\pmod c, g=\gcd(a, b, c)$可以转化成 $$\frac{a}{g}x\equiv \frac{b}{g}\pmod{\frac{c}{g}}$$ 同样的，我们也可以不断去消去$c$中与$a$不互素的部分，从而达到目的 具体步骤为： $a\times a^{x-1}\equiv b\pmod c$ $g=(a,c)$，若$g\nmid b$则无解 $\frac{a}{g}\times a^{x-1}\equiv \frac{b}{g}\pmod{\frac{c}{g}}$ 循环操作直到$(a,c)=1$或$\frac{a^k}{G}=\frac{b}{G}$ 代码模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 ll qpow(ll x, ll n, ll mod) { ll res = 1LL; for (x %= mod; n > 0LL; n >>= 1, x = x * x % mod) { if (n & 1LL) res = res * x % mod; } return (res + mod) % mod; } // a^x EQUIV n (MOD mod), and gcd(a, mod) = 1 ll BSGS(ll a, ll n, ll mod) { a %= mod, n %= mod; if (n == 1LL || mod == 1LL) return 0LL; unordered_map<ll, ll> bs; ll S = sqrt(mod) + 1; ll base = n; for (ll k = 0, val = base; k <= S; k++) { bs[val] = k, val = val * a % mod; } base = qpow(a, S, mod); for (ll x = 1, val = base; x <= S; x++) { if (bs....

随机数据下十分优秀的处理区间赋值操作的暴力数据结构。 本篇只给出split和assgin操作的代码，其它更暴力的就不提了，一般的能用的情况下有这两个应该就够了。 基础操作 思路十分清晰简单（暴力），维护一个有序的区间段的集合，每段区间带上其属性。 拆分前用lower_bound找到对应的位置，删去中间原来所有的后，再加入新的那段。 注意，set.erase(begin, end)为前闭后开，所以在找右端点时应该找R + 1。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 struct ODT { map<ll, ll> mp; ODT(ll _, ll unit) { mp[_ - 1] = unit; } void split(ll x) { mp[x] = prev(mp.upper_bound(x))->se; } void assign(ll l, ll r, ll v) { split(l), split(r + 1); auto it = mp....

对于二次剩余式 $$x^2\equiv n\pmod p$$ 其中$p$为奇素数，且$p \nmid n$，求$x$。 Cipolla算法 $Cipolla$和之前就写过的三次剩余是同一个思路，所以我在写完$Cipolla$后感觉好像什么都没变。 构造一个环 $$R=\frac{\mathbb{Z}_p[x]}{x^2-a}=\set{\alpha+\beta Y | \alpha,\beta,\in\mathbb{Z}_p,Y^2=a}$$ 可知， 对于$z\in R$，即$z=\alpha+\beta Y$，有$z^{p-1}\equiv 1\pmod{p}$ 如果$z^{\frac{p-1}{2}}=\beta_0 Y$，则有$(\beta_0 Y)^2\equiv\beta_0^2a\equiv1\pmod{p}$，即$\sqrt{a}\equiv\beta_0^{-1}\pmod{p}$ 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 mt19937 rng(__builtin_ia32_rdtsc()); inline ll randint(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } ll qpow(ll x, ll n, ll mod) { ll res = 1LL; for (x %= mod; n > 0LL; n >>= 1, x = x * x % mod) { if (n & 1LL) res = res * x % mod; } return (res + mod) % mod; } struct R { ll a, p, x, y; R(ll _a, ll _p) : a(_a), p(_p) { x = 1LL, y = 0LL; } void rand() { x = randint(0, p - 1); y = randint(0, p - 1); } R &operator*=(const R &rhs) { ll _x = (x * rhs....

$\forall a<m,(a, m)=1$，均有$a^{\varphi(m)}\equiv1\pmod{m}$，于是就有欧拉定理： $$a^n\equiv a^{n \mod \varphi(m)} \pmod{m}$$ 对于$n$取值较大的情况（比如$10^{30000}\mod 13$），欧拉降幂的作用不可忽视，但局限的是必须满足$(a,m)=1$才能有上式恒成立。 由于上述形式流传甚广，读者大抵早已熟记于心，这里便不再赘述。本文的最终目的是介绍另一个适用范围更广的版本，即所谓拓展欧拉定理。 $$a^n\equiv a^{n \mod \varphi(m) + \varphi(m)} \pmod{m} \quad \textrm{if }n \geq \varphi(m)$$ 证明 - 欧拉定理 证明方法来自《初等数论》柯召 考虑这样一组数$r_1,r_2,\dots,r_{\varphi(m)}$，满足$\forall r_i\in \set{r_1,r_2,\dots,r_{\varphi(m)}},\mathrm{s.t.}(r_i,m)=1$，同时$\forall i\ne j,(r_i,r_j)=1$。 当$(a,m)=1$，我们可以得到: $$ \begin{aligned} (ar_1)(ar_2)\dots(ar_{\varphi(m)}) & \equiv & r_1r_2\dots r_{\varphi(m)}\pmod{m}\newline (r_1r_2\dots r_{\varphi(m)})\times (a^{\varphi(m)} - 1) & \equiv & 0\pmod{m} \end{aligned} $$ 由于$(r_i,m)=1$，可知$(r_1r_2\dots r_{\varphi(m)},m)=1$，故$a^{\varphi(m)}\equiv1\pmod{m}$。 拓展情况 这里的讨论是基于$(a,m)\ne1$的情况来的，因为当$(a,m)=1$成立时直接用欧拉定理就能推知上式成立。 由于$n=\lfloor\frac{n}{\varphi(m)}\rfloor\times\varphi(m) + \langle n \rangle_{\varphi(m)}\geq\varphi(m)$，不妨令$n=\lambda\varphi(m) + \langle n\rangle_{\varphi(m)},\lambda\in\mathbb{Z}^+$。 问题转换为证明$a^{\lambda\varphi(m)}\equiv a^{\varphi(m)}\pmod m$，这可以从$\lambda=2$的情况递推过去，下面证明$\lambda=2$时同余式成立。 将$a$因式分解，其中与$m$互素的部分可以直接使用欧拉定理消去，剩余的素数幂乘积分开后的情况和原问题同一结构，所以只考虑单个素数情况即可。原问题等价为证明：$p^{2\times\varphi(m)}\equiv p^{\varphi(m)}\pmod m,p\in Prime$。...

题外话：好像文章有点长，本地调的时候加载目录都掉帧了。虽然一度想删点题目，但思前想后还是一题没删，总感觉每一题都代表了一种典型，实在不好取舍，或许只写推导会好一点，但还是有点怕代码的实现未有较好交代。。。 好了，闲言少叙。 本篇是平时刷的反演题目的解题记录，个人认为这方面的知识点和写题目是有点脱节的，题目要么是纯套路，要么就是有些不太友好的小技巧。 题目来源：Luogu, LibreOJ, HDU等。 P3312 [SDOI2014]数表 题目描述 有一张 $n\times m$ 的数表，其第 $i$行第 $j$ 列（$1\le i\le n$，$1\le j\le m$）的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。 输入包含多组数据。 输入的第一行一个整数 $Q$ 表示测试点内的数据组数 接下来 $Q$ 行，每行三个整数 $n$，$m$，$a$（$|a|\le 10^9$）描述一组数据。 答案模$2^{31}$。 显然有答案为： $$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma(\gcd(i,j))[\gcd(i,j)\leq a] \newline$$ 先不考虑大小限制，之后将其转换成离线求值+动态加入贡献的问题。 $$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}\sigma(\gcd(i,j))&=\sum_{d=1}^{n}\sigma(d)\sum_{i=1}^{[\frac{n}{d}]}\sum_{j=1}^{[\frac{m}{d}]}[\gcd(i,j)=1]\newline &=\sum_{d=1}^{n}\sigma(d)\sum_{k=1}^{[\frac{n}{d}]}\mu(k)\sum_{i=1}^{[\frac{n}{d}]}\sum_{j=1}^{[\frac{m}{d}]}\newline &=\sum_{d=1}^{n}\sigma(d)\sum_{k=1}^{[\frac{n}{d}]}\mu(k)[\frac{n}{dk}]\times[\frac{m}{dk}]\newline &=\sum_{T=1}^{n}[\frac{n}{T}][\frac{m}{T}]\sum_{d\mid T}\sigma(d)\mu(\frac{T}{d}) \end{aligned} $$ 只有当$\sigma(n)\leq a_i$，才将$\sigma(n)$的贡献计入，那么我们可以离线处理，用树状数组维护，$O(Q\sqrt{n}\log{n})$。 取模$2^{31}$标志着需要$32$位整型自然溢出，当然最终还是要变成无符号整数，这里可以写成ans & 2^{31}-1。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include <bits/stdc++....

先给出全部公式： $$ \begin{aligned} & \sin^{2n}{x}=\frac{1}{2^{2n-1}}\left[ \sum_{k=0}^{n-1}{2n \choose k}(-1)^{n-k}\cos{2(n-k)x} + \frac{1}{2}{2n \choose n} \right] \newline & \sin^{2n+1}{x}=\frac{1}{2^{2n}}\sum_{k=0}^{n}{2n+1 \choose k}(-1)^{n-k}\sin{(2n-2k+1)x} \newline & \cos^{2n}{x}=\frac{1}{2^{2n-1}}\left[ \sum_{k=0}^{n-1}{2n \choose k}\cos{2(n-k)x}+\frac{1}{2}{2n \choose n} \right] \newline & \cos^{2n+1}{x}=\frac{1}{2^{2n}}\sum_{k=0}^{n}{2n+1 \choose k}\cos{(2n-2k+1)x} \newline \end{aligned} $$ 虽然看起来原本简单的式子被极大地复杂化了，但其实在很多命题中，它们起着十分不错的化简作用。 Proof 由欧拉恒等式$e^{ix}=\cos{x}+i\sin{x}$有 $$ \begin{cases} \sin x &=& \frac{e^{ix}-e^{-ix}}{2i} \newline \cos x &=& \frac{e^{ix}+e^{-ix}}{2} \end{cases} $$ 可以得到 $$ \begin{aligned} \sin^{2n}{x} & = \left(\frac{e^{ix}-e^{-ix}}{2i}\right)^{2n} \newline & = \frac{1}{(-1)^{n}2^{2n}}\sum_{k=0}^{2n}{2n \choose k}{(-1)^{2n-k}e^{ixk-ix(2n-k)}} \newline & = \frac{1}{2^{2n}}\sum_{k=0}^{2n}{2n \choose k}(-1)^{(n-k)}e^{i2(n-k)x} \newline & = \frac{1}{2^{2n}}{2n \choose n}+\frac{1}{2^{2n-1}}\sum_{k=0}^{n-1}{2n \choose k}(-1)^{n-k}\cos{2(n-k)x}\newline \newline \cos^{2n}{x} & = \left(\frac{e^{ix}+e^{-ix}}{2}\right)^{2n} \newline & = \frac{1}{2^{n}}\sum_{k=0}^{2n}{2n \choose k}{e^{i2(k-n)x}} \newline & = \frac{1}{2^{2n}}\left[\sum_{k=0}^{n-1}{2n \choose k}{e^{i2(k-n)x}}+\sum_{k=0}^{n-1}{2n \choose k}{e^{i2(n-k)x}}\right] + \frac{1}{2^{2n}}{2n \choose n} \newline & = \frac{1}{2^{2n}}{2n \choose n}+\frac{1}{2^{2n-1}}\sum_{k=0}^{n-1}{2n \choose k}{\cos2(n-k)x} \end{aligned} $$...