模拟赛T2为了防止被卡写了一百多行

复仇者_帅童

2025-08-12 16:16:00

发布于：浙江

38阅读

0回复

0点赞

rt，后面的题都没啥时间写了
附代码

#include <iostream>
#include <cstdio>
#include <random>
#include <ctime>
#include <vector>
#include <set>
#define int long long
using namespace std;
class Str{
	mt19937 rng;
	int mul, mod1, mod2;
	vector <int> v, v2, ksm1, ksm2;
	
	public:
	
	struct hval{
		int siz;
		int x, y;
		hval(){
			siz = 0, x = 0, y = 0;
		}
		hval(int _siz, int _x, int _y){
			siz = _siz, x = _x, y = _y;
		}
		bool operator < (const hval &b) const{
			if(x == b.x){
				if(y == b.y) return siz < b.siz;
				return y < b.y;
			}
			return x < b.x;
		}
		bool operator == (const hval &b) const{
			return (x == b.x && y == b.y && siz == b.siz);
		}
		friend ostream &operator << (ostream &cout, hval a){
			cout << a.siz << ' ' << a.x << ' ' << a.y;
			return cout;
		}
	};
	
	Str(){}
	void init(){
		rng.seed(time(0));
		mul = rng() % 1145 + 131;
		mod1 = (int)(rng() % (int)(1e9)) + (int)(1e9);
		mod2 = (int)(rng() % (int)(1e9)) + (int)(1e9);
	}
	void add(string s){
		for(int i = 0; i < s.size(); i++){
			if(v.empty()) v.push_back(s[i]), v2.push_back(s[i]), ksm1.push_back(1), ksm2.push_back(1);
			else{
				v.push_back((v.back() * mul + s[i]) % mod1);
				v2.push_back((v2.back() * mul + s[i]) % mod2);
				ksm1.push_back(ksm1.back() * mul % mod1);
				ksm2.push_back(ksm2.back() * mul % mod2);
				// cout << v[i] << ' ';
			}
		}
		// cout << '\n';
	}
	hval substr(int l, int r){
		if(l > r) return hval();
		if(l == 0){
			return hval(r + 1, v[r], v2[r]);
		}
		return hval(r - l + 1, ((v[r] - v[l - 1] * ksm1[r - l + 1]) % mod1 + mod1) % mod1, ((v2[r] - v2[l - 1] * ksm2[r - l + 1]) % mod2 + mod2) % mod2);
	}
	hval merge(hval s1, hval s2){
		return hval(s1.siz + s2.siz, (s1.x * ksm1[s2.siz] + s2.x) % mod1, (s1.y * ksm2[s2.siz] + s2.y) % mod2);
	}
	void clear(){
		v.clear();
		v2.clear();
		ksm1.clear();
		ksm2.clear();
		mul = rng() % 1145 + 131;
		mod1 = (int)(rng() % (int)(1e9)) + (int)(1e9);
		mod2 = (int)(rng() % (int)(1e9)) + (int)(1e9);
	}
	void test(){
		cout << mul << ' ' << mod1 << ' ' << mod2 << '\n';
	}
}h;
void solve(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	set <Str::hval> st;
	h.add(s);
	st.insert(h.substr(2, n - 1));
	for(int i = 0; i < n - 2; i++){
		st.insert(h.merge(h.substr(0, i), h.substr(i + 3, n - 1)));
	}
	cout << st.size() << '\n'; 
	h.clear();
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	h.init();
	// h.test();
	int t;
	cin >> t;
	while(t--) solve();
	
	return 0;
}