小衣同学的博客

这样对于不包含这个(i,j)对的区间[l,r]（1<=l<=i，i<=r<j）来说，(i,j)对都是有贡献的，这样的区间数是i*(j-i)k>1时，需要选长度为k的序列l[]、r[]，满足l[j]∈[1,i]，l[j]<=l[j+1]，r[1]<j，r[j]<=r[j+1]r序列，由于有r[1]<j的限制，可以用在[i,n]里任取减去在[j,n]里任取，方案数是。k=1时，需要选长度为1的序列l[]、r[]，满足l[1]∈[1,i]，r[1]<j。代入k=1，其实发现也成立。记第一次选的右端点x，

那么这种集合的数量恰好等于 f_(y/x)，也就是把 f_m 减去所有 d(m/i)*f(i) 应该就行了。每个质因子有两个集合，1e18最多有15个不同质因子，最多有30个集合，暴力枚举是O(2^30)的。然后考虑容斥掉，就是这里面会出现 gcd=x, lcm=y 的集合，且 (x,y)!对于每个质因子p，我们要用全集，减掉gcd是pi的倍数的集合，也要减掉lcm不是pi^ai的集合。求非空集合的数量，满足gcd=1，lcm=m(m<=1e18)，答案取模998244353。

比如需要减去的是gcd=2，lcm=y的方案，就等价于减去gcd=1,lcm=y/2的方案。dp[i][S]表示约数里当前选了i个数，当前所有质因子的状态有没有覆盖住最高幂次，由于lcm+gcd=x，有lcm/gcd+1=x/gcd，还有lcm/gcd>=1。显然如果gcd>1，让gcd和lcm同除以gcd即可，所以可以认为gcd=1，但是，这个只能限制住lcm的限制，不能限制住gcd=1，所以容斥。用gcd=1的，减去gcd>1的，枚举大于1的具体是几，枚举gcd，gcd一定是x的因子，

一棵树，考虑加边的过程，加一条边减少一个连通块。那么，逆向这个过程，没删一条边，就多一个连通块。连通块贡献=点的贡献-边的贡献，然后分开统计。森林：点的个数=边的个数+连通块个数。树：点的个数=边的个数+1。

一条数轴，0和l+1两点有墙，[1,l]这l个点需要放2n头奶牛，其中n头属于FJ，n头属于FN。那么，有0<𝑎1<𝑏1<𝑎2<𝑏2<…<𝑎𝑛<𝑏𝑛<𝑙+1成立。每个间隔都是奇数，每个空隙都是>0的数，相加之和为n+1的方案数。如果 𝑎1,𝑎2,...,𝑎𝑛 代表一个农场主的奶牛的位置，而 𝑏1,𝑏2,...,𝑏𝑛 代表另一个农场主的奶牛的位置，每次一个人选一个数字k(1<=k<=n)，并选择k头奶牛，FJ先手，给定l(l<=1e6)和n(n<=l/2)，然后将问题转化成，n个间隔，此外还有n+1个空隙，

求(i,j)(1<=i<=j<=n)对的数量，满足gcd(i,j)≠1且gcd(pi,pj)≠1。新函数需要满足n=1的时候对因子求和为0，大于1的时候对因子求和为1，枚举i和i的倍数j，所有倍数j需要反演得到i固定时的答案，取到了一个数和一个空位的时候，就认为是取了两次相同的数。那么0减掉mu[1]之后是-1，取反之后即为1，给定长为n(n<=2e5)的1-n的排列p，由于gcd不能为1，要忽略mu[1]的贡献，一共有x个数时，任意取两个，可以重复取，之前n>=2的时候，因子mu之和为0，

m(m<=3e5)次修改，每次选一个位置x(1<=x<=n-1)，将这个位置原来的字母改成?[1,i]总共有i+1个空，其中最大值、最小值各对应一个空，方案唯一空，而?从第二个字母开始，比如到第i个字母，需要决定第i+1个值的大小关系时，，表示a[i+1]既不是[1,i+1]最大值也不是最小值。询问时，先判断第一个字母是不是最大最小值的一个，不是输出0，①为<，表示a[i+1]是[1,i+1]的最大值。②为<，表示a[i+1]是[1,i+1]的最小值。第i(1<=i<=n-1)个字母，

剩下n-i个随便选（可能冲突），乘以n-i的阶乘，转化成至少冲突i次的方案数。1. 如果选了（1，n），对应长为n-2的链上选k-1对匹配的方案，在新环上：则认为是在长度为2*n的环上，选择一对相邻的点两两匹配，剩下的随便选，转化成至少冲突k次的方案数，利用二项式反演解决。2. 如果没选（1，n），对应长为n的链选k对匹配的方案，暴力合并背包，得到恰好选了i个冲突的点的方案数，由于原来长为n的环变为新的长为2n的环，考虑容斥，算恰好冲突的k次的方案数，对于环来说，一个长为n的环，

1. 如果第一个点是空，那么第n个点是球，长为n-2的链上选k-1对匹配的方案，k个空位对应n-k个字母，终态局面定下来之后，乘上俩人填n-k个字母的顺序，Alice和Bob在一个圆格上玩游戏，格子共有1，...，n个，格子i(i<n)与i+1相邻，n与1相邻，每个格子初始都是空的，特别地，填的时候，相邻的格子不能有相同的字母，否则无法填。所以，不妨认为是n个点的环上，选k对「左球右空」的方案。2. 如果第一个点不是空，长为n的链选k对匹配的方案，Alice先手，每次可以选一个空的格子，填A或者B，

只需全局减1，即可删掉m+1个1，并且使得第m+2个数的值>=1，也就对应了f[i-(m+1)][j-i]②要么令所有数都+1，使得所有数都大于等于2，转移到2 2 3，f[i][j]从f[i][j-i]转移。①每次要么新增一个1，转移到1 1 1 2，f[i][j]从f[i-1][j-1]转移。原序列2 2 3，差分序列2 0 1，反转差分序列1 0 2，原序列2 2 3，差分序列2 0 1，反转差分序列1 0 2，令B[1]=A[1]，B[i]=A[i]-A[i-1]，

假设最后一段x个数，说明冲突了x-1次，容斥系数是(-1)的x-1次方，加上对应的贡献即可。前0个数分成偶数段方案数为1，分成奇数段方案数为0，对应dp[0][0]=1。2. 注意到，第二维对容斥系数的贡献，只有第二维的奇偶性，所以可以改写为。构造一个序列b，要求bi∈[1,ai]，且b[i]不等于b[i+1]其中，dp[i]表示以i结尾的方案数，枚举最后一段合并了几个数，那么，ai对前面的位置的数，也就是k

如图所示，其中，w1=i-las，h1=las-a[las]，h2=i-las，w2=i-a[las]可以从0枚举到a[i]-a[las]枚举这个k，因为邻相差之和最终等于n，所以复杂度是O(n)的。3. 除去-1的部分，其他值需要满足非严格单调递增，即a[las]>a[i]的情况是非法的。可以发现多了一个L形状的区域可以选点，这部分需要选v=a[i]-a[las]个点，那么，

第一个数字选0，后面每个数都有2k+1种选择方式，最后把最小值往上平移到[0,x+k-1]之间。t(t<=50)组样例，每次给定n(1<=n<=1e9),x(1<=x<=40),由于长度为1时对应的[0,x-1]的向量均为1，所以将每一行的和从答案中减掉即可。注意到x<=40，所以可以dp[i][j]表示长为i的数组最后一个是j的方案数。转移时，只要abs(j1-j2)<=k，就可以从j1转移到j2，即长为n的数列，使用的值均在[0,x-1]的方案数，的字眼，首先想到容斥，用总的减不满足的，

1. 第i-1行没取的话，第i行会新增一列，dp[i-1][j-1]转移到dp[i][j]等到第n行决策完取不取后，第n+1行都会新增一列，所以dp[n+1][n-k+1]即为所求。取完之后，第i行还是会新增一列，dp[i-1][j]*j转移到dp[i][j]有dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j。dp[i][j]表示只考虑前i行还有j个空列的方案数，2. 第i-1行取了的话，从j列里挑一列取，j种方案，例如，n=3，m=2时，合法方案有7种，如下图。

t(t

其中dp[i][0]表示两端都位于子树内部的路径，dp[i][1]表示有一端位于根节点的路径。对于每个点i，记其值为a[i]，a[i]可以取[1,m](1

给定一个长度为n(nc,b->b这个性质，然后再着手计数。不难发现，自环的情况和>=2的环的情况是统一的，所以dfs找环即可。组合题更多的是一种无从下手的感觉，需要多培养手玩性质的能力。感觉已经说的很详尽了，甚至没什么需要补充的地方...操作：你可以将当前i位置的数和a[i]位置的数交换。

p,q)之间都是小于10的值，排序的时候可以归给第一段，使得10仍为第一段区间排序后的右端点。每次操作，你可以选择两个下标[l,r]，将区间[l,r]排增序，代价是r-l秒。这种取数方式，保证了第一段区间不存在大于10的值，第二段区间不存在小于10的值。右端点r：[>10的第一个数的位置q,<10的第一个数的位置R)，p<q<R。即，如果区间是[1,n]，最左端开区间对应0，最右端开区间对应n+1。统计其减小1的贡献时，对应的区间数有多少，即为这个值对应的贡献数。使得一个区间，能被分割成两个子区间考虑。

题目链接：https://ac.nowcoder.com/acm/contest/1108/H来源：牛客网Bobo 精通数据结构！他想维护一个线段的集合 S。初始时，S 为空。他会依次进行 q 次操作，操作有 2 种。* 类型 1：给出 l, r，向集合 S 中插入线段 [l, r].* 类型 2：给出 l, r，询问满足 [x,y]∈S[x, y] 且 x≤l≤r≤y 的线段 [x,...

Codeforces Round #838 (Div. 2) E. Tree Sum(组合数学 prufer序列)

Codeforces Round #836 (Div. 2) E.Tick, Tock(在线:带权并查集/离线:dfs判环+计数)

AtCoder Beginner Contest 279 G. At Most 2 Colors(计数/组合数学/dp递推)

IOI2022 D2T1 数字电路（计数&概率/组合数学+线段树区间翻转）

AtCoder Beginner Contest 276 G.Count Sequences(计数/组合数学)

Educational Codeforces Round 137 (Rated for Div. 2) F. Intersection and Union（动态dp(线段树+矩阵+dp) /组合数学）

Codeforces Round #823 (Div. 2) E.Maximums and Minimums(单调栈+计数)

题目在三维空间内，你当前处于(0,0,0)，需要走到(x,y,z)(-1e7<=x,y,z<=1e7)每一步，你可以先选择三维中的某一维，然后令这一维+1或-1，其他两维保持不变，换言之，每一步只能从当前整点移动到三维空间内相邻的整点，求恰好n(n<=1e7)步走到(x,y,z)的方案数，答案对998244353取模思路来源dls的B站讲解题解首先，题目n=1e7，刻意卡了NTT，因为998244353=2^23*7*17，即最大支持的NTT长度为2^2

题目n(n<=1e5)个点的一棵树，每个点有点权ai(1<=ai<=1e5)，对于树上两个点s、t，定义C(s,t)=k×gcd(Ap1​​,Ap2​​,…,Apk​​)，其中，k为s到t这条链的顶点个数，p1为点s，pk为点t，中间的点是链上经过的点求，答案对998244353取模思路来源dls/官方题解题解1（反演）根据反演，考虑将gcd的贡献拆开，然后统计每一部分贡献的倍数有哪些，根据式子，将gcd(a1,...,an)的贡献展开，即对于每个.

题目这个题意还是看题面比较好司机个数未知，每个司机初始赢0局，输0局，两个当前赢的局数和输的局数相同的司机，会在一起比赛一局，比完之后，其中一个司机赢的局数+1，另一个司机输的局数+1，司机当他总共赢了n场，或总共输了m场之后就不再继续比赛，你想邀请最少的司机数，使得每个人都能要么总共赢n场，要么总共输m场，其中，赢了0场、输了m场的司机将会被授予Leadfoot badges，k(k<=1e5)组样例，每次给出n,m(1<=n,m<=1e5)，

题目bzoj3294在一个m(m<=30)行n(n<=30)列的棋盘里，放c(c<=10)种彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。求合法的方案数，答案对1e9+9取模。例如，n=m=3，有两个白棋子和一个灰棋子，下面左边两种方法都是合法的，但右边两种都是非法的。思路来源hx073269代码题解把棋盘考虑成一个二分图，对于每种颜色单独处理，考虑为第i种颜色分j行k列，则需要n行里选j行，m列里选k列，

题目在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法，中国象棋中炮的行走方式大家应该很清楚吧。一个炮要能攻击另一个炮，他们必须要处于同一行或者一列且他们之间有且仅有一个棋子。思路来源蔡老师题解不存在三个炮位于同一行或者同一列，即每一行最多有两个炮，每一列最多有两个炮。于是可以考虑把棋盘考虑成一个二分图，左侧的点代表行，右侧的点代表列， 每个点的度数<=2dfs(i,j,k)表示还需要考虑右边的[1,i]列时，左边还有

题目t(t<=10)组样例，每次给出一个n,k(2<=k<=n<=1e5)表示1,2,...,n位置上每个位置放置了一盏熄灭的灯，你等概率地选择一盏熄灭的灯并点亮，并等概率地从熄灭地灯里选一盏且点亮，特别地，如果此刻存在两盏灯的距离小于等于k，则游戏终止求游戏终止时，操作的灯的数量的期望思路来源https://blog.csdn.net/Tan_tan_tann/article/details/117430238https://blog.csdn.ne

题目有c1个a，c2个b，...，c26个z。你需要用这些字母构造出一个长度为n的字符串，使得不存在长度>=3的奇回文子串。输出答案对998244353取模的值。保证对于输入的所有ci来说，ci>n/3都成立。思路来源uoj群题解奇回文子串的限制，等价于s[i]!=s[i-2]。如果没有ci的限制，就变成了一个计数问题，前两个字母26种选法，后面的只要保证和s[i-2]不同，25种选法。于是，ci>n/3成为了突破口，鸽巢原理表明，最多只有两种字母会

A.Association for Cool Machineries (Part 1)https://vjudge.net/problem/Kattis-cool1

题目1000*1000的cell图，某些cell里有蛇，一共n(n<=2e3)条蛇，第i条的坐标(xi,yi)，其危险值为bi，你需要选中其中m(m<=n)条蛇，距离选中的蛇的距离在的蛇会一并被选中，最终这个选法对答案的贡献是，所有被选中的蛇的bi值之和的平方，求所有不同选法的贡献值之和，答案模1e9+7思路来源jiangly代码题解算贡献的一道题，是平方项加乘积二倍，考虑将合式打开，考虑的出现次数，选法同时包含了ij，这个并集很难取，难以确定ij

题目每次给定一个n，表示在包含{1,2,...,n}的集合S中，每次删除当前集合中最小的元素，再随机删掉1个元素，直到|S|=1，求每个元素最后被留下来的概率，答案对998244353取模。T(T<=40)组样例，保证思路来源官方题解题解的的的代码#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=5e6+10,mod=9982443

题目为了知道自己的排名，小C使用了系统中的“好友伴学”功能。每次，系统会在除了小C之外的所有考生中随机抽取一名，然后返回Ta的排名比小C高还是低。这次考试有n(2<=n<=1e11)个人参加，可以认为小C的排名是一个在[1,n]内等概率随机的整数。小C总共使用的m(0<=m<=5e3)次“好友伴学”功能，却没有一次抽中排名比自己高的人。请问小C在这次考试中的期望排名是多少，若答案为，输出思路来源题解https://ac.nowcoder.com/d

题目给出标号为1到N的点，以及某些点最终的度数，允许在任意两点间连线，可产生多少棵度数满足要求的树输入：第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1输出：一个整数,表示不同的满足要求的树的个数,无解输出0思路来源https://m-sea-blog.com/archives/1661/题解prufer序列，常用来解决，和度数有关的树计数问题大数，懒得粘板子，py一发入魂代码n = in

题目共有4种硬币，面值分别为c1​,c2​,c3​,c4​。某人去商店买东西，去了n 次。对于每次购买，他带了 di​枚i种硬币，想购买s的价值的东西。请问每次有多少种付款方法。思路来源题解代码#include<bits/stdc++.h>using namespace std;const int N=1e5+10;...

题目T(T<=5e5)组样例，每组给定两个数n,m(1<=n,m<=1e6)求有多少种1到n的排列a，满足序列恰好有 m个位置i，使得 ai​=i。答案对 1e9+7 取模。思路来源https://www.bilibili.com/video/BV1Pz41187Px题解C(n,m)取出恰好对应的位置，剩下n-m个就对应错位排列的方案...