Atcoder arc144
D
题目
https://atcoder.jp/contests/arc144/tasks/arc144_d
有多少个映射f满足
定义域[0..2^n-1]
值域[0..k]
且值域内任意值x,y满足
f(x) + f(y) = f(x & y) + f(x | y)
范围
n 3e5
k 1e18
2s
1024mb
题解
我的思路
f(…0) + f(1) = f(…1) + f(0)
f(…0.) + f(10) = f(…1.) + f(0)
因此 自由元素 f(0) f(1) f(2) f(4) …
把 f(0..2^{n-1}-1)看作整体, 那么 f(2^{n-1}..2^{n}-1) 可以看作它的平移
显然有
dp[i][min][max] = sum{dp[i-1][min][min..max]} + sum{dp[i-1][min..max][max]} - dp[i-1][min][max]
然而这 $O(nk^2)$ 显然时间空间都接受不了
不知道怎么化简
题解
跟着上面思路 如果 f(0) = 0 , 那么 f(x) = 按二进制拆开x的 sum f(bit)
相当于 f(1) + f(2) + f(4) + f(8) … <= k 插板组合数
如果f(0) != 0, 令 f(0) = V
那么令 g(x) = f(x) - V
那么g(x) 也满足条件, -V <= g(x) <= K - V
0 <= sum g(任意2幂) + V <= k
sum 正g(2幂) + V <= k
sum 负g(2幂) + V >= 0
然后就是
枚举f(0) 的值V
枚举正数个数i, i个正的和 $\le k-V$, 因为小于等于 所以不妨把k-V-和+1 看作一个新的正数,相当于 i+1个正数 和 = k-V+1, 那就是k-V空隙插i个板子
枚举负数个数j,同理
$\sum_{V=0}^k \sum_{i=0}^n \sum_{j=0}^{n-i} \binom{n}{i} \binom{n-i}{j} \binom{k-V}{i} \binom{V}{j}$
$\sum_{i=0}^n \sum_{j=0}^{n-i} \binom{n}{i} \binom{n-i}{j} (\sum_{V=0}^k \binom{k-V}{i} \binom{V}{j})$
$\sum_{i=0}^n \sum_{j=0}^{n-i} \binom{n}{i} \binom{n-i}{j} (\sum_{V=j}^{k-i} \binom{k-V}{i} \binom{V}{j})$
右侧括号里,可以想成$k+1$个球, 选出$i+j+1$个球的组合方案数
我们去枚举被选的第$i+1$个球的位置$p$, $p \in [i+1,k+1-j]$
那么左侧有$p-1$个, 需要选出$i$个, 右侧有$k + 1 - p$个需要选出$j$个
令$V = k + 1 - p$即和现在表达式一致了
所以
$\sum_{i=0}^n \sum_{j=0}^{n-i} \binom{n}{i} \binom{n-i}{j} \binom{k+1}{i+j+1}$
$\sum_{i=0}^n \sum_{j=0}^{n-i} \binom{i+j}{i} \binom{n}{i+j} \binom{k+1}{i+j+1}$
$\sum_{i+j \le n} \binom{i+j}{i} \binom{n}{i+j} \binom{k+1}{i+j+1}$
二项式和
$\sum_{s = 0}^n 2^s \binom{n}{s} \binom{k+1}{s+1}$
就可以做了
代码
https://atcoder.jp/contests/arc144/submissions/33279666
1 |
|
E
题目
N点,M边有向图
有向边 都是从小节点指向大节点的(无自环,无重边)
输入一个初始W[1..N],其中如果是Wi=-1,就可以取任何值,否则按给定的来
点i 权重 Wi
求最大从1到N的所有路径的权重和的gcd
如果gcd可能无限大则输出-1
不需要输出W的方案
范围
N 3e5
M 3e5
至少存在一条路径
初始Wi [1…10e12]
2s
1024MB
题解
我的思路
首先 如果存在一条完全给定的 1->N的权重和则有限大,否则可能无限大(A->B, B->C->D, B->D, 其中B任意,而后面指定两条路径不等, 那么gcd也是有限大)
对于有限大, 因为有向边全是从小指向大, 所以不成环只有拓扑关系
在没有具体值的情况, 并不能对求和的表达式计算gcd
所以考虑有没有可能反过来
反过来指定gcd, 1个问题是并没有二分性质, 每条边的可能性是考虑mod gcd,也是gcd个, 量级也不会太小
对于直接有指定W路径的相对好一些, 其中gcd一定是它的约数,这样情况会少一些,但是Ai和M都很大,即使给定的路径W和也可以达到3e17
题解
首先干掉 1不能到达, 和 不能到达N的点(无效的点), 防止无效的点影响找环的结果
如果k是答案,那么也就是所有路径 和 %k == 0
那么假设 到点u, (1 -> u)%k = p[u] 是唯一的
那么所有直接相邻的 vi->u, 有 p[vi] + w[u] = p[u] (mod k)
说明p[vi] 全部一样
这样, 就并查集了!
然后p[n] = 0, 所以可以加0号点 W[0] = 0, 路径0->1
有直接相邻u->v,且w[v]给定,
说明 两个并查集里的 的union[u] + 3 = union[v]
变成了 一些点, 和一些有权有向边
找所有环, 求gcd, 并不能找所有环,但是gcd性质上, 所有环gcd = 所有(树+回边) gcd
所以就可以搞了
环即可能由0产生, 也会有形如A->B->C->D, A->D, 这样产生
无环 就任意都可以, -1
然后有向图找环 我真不会写
学了一下apiad巨佬的代码, 发现是所有边建立正向和负向, 保证任何简单复杂路径 = 端点简单路径和即 全部像是无向图的有向图, 这样任何一个点可以作为根
代码
https://atcoder.jp/contests/arc144/submissions/33329393
1 |
|
总结
D
这个对f(0) = 0特殊讨论 ,在 讨论f(0) 不为零的转化, 就是 一个特殊边界讨论 + 向特殊转移的问题
然后什么神奇的范德蒙恒等式(这里并不是, 但有一点思路相近的感觉
$\binom{n+m}{k} = \sum_{i=0}^k \binom{m}{i} \binom{n}{k-i}$
其实就是考虑$(1+x)^{m+n}$的$x^k$系数和 $(1+x)^m\cdot (1+x)^n$的$x^k$的系数
总之还有一些组合数的技巧,不是光有了初始表达式就可以的
E
讨论满足目标条件的 相邻转移
然后这个有向找所有环的gcd 也是学了一手, 改成正负双向