Aeon
显然字典序最大就是把最小的字母放在最后
Business
[动态规划]
简单dp
dp[i][j]dp[i][j]dp[i][j]表示到第iii天，当前有jjj块钱，最后返还的钱最多为多少
完全背包转移
Celebration
Description
有一个环
，求把它分成三段，使得每一段内无重复元素，且三段长度可以作为某个三角形的三边的方案数。
一个拆分方案可以看作一个三元组 (a,b,c)(a,b,c)(a,b,c)，其中 0<a<b<c≤n0lt alt b lt c le n0<a<b<c≤n，表示在第 a,b,ca,b,ca,b,c个位置之前断开。两个拆分不同当且仅当其对应的三元组不同。
n≤2×106nle 2times10^6n≤2×106
Solution
[计数] [树状数组]
定义长度不超过 n−12frac{n-1}{2}2n−1 ，且不含重复颜色的段为合法的段。记 prexpre_xprex 为以
为右端点的合法段最远的左端点，nxtxnxt_xnxtx 为以 xxx 为左端点的合法段最远的右端点。
先枚举题目中的aaa，那么b∈(a,nxta+1]bin(a, nxt_a + 1]b∈(a,nxta+1]。在确定了a,ba, ba,b的位置后，合法的ccc位于(b,nxtb+1](b, nxt_b + 1](b,nxtb+1]和[prea,n][pre_a, n][prea,n]的交集中
可以用树状数组维护：
从左往右枚举aaa，把合法的bbb对应的(b,nxtb+1](b, nxt_b + 1](b,nxtb+1]这段区间在树状数组中+1；查询就直接查[prea,n][pre_a, n][prea,n]的区间和；在离开aaa的时候把(a,nxta+1](a, nxt_a + 1](a,nxta+1]区间-1
Disaster
[kruskal重构树]
kruskal重构树模板题
Effort
Description
有 mmm种数据结构(可把数据结构想像成游戏中的种族)，第 iii种有 aia_iai个，每个可给敌人造成至少 111 次，至多 bib_ibi次伤害。有n nn名敌人，每人承担至少一次伤害。求总情况数模 998244353998244353998244353的值
数据结构两两不同 (同种的任两个也不同)，敌人两两不同。
两种方案不同当且仅当某个数据结构造成的伤害不同，或某个敌人受到的伤害不同。
n×m≤105,ai≤105,bi <998244353n times mle 10^5, a_ile 10^5, b_i < 998244353n×m≤105,ai≤105,bi <998244353
Solution
[组合数学] [生成函数] [多项式] [NTT]
注意到每个敌人的伤害是无序的，即这个敌人在被第几次攻击到都是一样的，而其他限制都是有序的
于是可以钦定攻击顺序和受到伤害的顺序。形象地理解就是先把所有数据结构按顺序摆一排，确定每个数据结构攻击多少次，这样就确定出一个攻击序列。再在这个攻击序列上插n−1n-1n−1个板就是这个攻击序列方案数
看上去这是由两个部分构成的（先确定攻击序列，再插板），但实际上可以同时算
设Fi(x)F_i(x)Fi(x)表示一个第iii种数据结构插板方案的生成函数，它的kkk次项系数表示插kkk个板的方案数。那么[xk]Fiai(x)displaystyle [x^k]F_i^{a_i}(x)[xk]Fiai(x)就是在第iii种里插kkk个板的方案数了
考虑如何求Fi(x)F_i(x)Fi(x)
第kkk项系数其实就是
(1k)+(2k)+⋯+(bik)
binom{1}{k} + binom{2}{k} + cdots + binom{b_i}{k}
(k1)+(k2)+⋯+(kbi)
发现除了k=0k=0k=0之外，都是是杨辉三角一列的之和，就等于(bi+1k+1)binom{b_i + 1}{k + 1}(k+1bi+1)
因为bib_ibi很大，不能直接算，但是kkk比较小，所以可以先O(1)O(1)O(1)计算出k=1k=1k=1时的值，然后O(1)O(1)O(1)递推下一个kkk的值
由于只有n−1n-1n−1个板，所以多项式长度始终不超过n−1n-1n−1。直接做多项式快速幂即可，再把mmm个多项式依次合起来
Farewell
Description
有一张 nnn个点 mmm条边的图，第 iii条边 ui,viu_i,v_iui,vi有 13frac{1}{3}31的概率从ui u_iui指向 viv_ivi ，另 13frac{1}{3}31 的概率从 viv_ivi 指向 uiu_iui ，剩下 13frac{1}{3}31的概率被删除。求这张图是有向无环图的概率
n≤20nle 20n≤20
Solution
[FWT] [子集卷积] [动态规划] [状态压缩]
设FSF_SFS表示SSS是DAG的方案数，ESE_SES表示点集SSS内部的边数，ES,TE_{S, T}ES,T表示SSS与TTT之间的边数
DAG计数显然枚举入度为000的点容斥
FS=∑T⊆S,T≠∅(−1)∣T∣+1FS−T×2ET,S−T
F_S = sum_{Tsubseteq S, Tne emptyset} (-1)^{|T| + 1}F_{S - T}times 2^{E_{T, S - T}}
FS=T⊆S,T≠∅∑(−1)∣T∣+1FS−T×2ET,S−T
2ET,S−T 2^{E_{T, S - T}}2ET,S−T是因为从S−TS-T S−T到T TT的边只能断掉或指向TTT
又因为2ET,S−T=2ES−ET−ES−T 2^{E_{T, S - T}} = 2^{E_S - E_T - E_{S - T}}2ET,S−T=2ES−ET−ES−T，所以式子可以化为
FS2ES=∑T⊆S,T≠∅(−1)∣T∣+12ET×FS−T2ES−T
frac{F_S}{2^{E_S}} = sum_{Tsubseteq S, Tne emptyset} frac{(-1)^{|T| + 1}}{2^{E_{T}}} times frac{F_{S - T}}{2^{E_{S - T}}}
2ESFS=T⊆S,T≠∅∑2ET(−1)∣T∣+1×2ES−TFS−T
子集卷积即可