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}$，

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