結果
問題 | No.2626 Similar But Different Name |
ユーザー |
|
提出日時 | 2024-02-09 23:11:26 |
言語 | C# (.NET 8.0.404) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 10,922 bytes |
コンパイル時間 | 7,155 ms |
コンパイル使用メモリ | 166,800 KB |
実行使用メモリ | 261,456 KB |
最終ジャッジ日時 | 2024-09-28 16:25:27 |
合計ジャッジ時間 | 63,299 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 TLE * 15 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (84 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
namespace AtCoder;#nullable enableusing System.Numerics;static class Extensions{public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();}struct FormalPowerSeries :IAdditiveIdentity<FormalPowerSeries, FormalPowerSeries>,IAdditionOperators<FormalPowerSeries, FormalPowerSeries, FormalPowerSeries>,IMultiplicativeIdentity<FormalPowerSeries, FormalPowerSeries>,IUnaryNegationOperators<FormalPowerSeries, FormalPowerSeries>,ISubtractionOperators<FormalPowerSeries, FormalPowerSeries, FormalPowerSeries>,IMultiplyOperators<FormalPowerSeries, FormalPowerSeries, FormalPowerSeries>,IDivisionOperators<FormalPowerSeries, FormalPowerSeries, FormalPowerSeries>{public const int p = 998244353; // static int p = -1;const long small = 8; // 1L << 40; // no convolutionpublic static int Max = -2; // x ^ 0 ... x ^ Maxpublic long[] Series { get; private init; }public readonly int Degree => Series.Length - 1;static long Mod(long v) => (v % p + p) % p;public FormalPowerSeries(long[] series){var indices = NonZeroValueIndices(series);var maxIndex = 0;if (indices.Length > 0) maxIndex = indices[^1];var n = Math.Min(Max, maxIndex) + 1;var s = new long[n];foreach (var i in indices) if (i <= n) s[i] = Mod(series[i]);Series = s;}public static implicit operator FormalPowerSeries(long[] series) => new(series);public static implicit operator FormalPowerSeries(long k) => new(new[]{ k });public readonly long this[int index]{get => index <= Degree ? Series[index] : 0;set { Series[index] = value; }}public static FormalPowerSeries operator +(FormalPowerSeries y1, FormalPowerSeries y2){if (y1.Degree > y2.Degree) (y1, y2) = (y2, y1);var res = new long[y2.Degree + 1];for (var i = 0; i <= y1.Degree; i++){var sum = y1[i] + y2[i];if (sum >= p) sum -= p;res[i] = sum;}for (var i = y1.Degree + 1; i <= y2.Degree; i++) res[i] = y2[i];return new(res);}public static FormalPowerSeries operator -(FormalPowerSeries y) => y * -1;public static FormalPowerSeries operator -(FormalPowerSeries y1, FormalPowerSeries y2) => y1 + y2 * -1;// y2[0] must not be zeropublic static FormalPowerSeries operator /(FormalPowerSeries y1, FormalPowerSeries y2){var y2i = NonZeroValueIndices(y2.Series);if (y2i.Length < small){var res = new long[Max + 1];var inverse = Pow(y2[0], -1);for (var i = 0; i <= y1.Degree; i++) res[i] = Mod(y1.Series[i] * inverse);for (var i = 0; i <= Max; i++) for (var k = 1; k < y2i.Length; k++){var j = y2i[k];if (j == 0) continue;if (i + j > Max) break;res[i + j] = Mod(res[i + j] - Mod(res[i] * y2[j]) * inverse);}return new(res);}return y1 * y2.Inverse();}public readonly FormalPowerSeries Inverse(){var g = new FormalPowerSeries(new long[] { Pow(Series[0], -1) });while (g.Degree < Max){var l = (g.Degree + 1) * 2;var f = -g * GetResizedArray(Series, l);f[0] = Mod(f[0] + 2);g = GetResizedArray((f * g).Series, l);}return g;}public static FormalPowerSeries operator *(FormalPowerSeries y1, FormalPowerSeries y2){if (IsAdditiveIdentity(y1) || IsMultiplicativeIdentity(y2)) return y1;if (IsAdditiveIdentity(y2) || IsMultiplicativeIdentity(y1)) return y2;var (f, g) = (y1.Series, y2.Series);var fi = NonZeroValueIndices(f);var gi = NonZeroValueIndices(g);var m = f.Length + g.Length - 1;if (Math.Min(fi.Length, gi.Length) < small){var res = new long[m];foreach (var i in fi) foreach (var j in gi) res[i + j] = (f[i] * g[j] + res[i + j]) % p;return new(res);}var (n, shift) = (1, 0);while (n < m) (n, shift) = (n << 1, shift + 1);var ft = FastModuloTransform(GetResizedArray(f, n), shift);var gt = FastModuloTransform(GetResizedArray(g, n), shift);for (var i = 0; i < n; i++) ft[i] = ft[i] * gt[i] % p;ft = FastModuloTransform(ft, shift, true);var nInverse = Pow(n, -1);for (var i = 0; i < n; i++) ft[i] = ft[i] * nInverse % p;return new(GetResizedArray(ft, m));}static int[] NonZeroValueIndices(long[] a){var res = new List<int>();for (var i = 0; i < a.Length; i++) if (a[i] != 0) res.Add(i);return res.ToArray();}public static FormalPowerSeries AdditiveIdentity => new(new[]{ 0L });public static FormalPowerSeries MultiplicativeIdentity => new(new[]{ 1L });static bool IsAdditiveIdentity(FormalPowerSeries f) => f.Series.Length == 1 && f[0] == 0;static bool IsMultiplicativeIdentity(FormalPowerSeries f) => f.Series.Length == 1 && f[0] == 1;static readonly int[] roots, rootsInverse;static FormalPowerSeries(){roots = new int[24];rootsInverse = new int[24];roots[23] = Pow(3, 119);rootsInverse[23] = Pow(roots[23], -1);for (var i = 23; i > 0; i--){roots[i - 1] = (int)(1L * roots[i] * roots[i] % p);rootsInverse[i - 1] = (int)(1L * rootsInverse[i] * rootsInverse[i] % p);}}static long[] FastModuloTransform(long[] f, int shift, bool inverse = false){var l = f.Length;if (l < 2) return f;var n = l >> 1;var f1 = new long[n];var f2 = new long[n];for (var i = 0; i < n; i++){f1[i] = f[i * 2];f2[i] = f[i * 2 + 1];}f1 = FastModuloTransform(f1, shift - 1, inverse);f2 = FastModuloTransform(f2, shift - 1, inverse);var ft = new long[l];long rotation = 1;var mask = n - 1;for (var i = 0; i < l; i++){ft[i] = (rotation * f2[i & mask] + f1[i & mask]) % p;rotation = rotation * (inverse ? roots[shift] : rootsInverse[shift]) % p;}return ft;}static int Pow(long n, int m){if (m < 0) m = (m % (p - 1)) + p - 1;var res = 1L;long k = n;while (m > 0){if ((m & 1) > 0) res = res * k % p;k = k * k % p;m >>= 1;}return (int)res;}static long[] GetResizedArray(long[] array, int n){var res = new long[n];Array.Copy(array, res, Math.Min(array.Length, n));return res;}}class RollingHash{static readonly long b = new Random().Next(int.MaxValue / 2, int.MaxValue);static long[] Digit { get; set; } = new long[]{ 1 };long[] Hash { get; init; }public string String { get; init; }public RollingHash(string s) // chars must not be 0{var n = s.Length;Resize(n + 1);Hash = new long[n + 1];for (var i = 1; i <= n; i++) Hash[i] = Mod(Mul(Hash[i - 1], b) + s[i - 1]);String = s;}public long Slice(int begin) => Slice(begin, Length - begin);public long Slice(int begin, int length) => Mod(Hash[begin + length] - Mul(Hash[begin], Digit[length]));public int Length { get => Hash.Length - 1; }static void Resize(int size){var l = Digit.Length;if (l >= size) return;while (l < size) l <<= 1;var d = new long[l];d[0] = 1;for (var i = 1; i < l; i++) d[i] = Mod(Mul(d[i - 1], b));Digit = d;}const long M61 = (1L << 61) - 1;const long M31 = (1L << 31) - 1;const long M30 = (1L << 30) - 1;static long Mul(long x, long y){long xu = x >> 31;long xd = x & M31;long yu = y >> 31;long yd = y & M31;long head = xu * yu * 2;long mid = xd * yu + xu * yd;long midu = mid >> 30;long midd = mid & M30;long last = Mod(xd * yd);return Mod(head + midu + (midd << 31) + last);}static long Mod(long x){while (x < 0) x += M61;long y = (x >> 61) + (x & M61);if (y >= M61) y -= M61;return y;}}class AtCoder{object? Solve(){var n = Int();var m = Int();var k = Int();var so = String();var t = String();var to = new string(t.Reverse().ToArray());FormalPowerSeries.Max = n + m + 1;var asb0 = new long[n];var asb1 = new long[n];for (var i = 0; i < n; i++){if (so[i] - 'Z' <= 0) asb0[i] = 1;asb1[i] = 1 - asb0[i];}var atb0 = new long[n];var atb1 = new long[n];for (var i = 0; i < m; i++){if (to[i] - 'Z' <= 0) atb0[i] = 1;atb1[i] = 1 - atb0[i];}var f = new FormalPowerSeries(asb0) * new FormalPowerSeries(atb1) + new FormalPowerSeries(asb1) * new FormalPowerSeries(atb0);var sh = new RollingHash(so.ToLower());var th = new RollingHash(t.ToLower()).Slice(0);var ans = 0L;for (var i = m - 1; i < n; i++){var b = i - m + 1;if (sh.Slice(b, m) != th) continue;if (0 < f[i] && f[i] <= k) ans++;}return ans;}public static void Main() => new AtCoder().Run();public void Run(){var res = Solve();if (res != null){if (res is bool yes) res = yes ? "Yes" : "No";sw.WriteLine(res);}sw.Flush();}string[] input = Array.Empty<string>();int iter = 0;readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };#pragma warning disable IDE0051string String(){while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0);return input[iter++];}T Input<T>() where T : IParsable<T> => T.Parse(String(), null);int Int() => Input<int>();void Out(object? x, string? separator = null){separator ??= Environment.NewLine;if (x is System.Collections.IEnumerable obj and not string){var firstLine = true;foreach (var item in obj){if (!firstLine) sw.Write(separator);firstLine = false;sw.Write(item);}}else sw.Write(x);sw.WriteLine();}#pragma warning restore IDE0051}