9月做题记录

9月做题记录
最后一个9月份了,年份都不用写了

loj6338「SDWC2018 Day2」优秀、CF301E Yaroslav and Arrangements

请先思考后再展开

先题目转化:

  1. 首先值可以平移到从1开始,然后乘上(m-mx+1)即可
  2. 拆环,在n+1处放个1

k很小可以放状态里面,明显计数dp
考虑从小到大插入数字,一开始一坨1,每两个1中间需要插2,每两个2又要插3
$f(mx,now,pp,cnt)$表示长度now,pp个空位,生成cnt个良好数列
转移枚举插入T个数,$f(mx+1,now+T,T-pp,cnt*C_{T-1}^{pp-1})+=f(mx,now,pp,cnt)$

code

CF947E Perpetual Subtraction

请先思考后再展开

生成函数做法:
$$
考虑f(生成函数为F)转移到ff(生成函数为FF),通过化式子使其支持快速重复\\
FF=\sum_{i=0}^n(\sum_{j=i}^nf_j/(j+1))x^i=\sum_{j=0}^n \frac{f_j}{j+1}*\frac{x^{j+1}-1}{x-1}=\frac{\int_1^x F(t)dt}{x-1}\\
考虑设G(x)=F(x+1),GG(x)=\frac{\int_0^xG(t)dt}{x},gg_i=\frac{g_i}{i+1},每次操作可快速转移 \\
那么只需要考虑开始和最后同阶f和g怎么转化,\sum_{i=0}^n g_ix^i=\sum_{i=0}^nf_i(x+1)^i
$$
二项式展开+二项式反演+ntt,卷积方式和第一类斯特林log卷的方法类似,就翻转一下就好了,code
可见本做法的核心在于巧妙地构造G,得到一个很好用的转移式;这个做法并不是很好想,然而另一种做法更鬼畜……

线性代数做法:

其实有了线性代数基础知识,并不难看懂Vectorxj题解官方题解scb的题解

然而这个特征值好推,特征向量不好推啊,似乎scb有有理有据的中文推导,然而并没有太大耐心去看了

51nod1229 序列求和 V2

题意:求$f_k(n)=\sum_{i=1}^n i^kR^i$

请先思考后再展开

$$
(R-1)f_k(n)
=n^kR^{n+1}+\sum_{i=1}^n R^i((i-1)^k-i^k)二项式定理\\
=n^kR^{n+1}+\sum_{i=1}^n R^i(\sum_{j=0}^{k-1} C_k^j i^j(-1)^{k-j} )
=n^kR^{n+1}+\sum_{j=0}^{k-1} (-1)^{k-j}C_k^j \sum_{i=1}^{n} i^j R^i\\
=n^kR^{n+1}+\sum_{j=0}^{k-1} (-1)^{k-j}C_k^j f_j(n),可以O(k^2)递推
$$
记得R=1要特判,自然数幂和

51nod1822 序列求和 V5

请先思考后再展开

uoj193【UR#14】人类补完计划

题意:给出一个n个点m条边的无向图,求所有基于边集的生成子图是一棵连通基环树的方案权值和,一个方案的权值为$2^{非叶子节点个数}$

请先思考后再展开

这题和CEOI2019游乐园有点像,一定要分清哪些东西你需要考虑进容斥系数的选择而哪些不用

Rose的做法:
$$
首先考虑环,不妨从编号最小的点开始,这样每个环会记两次,设link(S,ed)然后转移到比mi(S)大的点,O(2^nn^2)\\
f(S)表示以S为点集的连通基环树方案数,用link(S)/2初始化,然后下面T的条件都是T\ne \emptyset,T\subset S\\
设cnt(T\to S \setminus T)表示可选择的边,可以用类似游乐园的方法O(1)处理切换 \\
f(S)=\sum_T (-1)^{|T|+1}f(S \setminus T)*cnt(T\to S \setminus T),ans=\sum_S \sum_T pp(T) 2^{|S|-|T|} f(S \setminus T)*cnt(T\to S \setminus T) \\
我们希望2^{n-i}=\sum_{j=1}^{i-1} C_i^j pp(j)*2^{n-j},即(1/2)^i=\sum_{j=1}^{i-1}C_i^jpp(j)*(1/2)^j
$$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8884.html
转载请注明出处,谢谢!