传送门 考虑一下最长公共子序列的求法： dp[i][j]=max⁡{dp[i−1][j−1](a[i]==b[j])dp[i][j−1]dp[i−1][j] dp[i][j]=\max\left\{ \begin{aligned} &dp[i-1][j-1](a[i]==b[j])\\&dp[i][j-1]\\&dp[i-1][j] \end{aligned} \ri...

考虑到一个合法的sss，长度为nnn，那么题目给的字符串（设为aaa，长度为mmm）肯定可以这么表示： s[1→n]+s[1→n]+s[1→n]...+s[1→n]+s[1→i]s[1 \to n] + s[1 \to n] + s[1 \to n] ... +s[1 \to n]+s[1 \to i]s[1→n]+s[1→n]+s[1→n]...+s[1→n]+s[1→i] 1≤i≤n1 ...

考虑到每行每列只有一个棋子，我们可以把整个棋盘映射到一个数组上面，如下： 显然这个数组里面的各个数字都不同。 考虑[l,r][l,r][l,r]区间映射到棋盘上面，满足k×kk \times kk×k且恰好包含kkk枚棋子的充要条件。 就是[l,r][l,r][l,r]中的数字形成了一个长度为r−l+1r-l+1r−l+1的值域连续段，比如4,2,34,2,34,2,3形成了一个长度为33...

水！ 离散化之后树状数组随便乱搞就行了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <bits/stdc++.h>#define MAXN 1000005using namespace std...

巧妙啊！ 不妨考虑枚举答案，我们不要从小到大枚举，而是从位数之和从小到大枚举。 考虑一个数xxx，x+1x+1x+1为xxx的数位之和+1+1+1，x×10x \times 10x×10数位和不变。 于是我们可以在 mod k\bmod kmodk的意义下计算xxx，将x,x+1x,x+1x,x+1连一条长度为111的边，将x,x×10x,x\times 10x,x×10连一条长度为000的...

考虑g1=gcd(al,al+1,...,ar),g2=gcd(al,al+1,...,ar,ar+1)g_1=gcd(a_l,a_{l+1},...,a_{r}),g_2=gcd(a_l,a_{l+1},...,a_r,a_{r+1})g1​=gcd(al​,al+1​,...,ar​),g2​=gcd(al​,al+1​,...,ar​,ar+1​) 显然有g1g_1g1​为g2g_2g...

传送门 首先，遇到等差数列这种形式，最先要想到移项。 A[k]−A[j]=A[j]−A[i]→A[k]+A[i]=2×A[j]A[k]-A[j]=A[j]-A[i] \to A[k]+A[i]=2 \times A[j]A[k]−A[j]=A[j]−A[i]→A[k]+A[i]=2×A[j] 于是很容易想到固定jjj，而在jjj两边枚举i,ki,ki,k。 注意到如果固定jjj，2×A[j]...

此题恶臭，心态被搞了。 考虑SolveSolveSolve算法，每个点有且仅有一次被当做树的根，于是可以将整个算法的期望时间复杂度变成每个点的树的期望大小之和。 想到这里，你还得有一个更加恶臭的想法，考虑如何表示每个点的树的期望大小，记p[i][j]p[i][j]p[i][j]为jjj在iii子树里面的概率。 那么iii子树的期望大小即是∑j!=ip[i][j]\sum _{j!=i} p[...

传送门 很好的一道生成函数+NTT题，做完之后可以加深对生成函数的理解。 建议先弄懂卡特兰数是怎么用生成函数推的，参考这篇博客（只用看推到C(x)=\frac{1\pm\sqrt{\dfrac}{2}的部分） 考虑我们是怎么推导出nnn节点二叉树的种类数为卡特兰数的，考虑根节点两边连出的子树，他们的方案数为cn−i−1×cic_{n-i-1} \times c_{i}cn−i−1​×ci​。...

传送门 容易想到的是，枚举讨论蔡徐坤的组数，设至少有kkk组讨论蔡徐坤的人方案数是f(k)f(k)f(k)，容斥一下，答案就是∑i=0n/4f(k)×(−1)k\sum _{i=0}^{n/4} f(k) \times (-1)^k∑i=0n/4​f(k)×(−1)k。 现在的主要问题是求出f(k)f(k)f(k)，将讨论蔡徐坤的四个人缩成一个组，所以这样的组数是kkk组，剩下的人数lef...