Submission #1197670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197670		qrn	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	1595 ms	24640 KiB

selling_rna

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 41;
const intt inf = 1e18;
const intt mxN = 400005;
const intt L = 21;

vector<intt> inv(mxN), pw(mxN);

intt binpow(intt a, intt b) {
	intt res = 1;
	while(b) {
		if(b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b/= 2;
	}
	return res;
}

void solve() {
	intt N, M;
	cin >> N >> M;
	
	vector<string> A(N);
	vector<vector<intt>> H(N, vector<intt> {});
	for(auto &a : A) cin >> a;

	for(intt i = 0; i < N; i++) {
		// cout << i << endl;
		string s = A[i];
		H[i].assign(s.size(), 0ll);
		
		H[i][0] = (s[0] - 'A' + 1);
		for(intt j = 1; j < s.size(); j++) {
			H[i][j] = (H[i][j-1] + ((s[j] - 'A' + 1) * pw[j]) % mod) % mod;
		}
	}

	while(M--) {
		string P, Q;
		cin >> P >> Q;
		intt n = P.size(), nn = Q.size();
		vector<intt> curH(N, 0ll), curRH(nn, 0ll);
		curH[0] = (P[0] - 'A' + 1);
		for(intt i = 1; i < n; i++) {
			curH[i] = (curH[i-1] + ((P[i] - 'A' + 1) * pw[i]) % mod) % mod;
		}
		curRH[0] = (Q[0] - 'A' + 1);
		for(intt i = 1; i < nn; i++) {
			curRH[i] = (curRH[i-1] + ((Q[i] - 'A' + 1) * pw[i]) % mod) % mod;
		}

		intt forthis = 0;
		for(intt i = 0; i < N; i++) {
			intt cn = A[i].size()-1;
			if(n-1 >= A[i].size() && nn-1 >= A[i].size()) continue;
			intt sag = 0;
			if(cn - nn >= 0) sag = H[i][cn-nn];
			intt hasval = (H[i][cn] - sag + mod) % mod;
			if(curH[n-1] == H[i][n-1] && hasval == (curRH[nn-1] * pw[cn-nn+1]) % mod) {
				forthis++;
			}
		}
		cout << forthis << endl;
	}
}

signed main() {

	inv[0] = pw[0] = 1;
	for(intt i = 1; i < mxN; i++) {
		pw[i] = (pw[i-1] * base) % mod;
		inv[i] = binpow(pw[i], mod-2);
	}

	ios_base::sync_with_stdio(0); 
	cin.tie(NULL);                
	cout.tie(NULL);
	intt tst = 1, idx = 1;
	// cin >> tst;
	while(tst--) {
		// cout << "Case " << idx << ":" << endl; 
		solve();
		// idx++;
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40