- 博客(129)
- 收藏
- 关注
RSS订阅
原创 反演
二项式反演∑i=jn(−1)i−j(ni)(ij)=(nj)[n−j=0]①\sum_{i=j}^{n}(-1)^{i-j}{n\choose i}{i\choose j}={n\choose j}[n-j=0]\quad ①i=j∑n(−1)i−j(in)(ji)=(jn)[n−j=0]①证明∑i=jn(−1)i−j(ni)(ij)=∑i=jn(−1)i−j(nj)(n−ji−j)=(nj)∑i=jn(−1)i−j(n−ji−j)=(nj)∑i=0n−j(−1)i(n−ji)=(nj)(
2021-03-08 14:35:35
112
原创 多项式模板
#include<bits/stdc++.h>#define ll long longusing namespace std;const int N=2100009;const ll mod=998244353,G=3;//G是mod的原根int n,m;ll a[N],b[N];int bit,lim,r[N];//lim表示当前运算的长度ll ln[N],inv[N],tmp[N],diff[N],integral[N],sqr[N],quotient[N],remain
2021-02-15 14:23:10
90
原创 网络流模板
https://www.luogu.com.cn/problem/P3376#include<bits/stdc++.h>#define ll long longusing namespace std;const int N=209,M=5009;const ll inf=2e18;int ver[M<<1],head[N],ne[M<<1],tot=1,n,m,st,en,d[N];ll edge[M<<1],ans=0;void add(i
2021-04-10 13:03:31
93
原创 线段树模板
https://www.luogu.com.cn/problem/P3373#include<bits/stdc++.h>#define ll long longusing namespace std;const int N=200009;int n,m;ll p,sum[N<<2],add[N<<2],mul[N<<2];void pushdown(int o){ int lc=o<<1,rc=o<<1|1;
2021-04-08 13:34:04
94
原创 LCA模板
https://www.luogu.com.cn/problem/P3379#include<bits/stdc++.h>using namespace std;const int N=500009;int n,f[N][20],t,d[N],m,root;vector<int>w[N];void bfs() { queue<int>q; memset(d,0,sizeof(d)); d[root]=1,q.push(root);
2021-04-07 18:47:55
106
原创 最短路模板
https://www.luogu.com.cn/problem/P4779#include<bits/stdc++.h>#define ll long long#define inf 1000000000000000009using namespace std;const int N=200009;struct node{ int to; ll len; node(int x,ll y):to(x),len(y){} bool operator &l
2021-04-07 18:46:27
70
原创 第一类斯特林数·行
题目求xn‾=∑i=0n[ni]xix^{\overline{n}}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^ixn=i=0∑n[ni]xi在取模modmodmod意义下思路x2k‾=xk‾(x+k)k‾x^{\overline{2k}}=x^{\overline{k}}(x+k)^{\overline{k}}x2k=xk(x+k)k。假设知道xk‾x^{\overline{k}}xk就能快速求出(x+k)k‾(x+k)^{\over
2021-03-30 22:35:44
106
原创 D 动态序列
题目https://ac.nowcoder.com/acm/contest/13504/D给出n(1≤n≤100000)n(1\le n\le 100000)n(1≤n≤100000)个整数ai(1≤ai≤109)a_i(1\le a_i\le 10^9)ai(1≤ai≤109)的序列，有q(1≤q≤105)q(1\le q\le 10^5)q(1≤q≤105)个询问，设序列长度为lenlenlen，序号从111开始，每个询问有如下操作：1 b：序列中所有数乘以整数b(1≤b≤109)1
2021-03-28 20:49:19
178
原创 如何优雅地求和
题目https://uoj.ac/problem/269给定mmm次多项式f(x),n,xf(x),n,xf(x),n,x，求Q(f,n,x)=∑i=0nf(i)(ni)xi(1−x)n−iQ(f,n,x)=\sum_{i=0}^{n}f(i){n\choose i}x^i(1-x)^{n-i}Q(f,n,x)=i=0∑nf(i)(in)xi(1−x)n−if(x)f(x)f(x)给定点值表示法。n≤109n\le 10^9n≤109思路把多项式转换成下降幂表示，假设f(x)=∑i=0
2021-03-28 20:29:01
120
原创 点值转下降幂
对于n−1n-1n−1次多项式f(x)f(x)f(x)，给定a0,a1..an−1a_0,a_1..a_{n-1}a0,a1..an−1，其中ai=f(i)a_i=f(i)ai=f(i)，求f(x)f(x)f(x)得下降幂表示。即f(x)=∑i=0n−1fixi‾[x≥i]f(x)=\sum_{i=0}^{n-1}f_ix^{\underline{i}}[x\ge i]f(x)=i=0∑n−1fixi[x≥i]求出fif_ifif(i)=∑j=0n−1fjij‾[i≥j]0≤i≤n
2021-03-28 19:43:34
153
原创 简单的函数
题目https://loj.ac/p/6053求∑i=1nf(i) mod 109+7\sum_{i=1}^{n}f(i)\ mod\ 10^9+7i=1∑nf(i) mod 109+7f(1)=1f(1)=1f(1)=1f(pc)=p⊕cf(p^c)=p\oplus cf(pc)=p⊕c，ppp为质数f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(ab)=f(a)f(b)，(a,b)=1(a,b)=1(a,b)=1思路Min25Mi
2021-03-24 19:22:33
59
原创 Sanrd
题目https://uoj.ac/problem/188求∑i=lrf(i)\sum_{i=l}^{r}f(i)i=l∑rf(i)f(i)f(i)f(i)是iii的次大质因子，如果是素数或111，则为000。l+r≤1011l+r\le 10^{11}l+r≤1011思路考虑Min25Min25Min25筛时的SSS函数的dpdpdp，素数部分贡献是000，则只有合数的贡献S(n,j)=∑i=j+1π(n)∑e=1pie≤n(f(pie)[e>1]+∑k=2⌊npie⌋f(piek
2021-03-23 20:01:14
104
原创 Biological Software Utilities
题目https://codeforces.com/gym/102956/problem/G给一个nnn，问有多少棵nnn个节点的树满足完美匹配。思路首先两两配对，nnn一定是偶数。另外每棵树只对应一种匹配方式，因为树的叶子节点一定选，选完后把多余的的边和点删掉，一直下去，这样每次选方案是唯一的。所以从配对方式考虑，那么nnn个点两两配对的方案数是n!2n2n2!\dfrac{n!}{2^{\frac{n}{2}}\frac{n}{2}!}22n2n!n!然后每一对节点之间随意连边构成树
2021-03-22 15:06:43
258
原创 Min_25筛
题目一般要求∑i=1nF(i)n≤1010\sum_{i=1}^{n}F(i)\quad n\le 10^{10}i=1∑nF(i)n≤1010其中F(x)F(x)F(x)是积性函数。Min25Min25Min25筛能用的前提：质数处的f(p)f(p)f(p)值是关于ppp的低阶多项式，质数次方处的f(pe)f(p^e)f(pe)值可以快速计算。约定pip_ipi表示第iii个素数，下标从111开始P\mathbb{P}P表示素数的集合π(n)\pi(n)π(n)表示1∼n1\sim
2021-03-21 21:48:23
73
原创 Min_25筛模板
题目https://www.luogu.com.cn/problem/P5325定义积性函数f(x)f(x)f(x)，且f(pk)=pk(pk−1)(p为质数)f(p^k)=p^k(p^k-1)(p为质数)f(pk)=pk(pk−1)(p为质数),求∑i=1nf(i)\sum_{i=1}^{n}f(i)i=1∑nf(i)对109+710^9+7109+7取模。n≤1010n\le 10^{10}n≤1010。思路把f(p)=p2−pf(p)=p^2-pf(p)=p2−p拆成两个完全积性函
2021-03-18 20:41:14
77
原创 [国家集训队]Tree I
题目https://www.luogu.com.cn/problem/P2619给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有needneedneed条白色边的生成树。题目保证有解。思路凸优化裸题，要注意的就是，优先选白色(优先选黑色也行)，主要是同一斜率可能会切到很多点，那么就要有一个标准，要么选最小点，要么选最大。另外算答案时就乘上题目给的needneedneed。#include<bits/stdc++.h>#define ll long longusi
2021-03-16 14:14:01
118
原创 Imprecise Computer
题目https://codeforces.com/gym/102920/problem/E有两轮操作，每一轮，让1∼n1\sim n1∼n中的每个数字kkk和其他所有数字进行比较大小，如果两个数字之差大于等于222则能正确的比较大小，否则随机认为某个数字大，令ri(k)r_i(k)ri(k)为第iii轮时比kkk小的数字的个数，则dk=∣r1(k)−r2(k)∣d_k=|r_1(k)-r_2(k)|dk=∣r1(k)−r2(k)∣，现在给定ddd数组，问你经过两轮操作后是否可能出现ddd数组这种
2021-03-15 19:50:47
87
原创 分治FFT模板
#include<bits/stdc++.h>#define ll long longusing namespace std;const double Pi=acos(-1.0);const int N=2100009;const ll mod=998244353,G=3;//G是mod的原根ll a[N],b[N],c[N],d[N],f[N],p[N],p1[N],Gi,_inv;//Gi是原根的逆元,inv是lim的逆元int n,m,bit,lim,r[N];//lim表示
2021-03-13 13:58:27
63
原创 按位或
题目https://www.luogu.com.cn/problem/P3175刚开始你有一个数字000，每次给这个数按一定概率ororor上一个≤2n−1≤2^n−1≤2n−1的非负整数，第iii个数的概率为pip_ipi，保证和为111问这个数字到2n−12^n−12n−1的期望ororor次数。n≤20n≤20n≤20思路把数字看成集合，用min−maxmin-maxmin−max反演E(max(S))=∑T⊆S(−1)∣T∣−1E(min(T))E(max(S))=\sum_{T\su
2021-03-09 09:56:22
63
原创 Card Collector
题目有nnn种卡片，每一秒都有PiP_iPi的概率获得一张第iii种卡片，求每张卡片都至少有一张的期望时间。思路令max(S)max(S)max(S)表示集合SSS中每种卡片第一次出现时间的最大值，则E(max(S))E(max(S))E(max(S))为所求的值。根据min−maxmin-maxmin−max反演E(max(S))=∑T⊆S(−1)∣T∣−1E(min(T))E(max(S))=\sum_{T\subseteq S}(-1)^{|T|-1}E(min(T))E(max(S))
2021-03-08 16:38:25
70
原创 快速莫比乌斯变换
莫比乌斯变换定义函数fff的莫比乌斯变换为f^\hat ff^f^S=∑T⊆SfT\hat f_S=\sum_{T\subseteq S}f_Tf^S=T⊆S∑fT则有莫比乌斯反演fS=∑T⊆S(−1)∣S∣−∣T∣f^Tf_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}\hat f_TfS=T⊆S∑(−1)∣S∣−∣T∣f^T快速莫比乌斯变换FMT考虑如何快速快速进行莫比乌斯变换和反演。设f^Si=∑T⊆S[(S−T)⊆{1,2,...,i
2021-03-06 13:41:19
403
原创 着色方案
题目：https://ac.nowcoder.com/acm/problem/14604有nnn个木块，从左到右排成一排，你有kkk种颜色，每种颜色的可以涂cic_ici个木块，所有的颜色正好够涂所有的木块，即c1+c2+...+ck=nc_1+c_2+...+c_k=nc1+c2+...+ck=n。涂色时要求任意两块相邻木块不能同色，请统计出不同着色方案的总数。两种着色方案是不同的当且仅当两种方案至少有一个位置的木块颜色是不同的。思路：参考题目https://blog.csdn.net/
2020-11-17 20:35:39
246
原创 Erasing Vertices
题目：https://atcoder.jp/contests/agc049/tasks/agc049_a给你一个有向图，每次操作随机选一个点，删除该点并且删除所有该点能够到达的点。删除点的时候也要删除和点关联的边。求操作次数的期望。思路：首先缩点，因为同一个强连通分量里面的点是等价的，然后就是一个有向无环图删点操作。参考托米的游戏，每一个连通分量的贡献为该连通分量的大小所有能够到达该连通分量的大小的和\quad \\\frac{该连通分量的大小}{所有能够到达该连通分量的大小的和}所有能够到
2020-11-16 19:04:14
147
原创 组合数学常用公式
常用公式k(rk)=r(r−1k−1)(rk)=(r−1k)+(r−1k−1)(rk)=(−1)k(k−r−1k)(rm)(mk)=(rk)(r−km−k)∑k≤n(r+kk)=(r+n+1n)∑k=0n(km)=(n+1m+1)n,m≥0\begin{aligned}k{r\choose k}&=r{r-1\choose k-1}\\{r\choose k}&={r-1\choose k}+{r-1\choose k-1}\\{r\choose k}&=(-1)^k{k-
2020-11-14 19:14:06
233
原创 差分约束
设置超级源点000，假定所有数小于000。#include<bits/stdc++.h>#define inf 1000000007using namespace std;const int N=5009;struct node { int to,di; node(int x,int y):to(x),di(y) {}};int n,m,d[N],v[N],cnt[N];vector<node>w[N];int spfa() { queue&
2020-11-10 18:41:26
56
原创 最近公共祖先
#include<bits/stdc++.h>using namespace std;const int N=100009;int n,f[N][20],t,d[N];vector<int>w[N];void bfs() { queue<int>q; memset(d,0,sizeof(d)); d[1]=1,q.push(1); while(q.size()) { int x=q.front(),si;
2020-11-10 15:51:40
71
原创 树的直径
#include<bits/stdc++.h>using namespace std;const int N=100009;struct node { int to,di; node(int x,int y):to(x),di(x) {}};int n,ans=0,d[N];vector<node>w[N];void dfs(int x,int fa) { int si=w[x].size(); d[x]=0; for(int i
2020-11-10 15:33:04
50
原创 这是二叉搜索树吗？
题目：https://pintia.cn/problem-sets/994805046380707840/problems/994805070971912192一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，其左子树中所有结点的键值小于该结点的键值；其右子树中所有结点的键值大于等于该结点的键值；其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍
2020-11-09 21:28:26
217
原创 整数划分 V2
题目：将NNN分为若干个整数的和，有多少种不同的划分方式，例如：n=4n = 4n=4，{4}{1,3}{2,2}{1,1,2}{1,1,1,1}\{4\} \{1,3\} \{2,2\} \{1,1,2\} \{1,1,1,1\}{4}{1,3}{2,2}{1,1,2}{1,1,1,1}，共555种。由于数据较大，输出mod 109+7mod\;10^9 + 7mod109+7的结果即可。思路：参考问题分成两部分计算...
2020-11-08 21:05:24
73
原创 Sum of Powers
题目：https://csacademy.com/contest/round-32/task/sum-of-powers/给定NNN，MMM，KKK，考虑所有的多重子集{a1,a2,a3...ak}\{a_1,a_2,a_3...a_k\}{a1,a2,a3...ak}，满足a1+a2+...+ak=Na_1+a_2+...+a_k=Na1+a2+...+ak=N，求所有的多重子集的a1M+a2M+...akMa_1^M+a_2^M+...a_k^Ma1M+a2M+...akM。思
2020-11-08 10:45:14
223
原创 整数划分
** 题目：**http://www.51nod.com/Challenge/Problem.html#problemId=1201将NNN分为若干个不同整数的和，有多少种不同的划分方式，例如：n=6n = 6n=6，{6}{1,5}{2,4}{1,2,3}\{6\} \{1,5\} \{2,4\} \{1,2,3\}{6}{1,5}{2,4}{1,2,3}，共444种。由于数据较大，输出mod 109+7mod\;10^9 + 7mod109+7的结果即可。思路：https://blog.cs
2020-11-08 09:41:18
161
原创 「2017 山东一轮集训 Day7」逆序对
题目：https://loj.ac/problem/6077给定n,kn,kn,k ，请求出长度为nnn的逆序对数恰好为kkk的排列的个数。答案对109+710^9+7109+7取模。思路1：设aia_iai为数字iii对逆序数的贡献，则0≤ai≤i−10\le a_i\le i-10≤ai≤i−1。并且只要所有aia_iai满足该条件，都一定能构造出唯一的排列。所以问题变成有多少方案使得∑i=1nai=k,0≤ai≤i−1\sum_{i=1}^{n}a_i=k,0\le a_i\le i-
2020-11-07 21:02:05
220
原创 特殊背包
题目：有nnn个物品，第iii个物品的体积为iii，问有多少种方案凑成mmm体积。思路：如果正常背包，时间复杂度O(nm)O(nm)O(nm)。由于体积刚好是连续的，所以合法的方案等价于有多少种递减序列，数字和为mmm。可以这样构造递减序列，每次有两种决策。当前序列中的所有数字加111当前所有数字加111，并且在序列后放入数字111所以令f(i,j)f(i,j)f(i,j)表示当前有iii个数字，和为j且是递减序列的方案数，则f(i,j)=f(i−1,j−i)+f(i,j−i)f(i
2020-11-07 13:06:17
133
原创 背包方案数
题目：有nnn种物品，每种物品的体积为viv_ivi，有cic_ici个，问放入容量为mmm的背包有多少种方案。思路：除了可以用类似单调队列来维护决策之外还可以用容斥。设f(i,j)f(i,j)f(i,j)表示前iii个物品凑成体积为jjj的方案数，则有f(i,j)=f(i−1,j)+f(i,j−vi)−f(i−1,j−(ci+1)vi)f(i,j)=f(i-1,j)+f(i,j-v_i)-f(i-1,j-(c_i+1)v_i)f(i,j)=f(i−1,j)+f(i,j−vi)−f(i−
2020-11-06 19:11:04
63
转载 有限背包计数问题
题目：http://www.51nod.com/Challenge/Problem.html#problemId=1597你有一个大小为nnn的背包，你有nnn种物品，第iii种物品的大小为iii，且有iii个，求装满这个背包的方案数有多少。n≤105n\le 10^5n≤105思路：传送门传送门...
2020-11-05 12:56:59
106
原创 Divide and Sum
题目：http://codeforces.com/contest/1445/problem/D给定2n2n2n个数，分成两个数组p,qp,qp,q，ppp是非递减，qqq是非递增。f(p,q)=∑i=1n∣pi−qi∣f(p,q)=\sum_{i=1}^{n}|p_i-q_i|f(p,q)=∑i=1n∣pi−qi∣，计算所有f(p,q)f(p,q)f(p,q)的和。思路：...
2020-11-04 15:56:52
143
原创 Division
题目：http://codeforces.com/contest/1445/problem/C给定x,yx,yx,y，找到最大的zzz使得z∣x,y∤zz|x,y\nmid zz∣x,y∤z。1≤x≤1018,2≤y≤1091\le x\le 10^{18},2\le y\le 10^91≤x≤1018,2≤y≤109思路：y∤xy\nmid xy∤x，答案为xxxy∣xy|xy∣x，假设x=p1a1p2a2p3a3p4a4x=p_1^{a_1}p_2^{a_2}p_3^{a_3}p_4^{a_
2020-11-04 12:36:27
75
原创 Extreme Subtraction
题目：http://codeforces.com/contest/1443/problem/D给定一个数组，每次可以让前kkk个数字减111，或者后kkk个数字减111，请问能否使得所有数字变为000。思路：首先差分，把操作变成在差分数组上的操作，然后因为所有数字要变为000，所以我们知道最后的差分数组。分析一下即可。#include<bits/stdc++.h>#define ll long longusing namespace std;int T,a[30009],b[30
2020-11-04 12:23:33
83
原创 排列逆序数的期望
题目：随机生成1∼n1\sim n1∼n的排列，求逆序数的期望。思路：f(i,j)f(i,j)f(i,j)表示i,ji,ji,j对排列的逆序数产生的贡献，则逆序数X=∑i,jf(i,j)X=\sum_{i,j}f(i,j)X=∑i,jf(i,j)E(X)=E(∑i,jf(i,j))=∑i,jE(f(i,j))=∑i,j12=n(n−1)4\begin{aligned}E(X)&=E(\sum_{i,j}f(i,j))\\&=\sum_{i,j}E(f(i,j))\\&
2020-11-02 21:37:43
1789
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人