提出 #35742866

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500005, M = N * 20, mod = 998244353, inv2 = (mod + 1) / 2;
int n;
string s[N];
int trie[M][26], tot, cnt1[M], cnt2[M];

void insert(string s) {
	int p = 0, len = s.length();
	for (int i = 0; i < len; ++i) {
		int c = s[i] - 'a';
		if (!trie[p][c]) trie[p][c] = ++tot;
		p = trie[p][c];
		if (i != len - 1) ++cnt1[p];
	}
	++cnt2[p];
}

int pre(string s) {
	int p = 0, res = 0, len = s.length();
	for (int i = 0; i < len; ++i) {
		int c = s[i] - 'a';
		p = trie[p][c], res += cnt2[p];
	}
	return res;
}

int suf(string s) {
	int p = 0, len = s.length();
	for (int i = 0; i < len; ++i) {
		int c = s[i] - 'a';
		p = trie[p][c];
	}
	return cnt1[p];
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> s[i], insert(s[i]);
	for (int i = 1; i <= n; ++i) {
		int a = pre(s[i]), b = suf(s[i]);
		cout << 1ll * (a - b + n) * inv2 % mod << '\n';
	}
	return 0;
}

提出情報

ジャッジ結果