結果

問題 No.2626 Similar But Different Name
ユーザー tobisatistobisatis
提出日時 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/

ソースコード

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
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0