牛客小白月赛35 反·反爬虫函数

观察这个计算tta的函数发现，这个函数的值域是，而且多次运行发现这个函数的结果非常随机。

那么随机一个字符串得到任意一个结果的概率均为。

那么对于这种加密算法给出他的结果求一个原串，显然可以采用爆破的方法。

随机出个长度为8的字符串进行爆破，若函数完全随机的情况下，1009个值域全部爆破完成的概率可以用以下算法求解：

令表示一共有个值域，使用了个字符串进行爆破，共有个值域被爆破的概率。可以得到转移方程：

#include <bits/stdc++.h>

int main() {
  int c = 20000, m = 1009;
  std::vector<std::vector<double>> dp(c + 1, std::vector<double>(m + 1, 0.0));
  dp[0][0] = 1.0;
  for (int i = 1; i <= c; i++) {
    for (int j = 1; j <= m; j++) {
      dp[i][j] = dp[i - 1][j] * j / m + dp[i - 1][j - 1] * (m - j + 1) / m;
    }
  }
  std::cout << std::fixed << std::setprecision(10) << dp[c][m] << '\n';
}

用上面的算法可以求出C为20000时，全部值域被爆破的概率已经大于0.99999。

爆破个字符串的时间复杂度为。显然，直接爆破是可行的。

爆破完成后对于每一个询问的答案可以直接从数组中获取。

最终代码：

from typing import List
import random
import string


def gen(n: int) -> str:
    return ''.join(random.choice(string.ascii_letters + string.digits) for _ in range(n))


def calculatetta(a: str):
    b = 0
    for c in range(len(a)):
        b = (b + (c + 1) * (c + 2) * ord(a[c])) % 1009
        if c % 3 == 0:
            b = b + 1
        if c % 2 == 0:
            b = b * 2
        if c > 0:
            b = b - (ord(a[c // 2]) // 2) * (b % 5)
        while b < 0:
            b = b + 1009
        while b >= 1009:
            b = b - 1009
    return b


def init() -> List[str]:
    res = ['' for _ in range(1009)]
    count = 0
    while count < 1009:
        s = gen(8)
        tta = calculatetta(s)
        if res[tta] == '':
            res[tta] = s
            count += 1
    return res


def main():
    res = init()
    t = int(input())
    for _ in range(t):
        n = int(input())
        print(-1 if n >= 1009 else res[n])


if __name__ == '__main__':
    main()