Source
いろはちゃんコンテスト Day4
iroha2019day4
好题:E、H、K
iroha2019day4 E 芽生え
(原题为下面题意的补)
题意1:n个变量,其中$x_i \in [0,k_i]$,求异或和=0的方案数,$n \le 1e6,k_i \le 1e18$
题意2:n个变量,其中$x_i \in [0,k]$,求异或和=0的方案数,$n,k \le 1e18$
对于题意2,比较直接的$O(nlogk)$做法,已经能通过本题:
考虑最高位$2^w$,考虑有i个数没有顶上界,除了其中一个其他任意选而这个负责适应其他人;如果全部没有顶就递归到下一位
$\sum_{i=1}^n [(n-i)\%2=0]C_n^i(2^w)^{i-1}(k-2^w+1)^{n-i}$,
1 | ll solve(int n,ll k,int w) |
这个是可以用类似单位根反演(d=2下也可以不看作是单位根反演)优化的
对于题意1,就是若干个生成函数卷起来(仅那些$k_i \ge 2^w$,其他放外面搞):
$f(x)=\frac{1}{2^w} (\prod(2^w+(k_i-2^w+1)x)-\prod(k_i-2^w+1)),ans=\frac{f(1)+f(-1)}{2},O(nlogk)$
回到题意2:
$$
f(x)
=\sum_{i=1}^n C_n^i(2^w)^{i-1}(k-2^w+1)^{n-i} x^{n-i}
=\frac{1}{2^w}*((2^w+x(k-2^w+1))^n-(k-2^w+1)^nx^n)
\\
ans=\frac{f(1)+f(-1)}{2},O(logn*logk)
$$
iroha2019day4 H 永遠に
题意:构造一个n*n的方阵,使得每行、每列都不存在子序列是个长度>2的等差数列
如果会一维,二维直接搞个二元组$(i,j)=(i-1)n+j$,然后例如第i行就是$(p_i,p_1)..(p_i,p_n)$
一维的话,可以「奇数」+「偶数」,递归构造,code
iroha2019day4 K 世界線
题意:给出一个排列求多少种方案能搞出这个排列;初始一个n,每次选一个没插的数插入,要求插的位置左边比自己大;两个方案不同当且仅当某次插入的数或插入位置不同
结论:给定一棵树结构,每个点标号,要求每个点的编号比子树其他点小,合法方案个数=$\frac{n!}{\prod siz_i}$
不难发现总是有解的,例如倒序插入;考虑这个排列带来哪些限制
对于$p_i$,找到左边第一个更大的数$p_j$,则$p_{j+1..i-1}$需要在$p_i$前插入
注意到「左边第一个更大数」(可以用单调栈或链表求)显然形成一棵树,然后我们令每个节点的孩子按照在排列中位置排序,那么每个点的孩子显然是递增的
所谓$p_{j+1..i-1}$实际上就是节点x在fa中,孩子序列上左边的点子树内所有点
而这个限制也形成了一棵树形结构,即每个点向其所在孩子序列中右边第一个点连边,如果已经是最后一个就向父亲连边
那么用上面的结论就好了,下界$O(n)$,code