Java 解法, 执行用时: 252ms, 内存消耗: 31672K, 提交时间: 2022-05-08 16:37:36

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class Main {
    private static final int M = 17;
    private static final long P1 = 998244353;
    private static final long P2 = 1000000007;
    private static final long[] SECRETS = new long[1000];
    private static final ArrayList<Long> V1 = new ArrayList<>();
    private static final ArrayList<Long> V2 = new ArrayList<>();
    private static final HashMap<Long, Integer> MAP = new HashMap<>();
    
    private static long nextSecret(long secret, int indexNumber) {
        return (secret ^ indexNumber) * indexNumber % P1 * P2 % P1;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = reader.readLine().split(" ");
        long secret = Long.parseLong(temp[0]);
        int L = Integer.parseInt(temp[1]);
        temp[0] = reader.readLine();
        SECRETS[0] = secret;

//        生成后续秘钥
        for (int i = 1; i < 1000; i++) {
            long lastSecret = SECRETS[i - 1];
            SECRETS[i] = nextSecret(lastSecret, i);
        }
        
        for (int i = 0; i < M; i++) {
            V1.add(SECRETS[L + i]);
            V2.add(SECRETS[L + i + M]);
        }
        
        for (int i = 0; i < 1 << M; i++) {
            long sum = 0;
            for (int j = 0; j < M; j++) {
                if ((i >> j & 1) != 0) {
                    sum += V2.get(j) * 2;
                } else {
                    sum += V2.get(j);
                }
            }
            sum %= P1;
            MAP.put(sum, i);
        }
        
        for (int i = 0; i < 1 << M; i++) {
            long sum = 0;
            for (int j = 0; j < M; j++) {
                if ((i >> j & 1) != 0) {
                    sum += V1.get(j) * 2;
                } else {
                    sum += V1.get(j);
                }
            }
            sum %= P1;
            sum = (P1 - sum) % P1;
            temp[1] = temp[0];
            
//            伪造hash
            if (MAP.get(sum) != null) {
                for (int j = 0; j < M; j++) {
                    if ((i >> j & 1) != 0) {
                        temp[1] += 'b';
                    } else {
                        temp[1] += 'a';
                    }
                }
                for (int j = 0; j < M; j++) {
                    if ((MAP.get(sum) >> j & 1) != 0) {
                        temp[1] += 'b';
                    } else {
                        temp[1] += 'a';
                    }
                }
                System.out.println(temp[1]);
                break;
            }
        }
    }
}

C++ 解法, 执行用时: 77ms, 内存消耗: 7532K, 提交时间: 2022-03-11 15:44:02

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const long long p1 = 998244353, p2 = 1000000007;
void next_secret(long long &secret, long long index_number) {
    secret = (secret ^ index_number) * index_number % p1 * p2 % p1;
}
long long string_hash(long long secret, string str) {
    long long hash_value = 0;
    for (int i = 0; i < str.length(); i++){
        hash_value = (hash_value + secret * (str[i] - 'a' + 1)) % p1;
        next_secret(secret, i + 1);
    }
    return hash_value;
}
const int N = 1000;
ll val[N];
int main(){
   int x,n; cin>>x>>n;//输入密钥以及长度
    string s; cin>>s;
    val[0] = x;
    for(int i=1;i<N;i++){
        val[i] = val[i-1];
        next_secret(val[i],i);
    }
    int M = 17;
    vector<int> v1,v2;
    for(int i=0;i<M;i++){
        v1.push_back(val[n+i]);
        v2.push_back(val[n+i+M]);
    }
    map<int,int> m;
    for(int i=0;i<1<<M;i++){
        ll sum = 0;
        for(int j=0;j<M;j++){
            if(i>>j&1) sum += v2[j] * 2;
            else sum += v2[j];
        }
        sum %= p1;
        m[sum] = i;
    }
      for(int i=0;i<1<<M;i++){
        ll sum = 0;
        for(int j=0;j<M;j++){
            if(i>>j&1) sum += v1[j] * 2;
            else sum += v1[j];
        }
        sum %= p1;
        sum = (p1 - sum) % p1;
        if(m[sum]){
            for(int j=0;j<M;j++){
                if(i>>j&1) s += 'b';
                else s += 'a';
            }
            for(int j=0;j<M;j++){
                if(m[sum]>>j&1) s += 'b';
                else s += 'a';
            }
            cout<<s<<endl;
//            cout<<string_hash(x,s)<<endl;
            break;
        }
    }
}