2020-2021:teams:alchemist:weekly_digest_12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_12 [2020/08/28 14:46] mountvoom [肖思炀 MountVoom] |
2020-2021:teams:alchemist:weekly_digest_12 [2020/08/28 17:26] (当前版本) hardict [龙鹏宇 Hardict] |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | cf div2 | + | cf div2 涨回原rating |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 107: | 行 107: | ||
| === 来源： === | === 来源： === | ||
| - | [[http://acm.hdu.edu.cn/showproblem.php?pid=6061|HDU 6061]] | + | [[https://codeforces.com/gym/102465/problem/J|SWERC 2018 J]] |
| === 标签： === | === 标签： === | ||
| - | 多项式卷积,NTT | + | hash碰撞，随机算法 |
| === 题意： === | === 题意： === | ||
| - | 先给定一个$f(x)=\sum_{i=0}^{n}c_{i}x^{i}$,然后求解$g(x)=f(x-\sum_{i}a_{i})=\sum_{i=0}^{n}b_{i}x^{i}$ | + | 给定一个随机数生成器，以及$4$个种子$S_i$，知道算法可以求得其运行$C_i$次会生成数$x_i$(这个需要一步一步求)，我们截取$x_i$二进制前$N$位，计算$w=x_1 \oplus x_2 \oplus x_3 \oplus x_4$，题目要求选取合适的$C_i$使$w=0$ |
| - | + | ||
| - | 输出$b_{i}$ | + | |
| === 题解： === | === 题解： === | ||
| - | $A=-sum{a[i]}$并取模变成求解$f(x+A)$少去正负计算 | ||
| - | 然后按$f(x+A)$每一项进行一个展开(会成一个三角表) | + | 下述$x_i$默认只保留二进制前$N$位 |
| + | |||
| + | 先考虑两个数情况，对于$x_1$与$x_2$，我们实际是要寻找$x_1=x_2$情况，对于给定种子$S_i$我们可以根据随机序列定义$Hash:h(S_i,x_1)=c_k$，即给定种子下生成值与次数的关系 | ||
| - | 目标多项式系数$b_j=\sum_{i \geq j} c_i A^{i-j} C_i^j$ | + | 那么$x_1=x_2$可以理解为对$x_1$的$Hash$在${x_2}$中寻找一次$原像碰撞$ |
| - | 化解后有$j!A^jb_j=\sum_{i=j}^{n} \frac{c_{i}i!A^i}{(i-j)!}$ | + | 将设我们对$x_1$进行哈希了$D$次，我们可以利用//生日攻击//知道$D=2^{\frac{N}{2}}$最优（或者利用期望耗费为$D+\frac{2^N}{D}$分析） |
| - | 整体上$g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j=0}^{n-i}\frac{c_{i+j}(i+j)!A^{i+j}}{j!}$ | + | 于是对于原题我们得到一种想法：对${x_1}$构建大小为$2^{\frac{N}{2}}$的哈希表，$x_3,x_4$随便生成，遍历${x_2}$寻找碰撞$x_1=x_2 \oplus x_3 \oplus x_4$，复杂度为$O(2^{\frac{N}{2}})$，会$TLE$ |
| - | 这里令$k=n-(i+j),g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j+k=n-i}\frac{c_{n-k}(n-k)!A^{n-k}}{j!} | + | 现在考虑利用$x_3,x_4$，可以考虑将$(x_1,x_2),(x_3,x_4)$看作两个整体，要求$x_1 \oplus x_2;\quad x_3 \oplus x_4$分别将前$M$比特位碰撞为0，再在对于两个整体在后$N-M$位中寻找 |
| - | =\sum_{k=0}^{n}\frac{x^{k}}{A^{k}k!}\sum_{n+k=i+j}\frac{c_{i}(i)!A^{i}}{(n-j)!}$ | + | 哈希，复杂度为$O(4*2^{\frac{M}{2}}$) |
| - | 将$\frac{1}{j!}$当作一个翻转(两者都可),求$\sum_{i}c_{i}i!A^{i}x^{i}$与$\sum_{i}\frac{1}{(n-i)!}x^{i}$的卷积,然后取结果$n+i$项系数即可 | + | $M$作为参数进行选取，理论$\frac{N}{2}$即可，但实际可能没有碰撞，调参后选取$\frac{2N}{3}+4$通过 |
2020-2021/teams/alchemist/weekly_digest_12.1598597219.txt.gz · 最后更改: 2020/08/28 14:46 由 mountvoom
