$noi.ac$上好题选做
#489 shuffle NOI模拟赛第一场T2
题面描述：对于一个长度为$m$的序列$a_1,a_2,…,a_m$，小Q可以将这个序列随意打乱成序列$b_1,b_2,…,b_m$，使得$a_i=b_i(1≤i≤m)$的位置数量尽可能少。
给定一个长度为$n$的序列$s_1,s_2,…,s_n$，它有$2^n-1$个非空子序列。请对于每个$k=0,1,2,…,n$统计$s$有多少非空子序列$a$经过重排成$b$后，$a_i=b_i$的位置数量的最小可能值恰好为$k$。
答案对$10^9+7$取模，$n\leq250000$
$solution$:我们只需统计出所有$k>0$的答案，用$2^n-1$减去所有$k>0$的答案即为$k=0$的答案。
我们把一个子序列重排后$a_i=b_i$的最小可能值称为子序列的价值，根据$Hull’s\ Theorem$，设一个长度为$m$的子序列中出现次数最多的数字出现了$p$次，则子序列的价值为$max(0,2p-m)$
设一个子序列中出现次数最多的数字称为这个子序列的主数字（主数字若有多个，则根据上面分析这个子序列的价值为$0$，无需考虑）。设数字$u$在数列中出现了$N_u$次，则所有主数字为$u$的子序列的贡献可以用多项式表示：
$p_u(x)=\sum_{i=0}^{N_u}C_{N_u}^ix^i=(1+x)^{N_u}$
$q_u(x)=\sum_{i=0}^{n-N_u}C_{n-N_u}^ix^{-i}=\sum_{i=0}^{n-N_u}C_{n-N_u}^{n-N_u-i}x^{n-N_u-i}/x^{n-N_u}=(1+x)^{n-N_u}/x^{n-N_u}$
$G_u(x)=p_u(x)q_u(x)x^{N_u}=(1+x)^nx^{N_u}$的第$n+i$项系数就是这类主序列对$k=i$的答案的贡献。
所有子序列对$k>0$的每一项$k$答案的贡献为
$\sum G_u(x)=(1+x)^n(\sum_ux^{N_u})$的$n+k$次项系数
使用多项式乘法即可，由于$10^9+7$不是$NTT$模数，因此需使用$MTT$，新板子$get$
1 |
|
#170 数数 NOI模拟赛第四场T1
求有多少对$1-n$的排列$(a,b)$满足$\sum_{i=1}^nmax{a_i,b_i}>m$
$n\leq 50$
考虑两个$1-n$的递增数列$a,b,a_i=b_i=i$,用$a,b$元素的互相一一配对表示排列对，最终结果乘$n!$即可
我们考虑从前往后加入那些配对，我们规定某个配对一定是扫到标号较大的那个元素时将这个配对加入（因为一个配对的价值取决于标号较大的元素）
当我们扫到$i$时，$a[1:i]$中还未配对的元素个数肯定与$b[1:i]$中还未配对的元素个数是相等的(证明显然）设$dp[i][j][k]$表示扫到$i$，前$i$个中$a,b$还各有$j$个未配对，当前所加入的配对价值和未$k$。转移显然，复杂度$O(n^4)$
1 |
|
#442 牛羊被他抢了 NOI模拟赛第六场T2
一棵$n$个点的树，每个点有$0/1/2$权值，有多少个联通块使得这其中$0,1,2$三类点分别不超过$a,b,c$个
$n\leq 200,a+b+c\leq n/2$
第二个代价根据均值不等式等价于$abc\leq (n/6)^3$
这是个好题，考察了$dfs$序的树形完全依赖背包。
如果我们直接背包，复杂度为$O(n(abc)^2)$，不可接受
我们考虑另辟蹊径，只对包含根的联通块计数，这可以使用基于$dfs$序的树形完全依赖背包，选了某个点必须选它的所有祖先，这样，每次只加入一个点，在$dfs$回溯时涉及背包合并，一次背包的复杂度是$O(nabc)$
套个点分治即可对所有联通块计数，复杂度$O(nabclogn)$
本题我尝试了封装式的代码，可能可以当半个板子
1 | //点分治+dfs序树形依赖背包 |
#443 老头子的话 NOI模拟赛第六场T3
$n$个小屁孩，每次随机给某个小孩一个糖，期望几次所有小孩都有至少$k$个糖
$n\leq50,k\leq1000$
来一波套上期望线性性的$min-max$容斥
设$p_x=E(min(T))，|T|=x$,这是因为所有大小相等的集合都是等价的
$E(max(S))=\sum_{i=1}^n(-1)^{i-1}C_n^ip_i$
设只在$x$个小孩中随机发糖，一旦有一个小孩拿到$k$个糖就停止，期望发糖$q_x$次，则$p_x=\frac{nq_x}{x}$
我们考虑求所有的$q_x$
首先钦定一个小孩拿了$k$个糖，且最后一步拿了第$k$颗，其他$k-1$颗可在步骤中随意分配，其他的$x-1$个小孩拿了少于$k$颗糖，设$q_{xy}$表示$x$个小孩发$y$次糖的概率，
首先钦定一个小孩拿了$k$个糖，且最后一步拿了第$k$颗，其他$k-1$颗可在步骤中随意分配，其他的$x-1$个小孩拿了少于$k$颗糖，设$q_{x,y}$表示$x$个小孩发$y$次糖的概率，一共$n$个小孩，背包容量$nk$，每种小孩的糖有$n$种可能，复杂度$O(n^2k^2)$，无法通过。
背包使用$NTT$优化，设$f_x$为$q_{xy}$的指数型生成函数，$A=\sum_{i=0}^{k-1}\frac{x^i}{i!}$，那么$f_{x+1}=Af_x$
需要做$n$次长度递增的$NTT$，复杂度$O(n^2klog(nk))$
注意：当需要多次$NTT$时，一定要记得清空数组，而且要清空到$2(n+m)$项
1 |
|