結果

問題 No.430 文字列検索
ユーザー yuimyoyuimyo
提出日時 2023-12-09 11:06:27
言語 C#
(.NET 8.0.203)
結果
WA  
実行時間 -
コード長 16,323 bytes
コンパイル時間 8,501 ms
コンパイル使用メモリ 167,344 KB
実行使用メモリ 191,188 KB
最終ジャッジ日時 2024-11-10 01:09:27
合計ジャッジ時間 10,758 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
27,776 KB
testcase_01 WA -
testcase_02 AC 87 ms
30,464 KB
testcase_03 AC 79 ms
30,352 KB
testcase_04 AC 49 ms
27,904 KB
testcase_05 AC 49 ms
28,160 KB
testcase_06 AC 47 ms
27,904 KB
testcase_07 AC 48 ms
28,032 KB
testcase_08 AC 84 ms
29,440 KB
testcase_09 AC 49 ms
27,904 KB
testcase_10 AC 54 ms
29,184 KB
testcase_11 AC 85 ms
30,464 KB
testcase_12 AC 84 ms
30,720 KB
testcase_13 AC 82 ms
30,436 KB
testcase_14 AC 82 ms
30,328 KB
testcase_15 AC 82 ms
30,712 KB
testcase_16 AC 82 ms
30,464 KB
testcase_17 AC 84 ms
191,188 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (98 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 # 

using AtCoder;
using AtCoder.Internal;
using Kzrnm.Competitive.IO;
using System;
using System.Buffers.Text;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics.X86;
using System.Text;
namespace Roliha.Problems
{
    using ModInt = StaticModInt<Mod998244353>;
    internal partial class ProblemA
    {
        static void Solve()
        {
            var S = cr.String();
            var M = cr.Int();
            var C = cr.Repeat<string>(M);

            var sizeMax = Math.Min(S.Length, 10);
            var b = new ModInt[sizeMax + 1];
            b[0] = 1;
            b[1] = 27;
            for (int i = 1; i < sizeMax; i++)
                b[i + 1] = b[i] * b[1];

            var actualHash = new ModInt[sizeMax + 1];
            for (int i = 0; i < sizeMax; i++)
                actualHash[i + 1] = actualHash[i] * b[1] + (S[i] - 'A' + 1);

            var hashCnt = new Dictionary<ModInt, int>();
            for(int i = 0; i < M; i++)
            {
                ModInt expectedHash = 0;
                for (int j = 0; j < C[i].Length; j++)
                    expectedHash = expectedHash * b[1] + (C[i][j] - 'A' + 1);
                if (!hashCnt.ContainsKey(expectedHash))
                    hashCnt[expectedHash] = 0;
                hashCnt[expectedHash]++;
            }

            var ans = 0;
            for(int i = 0; i < S.Length; i++)
            {
                for (int j = 1; j <= sizeMax; j++)
                {
                    if (hashCnt.ContainsKey(actualHash[j]))
                    {
                        //cw.WriteLine($"({i}, {j}) +{hashCnt[actualHash[j]]}");
                        ans += hashCnt[actualHash[j]];
                    }
                    if (i + j >= S.Length) break;
                    actualHash[j] = actualHash[j] * b[1] + (S[i + j] - 'A' + 1) - (S[i] - 'A' + 1) * b[j]; 
                }
            }

            cw.WriteLine(ans);
        }
    }
}

#region Dependency resolution
namespace Roliha.Problems
{
    internal partial class ProblemA
    {
        static ConsoleReader cr;
        static ConsoleWriter cw;
#if COMPETITIVE
        public ProblemA(string outputFilePath = null, bool solving = true)
#else
        static void Main(string[] args)
#endif
        {
#if COMPETITIVE
            SourceExpander.Expander.Expand(outputFilePath: outputFilePath);
#endif
            if (cw != null)
                cw.Dispose();
            cr = new ConsoleReader();
            cw = new ConsoleWriter();
#if COMPETITIVE
            if (solving)
#endif
                Solve();
            cw.Dispose();
        }
    }
}
#endregion
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace AtCoder.Internal{public class Barrett{public readonly uint Mod;internal readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}[MethodImpl(256)]public uint Mul(uint a,uint b){var z=(ulong)a*b;if(Bmi2.X64.IsSupported){var x=Bmi2.X64.MultiplyNoFlags(z,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}return(uint)(z%Mod);}}}
namespace AtCoder.Internal{public static class InternalMath{private static readonly Dictionary<uint,int>primitiveRootsCache=new Dictionary<uint,int>(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};[MethodImpl(256)]public static int PrimitiveRoot<TMod>()where TMod:struct,IStaticMod{uint m=default(TMod).Mod;if(primitiveRootsCache.TryGetValue(m,out var p)){return p;}return primitiveRootsCache[m]=PrimitiveRootCalculate<TMod>();}static int PrimitiveRootCalculate<TMod>()where TMod:struct,IStaticMod{int m=(int)default(TMod).Mod;Span<int>divs=stackalloc int[20];divs[0]=2;int cnt=1;int x=(m-1)/2;while(x%2==0){x>>=1;}for(int i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;while(x%i==0){x/=i;}}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);for(int g=2;;g++){foreach(var d in divs)if(new StaticModInt<TMod>(g).Pow((m-1)/d).Value==1)goto NEXT;return g;NEXT:{}}}[MethodImpl(256)]public static(long,long)InvGCD(long a,long b){a=SafeMod(a,b);if(a==0)return(b,0);long s=b,t=a;long m0=0,m1=1;long u;while(true){if(t==0){if(m0<0)m0+=b/s;return(s,m0);}u=s/t;s-=t*u;m0-=m1*u;if(s==0){if(m1<0)m1+=b/t;return(t,m1);}u=t/s;t-=s*u;m1-=m0*u;}}[MethodImpl(256)]public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}[MethodImpl(256)]public static bool IsPrime(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long d=n-1;while(d%2==0)d/=2;ReadOnlySpan<byte>bases=stackalloc byte[3]{2,7,61};foreach(long a in bases){long t=d;long y=PowMod(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0){return false;}}return true;}[MethodImpl(256)]private static long PowMod(long x,long n,int m){if(m==1)return 0;Barrett barrett=new Barrett((uint)m);uint r=1,y=(uint)SafeMod(x,m);while(0<n){if((n&1)!=0)r=barrett.Mul(r,y);y=barrett.Mul(y,y);n>>=1;}return r;}[MethodImpl(256)]public static ulong FloorSumUnsigned(ulong n,ulong m,ulong a,ulong b){ulong ans=0;while(true){if(a>=m){ans+=(n-1)*n/2*(a/m);a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}ulong yMax=a*n+b;if(yMax<m)return ans;(n,m,a,b)=(yMax/m,a,m,yMax%m);}}}}
namespace AtCoder{public interface IStaticMod{uint Mod{get;}bool IsPrime{get;}}public readonly struct Mod1000000007:IStaticMod{public uint Mod=>1000000007;public bool IsPrime=>true;}public readonly struct Mod998244353:IStaticMod{public uint Mod=>998244353;public bool IsPrime=>true;}public readonly struct StaticModInt<T>:IEquatable<StaticModInt<T>>,IFormattable where T:struct,IStaticMod{internal readonly uint _v;private static readonly T op=default;public int Value=>(int)_v;public static int Mod=>(int)op.Mod;public static StaticModInt<T>Zero=>default;public static StaticModInt<T>One=>new StaticModInt<T>(1u);[MethodImpl(256)]public static StaticModInt<T>Raw(int v){var u=unchecked((uint)v);return new StaticModInt<T>(u);}[MethodImpl(256)]public StaticModInt(long v):this(Round(v)){}[MethodImpl(256)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[MethodImpl(256)]private StaticModInt(uint v)=>_v=v;[MethodImpl(256)]private static uint Round(long v){var x=v%op.Mod;if(x<0){x+=op.Mod;}return(uint)x;}[MethodImpl(256)]public static StaticModInt<T>operator ++(StaticModInt<T>v){var x=v._v+1;if(x==op.Mod){x=0;}return new StaticModInt<T>(x);}[MethodImpl(256)]public static StaticModInt<T>operator --(StaticModInt<T>v){var x=v._v;if(x==0){x=op.Mod;}return new StaticModInt<T>(x-1);}[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>lhs,StaticModInt<T>rhs){var v=lhs._v+rhs._v;if(v>=op.Mod){v-=op.Mod;}return new StaticModInt<T>(v);}[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>lhs,StaticModInt<T>rhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod){v+=op.Mod;}return new StaticModInt<T>(v);}}[MethodImpl(256)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs*rhs.Inv();[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>v)=>v;[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>v)=>new StaticModInt<T>(v._v==0?0:op.Mod-v._v);[MethodImpl(256)]public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;[MethodImpl(256)]public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;[MethodImpl(256)]public static implicit operator StaticModInt<T>(int v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(uint v)=>new StaticModInt<T>((long)v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(long v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(ulong v)=>new StaticModInt<T>(v);[MethodImpl(256)]public StaticModInt<T>Pow(long n){var x=this;var r=new StaticModInt<T>(1U);while(n>0){if((n&1)>0){r*=x;}x*=x;n>>=1;}return r;}[MethodImpl(256)]public StaticModInt<T>Inv(){if(op.IsPrime){return Pow(op.Mod-2);}else{var(g,x)=InternalMath.InvGCD(_v,op.Mod);return new StaticModInt<T>(x);}}public override string ToString()=>_v.ToString();public string ToString(string format,IFormatProvider formatProvider)=>_v.ToString(format,formatProvider);public override bool Equals(object obj)=>obj is StaticModInt<T>m&&Equals(m);[MethodImpl(256)]public bool Equals(StaticModInt<T>other)=>_v==other._v;public override int GetHashCode()=>_v.GetHashCode();}}
namespace Kzrnm.Competitive.IO{using static Utf8Parser;using _R=ConsoleReader;using MI=System.Runtime.CompilerServices.MethodImplAttribute;public class ConsoleReader{internal const int BufSize=1<<12;internal readonly Stream input;internal readonly Encoding encoding;internal readonly byte[]buf;internal int pos;internal int len;[MI(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[MI(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[MI(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){this.input=input;this.encoding=encoding;buf=new byte[bufferSize];}[MI(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len<buf.Length)buf[buf.Length-1]=10;len+=numberOfBytes;}private void FillNextBuffer(){if((len=input.Read(buf,0,buf.Length))==0){buf[0]=10;len=1;}else if(len<buf.Length)buf[buf.Length-1]=10;pos=0;}[MI(256)]internal byte ReadByte(){if(pos>=len)FillNextBuffer();return buf[pos++];}[MI(256)]public T Read<T>(){if(typeof(T)==typeof(int))return(T)(object)Int();if(typeof(T)==typeof(uint))return(T)(object)UInt();if(typeof(T)==typeof(long))return(T)(object)Long();if(typeof(T)==typeof(ulong))return(T)(object)ULong();if(typeof(T)==typeof(double))return(T)(object)Double();if(typeof(T)==typeof(decimal))return(T)(object)Decimal();if(typeof(T)==typeof(char))return(T)(object)Char();if(typeof(T)==typeof(string))return(T)(object)Ascii();return Throw<T>();}static T Throw<T>()=>throw new NotSupportedException(typeof(T).Name);[MI(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[MI(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[MI(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[MI(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[MI(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[MI(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}[MI(256)]public string String(){var sb=new List<byte>();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '<b);return encoding.GetString(sb.ToArray());}[MI(256)]public string Ascii(){var sb=new StringBuilder();byte b;do b=ReadByte();while(b<=' ');do{sb.Append((char)b);b=ReadByte();}while(' '<b);return sb.ToString();}[MI(256)]public string Line(){var sb=new List<byte>();byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}[MI(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[MI(256)]public int Int0()=>Int()-1;[MI(256)]public uint UInt0()=>UInt()-1;[MI(256)]public long Long0()=>Long()-1;[MI(256)]public ulong ULong0()=>ULong()-1;[MI(256)]public static implicit operator int(_R cr)=>cr.Int();[MI(256)]public static implicit operator uint(_R cr)=>cr.UInt();[MI(256)]public static implicit operator long(_R cr)=>cr.Long();[MI(256)]public static implicit operator ulong(_R cr)=>cr.ULong();[MI(256)]public static implicit operator double(_R cr)=>cr.Double();[MI(256)]public static implicit operator decimal(_R cr)=>cr.Decimal();[MI(256)]public static implicit operator string(_R cr)=>cr.Ascii();public T[]Repeat<T>(int count){var arr=new T[count];for(int i=0;i<arr.Length;i++)arr[i]=Read<T>();return arr;}}}
namespace Kzrnm.Competitive.IO{using _W=ConsoleWriter;using MI=System.Runtime.CompilerServices.MethodImplAttribute;public sealed partial class ConsoleWriter:IDisposable{private const int BufSize=1<<12;private readonly StreamWriter sw;public StreamWriter StreamWriter=>sw;public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,BufSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){sw=new StreamWriter(output,encoding,bufferSize);}[MI(256)]public void Flush()=>sw.Flush();[MI(256)]public void Dispose()=>Flush();[MI(256)]public _W Write<T>(T v){sw.Write(v.ToString());return this;}[MI(256)]public _W WriteLine(){sw.WriteLine();return this;}[MI(256)]public _W WriteLine<T>(T v){sw.WriteLine(v.ToString());return this;}[MI(256)]public _W WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);[MI(256)]public _W WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);[MI(256)]public _W WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);[MI(256)]public _W WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);[MI(256)]public _W WriteLineJoin<TTuple>(TTuple tuple)where TTuple:System.Runtime.CompilerServices.ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}[MI(256)]public _W WriteLineJoin(params object[]col)=>WriteMany(' ',col);[MI(256)]public _W WriteLineJoin<T1,T2>(T1 v1,T2 v2){sw.Write(v1.ToString());sw.Write(' ');sw.WriteLine(v2.ToString());return this;}[MI(256)]public _W WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){sw.Write(v1.ToString());sw.Write(' ');sw.Write(v2.ToString());sw.Write(' ');sw.WriteLine(v3.ToString());return this;}[MI(256)]public _W WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){sw.Write(v1.ToString());sw.Write(' ');sw.Write(v2.ToString());sw.Write(' ');sw.Write(v3.ToString());sw.Write(' ');sw.WriteLine(v4.ToString());return this;}[MI(256)]public _W WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);[MI(256)]public _W WriteGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[MI(256)]public _W WriteGrid<TTuple>(IEnumerable<TTuple>tuples)where TTuple:System.Runtime.CompilerServices.ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[MI(256)]private _W WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;sw.Write(en.Current.ToString());while(en.MoveNext()){sw.Write(sep);sw.Write(en.Current.ToString());}End:sw.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{using MI=System.Runtime.CompilerServices.MethodImplAttribute;public partial class ConsoleWriter{[MI(256)]public ConsoleWriter WriteLine(ReadOnlySpan<char>v){sw.WriteLine(v);return this;}[MI(256)]public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[MI(256)]public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);[MI(256)]public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[MI(256)]public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);[MI(256)]private ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;sw.Write(en.Current.ToString());while(en.MoveNext()){sw.Write(sep);sw.Write(en.Current.ToString());}sw.WriteLine();return this;}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
0