iroha2019-day4题解

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
2
3
4
5
6
7
ll solve(int n,ll k,int w)
{
if(w<0) return 1;
int t=((k&bin(w))?n:0);ll ans=(t%2==0?solve(n,k,w-1):0);
if(t) fo(i,1,n) if((n-i)%2==0) add(ans,C(n,i)*qpower(bin(w)%MOD,i-1)%MOD*qpower(1+k%bin(w)%MOD,n-i)%MOD);
return ans;
}

这个是可以用类似单位根反演(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

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