循环序列首次相等位置（胡乱想的问题，或许有些难度）
下面为方便描述，不妨用<01101>代指循环序列01101 01101 01101……假设这里有许多循环节长度互素的01序列，问有没有什么有效的方法找到这几个序列中的0-1首次相等的位置。
比如这里有循环序列<1>,<10110>,<001>,<01>，即：
111111111111111111111111111111111111111111111111111111111111……
101101011010110101101011010110101101011010110101101011010110……
001001001001001001001001001001001001001001001001001001001001……
010101010101010101010101010101010101010101010101010101010101……
我们可以用肉眼看到，这几个序列从左往右数第6个元素都是1，所以这几个序列在第六个元素处首次相等
对付这个问题我的想法暂时只有全写出来用眼睛慢慢看（或者用计算机实现类似的算法）
想知道有没有更有效的算法（如果序列数量不多同时序列不长，可以用MITM进行攻击（比如如果只有3个序列而第一个序列是<1>，我们可以利用长序列构造一个中间序列，以减少多次查找带来的负担）），又或者这个题目到底会不会是NPC（反正我没想到如何构造各种逻辑门）
附一个长序列跟短序列跟<1>的说明
假设三个序列是<1><0000100010000100000100001001><100001000100001000001000010010000100010000100000100001000>
首先肉眼查不到
000010001000010000010000100100001000100001000001000010010000100010000100000100001001000010001000010000010000100100……
100001000100001000001000010010000100010000100000100001000100001000100001000001000010010000100010000100000100001000……
然而呢，我们应该观测到这样一个事实，不妨把短序列打头的0换成*
*000100010000100000100001001*000100010000100000100001001*000100010000100000100001001*000100010000100000100001001*0……
100001000100001000001000010010000100010000100000100001000100001000100001000001000010010000100010000100000100001000……
我们注意到，*对应的五个位置分别是1-1-0-0-0，*后面那个0对应的分布是0-1-0-0-0，这给了我们一种提示，如果我们可以把这样的序列之中，只要出现1的都改成1，以此制作中间序列（此时中间序列长度等于短序列长度），再拿得到的中间序列跟短序列比较，如果发现某一个位置这两个序列都是1，就说明短序列与长序列在短序列的这个位置上一定会相等，究竟何时相等可以做一次复查，反正上例不会超过5次。
当然，如果不相等，需要重算这样的中间序列——这里唯一的好处就是，当我们利用长序列计算中间序列的时候，长序列上面的每一个元素对应的中间序列元素的值是固定的，于是我们只需要计算一次中间序列，就可以反复利用中间序列与短序列进行比较。
理想情况下，短序列会重复（长序列循环节长度）次，我们对（长序列循环节长度）开根号，依此选取我们要的搜索长度，这样我们差不多需要（根号（长序列循环节长度））次搜索，而生成中间序列需要（根号（长序列循环节长度））次，这样可以极大地减少计算量。
算法看上去很好而且有改进空间，但无可避免的是，算法无论如何也需要遍历长序列，这样如果长序列的循环节很长，会出问题，而当<>的数量增加的时候，哪怕每一个<>的长度都不太长（比如只有几千），几十个这样的<>加起来构成的长序列已经超长太多了 看做二进制整数，化为长度一样的整数（各循环节长度的最小公倍数），用取模或者BitAnd运算都可以。 lsr314 发表于 2018-8-20 17:44
看做二进制整数，化为长度一样的整数（各循环节长度的最小公倍数），用取模或者BitAnd运算都可以。
问题是……如果两个序列都很长
或者序列不止两个的时候，这个算法根本做不到
比如总共5个序列，序列长度分别为1，104743， 104759，104761， 104773
问题的输入并不会变得很复杂，但“化为长度一样的整数”这一步根本做不到
我们根本存不下一个120438508180343488061二进制数 假设某个长度为$k$的序列中$1$的个数为$k'$，它对应一个次数为$k'$，模为$k$的同余方程$(x-x_1)……(x-x_k')=0(mod k)$，在模$k$的意义下刚好有$k'$个解。
由于各序列长度互素，所以解的个数刚好是对应方程解的个数的乘积。
以序列长度分别为$1，104743， 104759，104761， 104773$为例，假如从第二个序列开始，对应序列中$1$的个数各占一半，那么大约每$2^4=16$个位置中就有$1$个全是$1$.
也就是说，大多数情况下，穷举可能是最快的。 lsr314 发表于 2018-8-21 10:20
假设某个长度为$k$的序列中$1$的个数为$k'$，它对应一个次数为$k'$，模为$k$的同余方程$(x-x_1)……(x-x_k' ...
然而特殊的情况下1的个数可能会远远少于1/2
比如你的某一个序列是由几个更短的序列合成的
当我们的序列数量达到几千的时候，穷举已经死掉了……
我现在想到的是一种针对两个稀疏的数列（比如都是$4e10$位附近），如果认真跑穷举可能会直接死掉，但我们可以用MITM（中间相遇攻击）算法，至多计算O(4e10*2e5)次就可以得到答案
当然想了想对稀疏数列这样做或许还不如直接把稀疏数列上面的每一个1取出来计算两个序列之中1相遇的位置然后取最小值……
这些方法都比穷举好，然而这些方法在数列很多的时候都会失效……
页:
[1]