結果
問題 | No.2102 [Cherry Alpha *] Conditional Reflection |
ユーザー |
![]() |
提出日時 | 2022-10-14 23:08:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,662 bytes |
コンパイル時間 | 2,248 ms |
コンパイル使用メモリ | 203,320 KB |
最終ジャッジ日時 | 2025-02-08 04:51:00 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 WA * 55 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct RollingHash {vector<long long> acc = {0};vector<long long> power = {1};int base = 17;int mod = 1000000007;RollingHash(string s) {for (int i=0; i<s.size(); i++) {acc.push_back((acc.back()*base+(s[i]-'a'))%mod);power.push_back(power.back()*base%mod);}}long long get(int l, int r) {long long h = (acc[r]-acc[l]*power[r-l])%mod;if (h<0) h += mod;return h;}};int main() {cin.tie(0); ios::sync_with_stdio(false);int N; cin >> N;set<long long> ws;for (int t=0; t<N; t++) {string s; cin >> s;RollingHash rh(s);long long h = rh.get(0, s.size());if (ws.find(h)!=ws.end()) cout << "Yes" << endl;else {bool ok = false;for (int i=0; i<s.size()-1; i++) {long long nh = h;nh -= (s[i]-'a')*rh.power[s.size()-1-i]%rh.mod;nh %= rh.mod;nh -= (s[i+1]-'a')*rh.power[s.size()-2-i]%rh.mod;nh %= rh.mod;nh += (s[i+1]-'a')*rh.power[s.size()-1-i]%rh.mod;nh %= rh.mod;nh += (s[i]-'a')*rh.power[s.size()-2-i]%rh.mod;nh %= rh.mod;if (nh<0) nh += rh.mod;if (ws.find(nh)!=ws.end()) {cout << "Yes" << endl;ok = true;break;}}if (!ok) cout << "No" << endl;}ws.insert(h);}}