結果
問題 | No.2626 Similar But Different Name |
ユーザー |
![]() |
提出日時 | 2024-02-09 22:18:06 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 162 ms / 3,000 ms |
コード長 | 2,449 bytes |
コンパイル時間 | 2,823 ms |
コンパイル使用メモリ | 172,412 KB |
実行使用メモリ | 29,284 KB |
最終ジャッジ日時 | 2024-09-28 15:33:41 |
合計ジャッジ時間 | 6,481 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <iterator>#include <string>#include <cctype>#include <cstring>#include <cstdlib>#include <cassert>#include <cmath>#include <ctime>#include <iomanip>#include <numeric>#include <stack>#include <queue>#include <map>#include <unordered_map>#include <set>#include <unordered_set>#include <bitset>#include <random>#include <utility>#include <functional>#include <atcoder/modint>#include <atcoder/convolution>using namespace std;using mint = atcoder::modint998244353;using ull = unsigned long long;const ull mod = (1ULL << 61) - 1;ull mul(ull a,ull b){ull au = a >> 31;ull ad = a & ((1ULL << 31)-1);ull bu = b >> 31;ull bd = b & ((1ULL << 31)-1);ull mid = au*bd + bu*ad;ull midu = mid >> 30;ull midd = mid & ((1ULL << 30)-1);ull res = au*bu*2 + midu + (midd << 31) + ad*bd;res = (res >> 61) + (res & mod);if(res >= mod) res -= mod;return res;}mt19937_64 mt{(unsigned int)time(nullptr)};void Main(){ull base = mt() % mod;int N,M,K;cin >> N >> M >> K;string S,T;cin >> S >> T;string s = S,t = T;for(char &c : s){if('A' <= c && c <= 'Z'){c -= 'A';c += 'a';}}for(char &c : t){if('A' <= c && c <= 'Z'){c -= 'A';c += 'a';}}vector<int> match(N - M + 1);{vector<ull> H(N + 1);for(int i = 0;i < N;i++){H[i + 1] = mul(H[i],base) + s[i];}ull h = 0;ull p = 1;for(int i = 0;i < M;i++){p = mul(p,base);h = mul(h,base) + t[i];}for(int i = 0;i + M <= N;i++){ull cur = H[i + M] + mod - mul(H[i],p);if(cur >= mod){cur -= mod;}if(cur == h){match[i] = 1;}}}vector<mint> A(N),B(N),C(M),D(M);for(int i = 0;i < N;i++){if('A' <= S[i] && S[i] <= 'Z'){A[i] = mint::raw(1);}else{B[i] = mint::raw(1);}}for(int i = 0;i < M;i++){if('A' <= T[i] && T[i] <= 'Z'){C[M - i - 1] = mint::raw(1);}else{D[M - i - 1] = mint::raw(1);}}vector<mint> P = atcoder::convolution(A,D),Q = atcoder::convolution(B,C);int ans = 0;for(int i = 0;i + M <= N;i++){if(match[i]){int cur = (int)P[i + M - 1].val() + (int)Q[i + M - 1].val();if(1 <= cur && cur <= K){ans++;}}}cout << ans << "\n";}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;/* cin >> tt; */while(tt--) Main();}