結果

問題 No.2626 Similar But Different Name
ユーザー tobisatistobisatis
提出日時 2024-02-09 23:11:26
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 2,938 ms / 3,000 ms
コード長 10,922 bytes
コンパイル時間 7,366 ms
コンパイル使用メモリ 158,692 KB
実行使用メモリ 328,504 KB
最終ジャッジ日時 2024-02-09 23:12:32
合計ジャッジ時間 60,720 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 299 ms
37,144 KB
testcase_01 AC 298 ms
37,144 KB
testcase_02 AC 325 ms
37,148 KB
testcase_03 AC 300 ms
37,136 KB
testcase_04 AC 314 ms
37,136 KB
testcase_05 AC 304 ms
37,188 KB
testcase_06 AC 334 ms
37,148 KB
testcase_07 AC 311 ms
38,044 KB
testcase_08 AC 306 ms
37,964 KB
testcase_09 AC 306 ms
37,956 KB
testcase_10 AC 361 ms
51,476 KB
testcase_11 AC 327 ms
51,472 KB
testcase_12 AC 316 ms
44,108 KB
testcase_13 AC 355 ms
51,488 KB
testcase_14 AC 330 ms
51,496 KB
testcase_15 AC 328 ms
51,472 KB
testcase_16 AC 329 ms
51,508 KB
testcase_17 AC 350 ms
51,508 KB
testcase_18 AC 421 ms
95,092 KB
testcase_19 AC 421 ms
87,456 KB
testcase_20 AC 421 ms
84,564 KB
testcase_21 AC 408 ms
75,604 KB
testcase_22 AC 2,888 ms
328,504 KB
testcase_23 AC 2,899 ms
229,300 KB
testcase_24 AC 2,899 ms
256,004 KB
testcase_25 AC 2,857 ms
305,376 KB
testcase_26 AC 2,903 ms
229,280 KB
testcase_27 AC 2,938 ms
307,260 KB
testcase_28 AC 2,909 ms
328,360 KB
testcase_29 AC 2,869 ms
240,432 KB
testcase_30 AC 2,850 ms
305,500 KB
testcase_31 AC 2,881 ms
228,084 KB
testcase_32 AC 2,863 ms
231,396 KB
testcase_33 AC 2,909 ms
307,260 KB
testcase_34 AC 2,887 ms
255,276 KB
testcase_35 AC 2,907 ms
283,924 KB
testcase_36 AC 2,839 ms
256,020 KB
testcase_37 AC 439 ms
247,144 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (96 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
  main -> /home/judge/data/code/bin/Release/net7.0/main.dll
  main -> /home/judge/data/code/bin/Release/net7.0/publish/

ソースコード

diff # 

namespace AtCoder;

#nullable enable

using 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 convolution
    public static int Max = -2; // x ^ 0 ... x ^ Max
    public 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 zero
    public 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 IDE0051
    string 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
}
0