Language: C++

/*
RollingHash ある文字列sの長さlenの部分文字列のhashをO(|S|)で計算する
種類数を求める問題だとhashを使うと確率が跳ね上がるため、複数のmodが必須
詳しくは、 https://snuke.hatenablog.com/entry/2017/02/03/035524
mod = 2^61-1を使ったこのmodはかなり強いため、衝突の危険性はほとんどない上、速い
さらにbaseを複数使えるようにした
計算量O(|S|)
@verify https://atcoder.jp/contests/abc141/submissions/9227996
*/

template <uint_fast64_t basesize>
class RollingHash {
public:
	using u64 = uint_fast64_t;
	using i32 = int_fast32_t;
	using arr = array<u64, basesize>;
	const u64 mod = (1ull << 61) - 1;
	const u64 m30 = (1ull << 30) - 1;
	const u64 m31 = (1ull << 31) - 1;
	const u64 p31 = (1ull << 31);
	arr base;
	RollingHash() {
		random_device seed_gen;
		mt19937_64 engine(0);
		for (u64 i = 0; i < basesize; ++i) {
			base[i] = (engine() & m30) + m30;
		}
	}
	u64 mul(u64 a, u64 b) {
		u64 au = a >> 31;
		u64 ad = a & m31;
		u64 bu = b >> 31;
		u64 bd = b & m31;
		u64 mid = ad * bu + au * bd;
		u64 midu = mid >> 30;
		u64 midd = mid & m30;
		u64 res = au * bu * 2 + midu + (midd << 31) + ad * bd;
		return res;
	}
	u64 calcMod(u64 v) {
		v = (v & mod) + (v >> 61);
		if (v > mod)v - mod;
		return v;
	}
	vector<arr> calcHash(string &s,i32 l,i32 r) { // s[l,r)のhashを計算
		if (l >= r) {
			vector<arr> res(0);
			return res;
		}
		vector<arr> res(r - l);
		for (i32 j = 0; j < basesize ; ++j) {
			res[0][j] = s[l];
		}
		for (i32 i = 1; i < r - l; ++i) {
			for (i32 j = 0; j < basesize; ++j) {
				res[i][j] = calcMod(mul(res[i - 1][j], base[j]) + s[i + l]);
			}
		}
		return res;
	}
	vector<arr> calcHashLen(string& s, i32 len) {
		i32 l = (i32)s.size() - len + 1;
		vector<arr> pre = calcHash(s, 0, len);
		vector<arr> res(l);
		const u64 pos = mod * 3;
		arr p;
		fill(p.begin(), p.end(), 1);
		if (0 < len) {
			for (i32 j = 0; j < basesize; ++j) {
				res[0][j] = pre[len - 1][j];
			}
		}
		for (i32 i = 0; i < len; ++i) {
			for (i32 j = 0; j < basesize; ++j) {
				p[j] = calcMod(mul(p[j], base[j]));
			}
		}
		for (i32 i = 1; i < l; ++i) {
			for (i32 j = 0; j < basesize; ++j) {
				res[i][j] = calcMod(mul(res[i - 1][j], base[j]) + s[i - 1 + len]);//添え字周りが怪しい
				res[i][j] = calcMod(res[i][j] + pos - mul(s[i - 1], p[j]));				
			}
		}
		return res;
	}
};

constexpr uint_fast64_t  bs = 50;
using arr = array<uint_fast64_t, bs>;
using rh = RollingHash<bs>;

Compiler output:
a.cc:11:11: error: 'uint_fast64_t' has not been declared
   11 | template <uint_fast64_t basesize>
      |           ^~~~~~~~~~~~~
a.cc:14:21: error: 'uint_fast64_t' does not name a type
   14 |         using u64 = uint_fast64_t;
      |                     ^~~~~~~~~~~~~
a.cc:15:21: error: 'int_fast32_t' does not name a type
   15 |         using i32 = int_fast32_t;
      |                     ^~~~~~~~~~~~
a.cc:16:21: error: 'array' does not name a type
   16 |         using arr = array<u64, basesize>;
      |                     ^~~~~
a.cc:17:15: error: 'u64' does not name a type
   17 |         const u64 mod = (1ull << 61) - 1;
      |               ^~~
a.cc:18:15: error: 'u64' does not name a type
   18 |         const u64 m30 = (1ull << 30) - 1;
      |               ^~~
a.cc:19:15: error: 'u64' does not name a type
   19 |         const u64 m31 = (1ull << 31) - 1;
      |               ^~~
a.cc:20:15: error: 'u64' does not name a type
   20 |         const u64 p31 = (1ull << 31);
      |               ^~~
a.cc:21:9: error: 'arr' does not name a type
   21 |         arr base;
      |         ^~~
a.cc:29:9: error: 'u64' does not name a type
   29 |         u64 mul(u64 a, u64 b) {
      |         ^~~
a.cc:40:9: error: 'u64' does not name a type
   40 |         u64 calcMod(u64 v) {
      |         ^~~
a.cc:45:9: error: 'vector' does not name a type
   45 |         vector<arr> calcHash(string &s,i32 l,i32 r) { // s[l,r)のhashを計算
      |         ^~~~~~
a.cc:61:9: error: 'vector' does not name a type
   61 |         vector<arr> calcHashLen(string& s, i32 len) {
      |         ^~~~~~
a.cc:88:11: error: 'uint_fast64_t' does not name a type
   88 | constexpr uint_fast64_t  bs = 50;
      |           ^~~~~~~~~~~~~
a.cc:89:13: error: 'array' does not name a type
   89 | using arr = array<uint_fast64_t, bs>;
      |             ^~~~~
a.cc:90:24: error: 'bs' was not declared in this scope
   90 | using rh = RollingHash<bs>;
      |                        ^~
a.cc:90:26: error: template argument 1 is invalid
   90 | using rh = RollingHash<bs>;
      |                          ^