QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234672#4187. Decrypting ZodiacFyind#TL 4ms5940kbC++202.5kb2023-11-01 20:39:432023-11-01 20:39:44

Judging History

你现在查看的是最新测评结果

  • [2023-11-01 20:39:44]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:5940kb
  • [2023-11-01 20:39:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef int ll;
const int maxn = 3e5 + 5;
const ll MOD = 998244353;
const ll G = 3, Gi = 332748118;

inline ll mul(ll a, ll b) {
    return (1ll*a * b) % MOD;
}

ll fpow(ll a, ll n) {
    a %= MOD; ll ret = 1;
    for (; n; n >>= 1, a = mul(a, a) )
    	if (n & 1) ret = mul(ret, a);
    return ret;
}

void ntt(vector<ll> &a, int len, int op) {
    while (sz(a) < len) a.push_back(0);
    vector<int> R(len);
    R[0] = 0;
    for (int i = 1;i < len; ++i) {
        R[i] = (R[i>>1]>>1) + (i&1)*(len>>1);
        if (i < R[i]) swap(a[i], a[R[i]]);
    }
    for(int mid = 1; mid < len; mid <<= 1) {	
		ll Wn = fpow( op == 1 ? G : Gi , (MOD - 1) / (mid << 1));
		for(int j = 0; j < len; j += (mid << 1)) {
			ll w = 1;
			for(int k = 0; k < mid; k++, w = mul(w, Wn)) {
                ll x = a[j + k], y = mul(w, a[j + k + mid]);
                a[j + k] = (x + y) % MOD,
                a[j + k + mid] = (x - y + MOD) % MOD;
			}
		}
	}
    ll iv = fpow(len, MOD - 2);
    if (op == -1) for(int i = 0; i < len; i++) a[i] = mul(a[i], iv);
}

vector<ll> convolution(vector<ll>& a, vector<ll>& b) {
    int len = 1;
    int lans = sz(a) + sz(b) - 1;
    while (len < lans) len <<= 1;
    ntt(a, len, 1);
    ntt(b, len, 1);
    vector<ll> ret(lans);
    for (int i = 0;i < len; ++i) a[i] = mul(a[i], b[i]);
    ntt(a, len, -1);
    for (int i = 0;i < lans; ++i) ret[i] = a[i];
    return ret;
}


int n, m;
int A[maxn], B[maxn], C[maxn];

int solve() {
    vector<int> eq(n*2);
    for (int c = 0;c < 26; ++c) { 
        vector<ll> polya(n), polyc(n*2);
        for (int i = 0;i < n; ++i) polya[i] = A[n-i] == c;
        for (int i = 0;i < n*2; ++i) polyc[i] = C[i+1] == c;
        auto poly = convolution(polya, polyc);
        for (int i = n-1;i < n*2; ++i) {
            eq[i] += poly[i];
        }
    }
    return n - *max_element(eq.begin()+n-1, eq.end());
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        char c; cin >> c;
        A[i] = c - 'a';
    } 
    for (int i = 1;i <= n; ++i) {
        char c; cin >> c;
        B[i] = c - 'a';
    }
    int ans = 1e9;
    for (int k = 0;k <= 25; ++k) { 
        for (int i = 1;i <= n; ++i) {
            C[i] = (B[i] + k) % 26;
            C[i + n] = C[i];
        }
        ans = min(ans, solve());
    }
    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5940kb

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 3ms
memory: 5704kb

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 4ms
memory: 3892kb

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Time Limit Exceeded

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:


result: