結果
| 問題 |
No.3082 Make Palindromic Multiple(Judge)
|
| ユーザー |
 KumaTachiRen
|
| 提出日時 | 2025-03-28 22:06:10 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,743 ms / 3,500 ms |
| コード長 | 14,734 bytes |
| コンパイル時間 | 7,396 ms |
| コンパイル使用メモリ | 167,140 KB |
| 実行使用メモリ | 186,432 KB |
| 最終ジャッジ日時 | 2025-04-16 13:12:11 |
| 合計ジャッジ時間 | 22,560 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 73 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (94 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using Lib;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static Lib.OutputLib;
public class Solver
{
const bool MultiTestCase = false;
void Solve()
{
var ps_all = new long[] { 999985249, 999985309, 999985313, 999985351, 999985379, 999985387, 999985391, 999985403, 999985423, 999985451, 999985471, 999985501, 999985517, 999985537, 999985541, 999985549, 999985589, 999985601, 999985607, 999985619, 999985639, 999985661, 999985667, 999985669, 999985673, 999985733, 999985741, 999985837, 999985913, 999985949, 999985957, 999985967, 999985969, 999986041, 999986051, 999986059, 999986069, 999986089, 999986101, 999986107, 999986123, 999986129, 999986137, 999986159, 999986167, 999986171, 999986173, 999986177, 999986179, 999986219, 999986231, 999986261, 999986263, 999986279, 999986297, 999986303, 999986311, 999986333, 999986399, 999986411, 999986413, 999986419, 999986441, 999986501, 999986509, 999986513, 999986567, 999986599, 999986609, 999986627, 999986639, 999986641, 999986651, 999986681, 999986707, 999986719, 999986731, 999986783, 999986789, 999986839, 999986849, 999986857, 999986861, 999986863, 999986917, 999986921, 999986927, 999986957, 999986959, 999987041, 999987061, 999987097, 999987101, 999987103, 999987137, 999987143, 999987151, 999987211, 999987227, 999987281, 999987299, 999987301, 999987323, 999987337, 999987349, 999987371, 999987377, 999987389, 999987409, 999987421, 999987427, 999987433, 999987449, 999987467, 999987487, 999987497, 999987503, 999987601, 999987607, 999987631, 999987697, 999987743, 999987761, 999987763, 999987829, 999987847, 999987871, 999987881, 999987913, 999987929, 999987943, 999987983, 999988007, 999988013, 999988051, 999988079, 999988117, 999988133, 999988163, 999988201, 999988217, 999988219, 999988243, 999988261, 999988277, 999988279, 999988313, 999988321, 999988343, 999988357, 999988427, 999988447, 999988453, 999988459, 999988477, 999988499, 999988513, 999988519, 999988523, 999988541, 999988543, 999988547, 999988571, 999988589, 999988609, 999988679, 999988747, 999988757, 999988763, 999988813, 999988823, 999988831, 999988861, 999988877, 999988883, 999988901, 999988903, 999988919, 999988949, 999988961, 999988987, 999989017, 999989033, 999989069, 999989083, 999989087, 999989141, 999989143, 999989149, 999989161, 999989191, 999989201, 999989203, 999989219, 999989231, 999989257, 999989267, 999989293, 999989297, 999989299, 999989321, 999989327, 999989359, 999989371, 999989411, 999989429, 999989447, 999989461, 999989509, 999989519, 999989567, 999989647, 999989681, 999989689, 999989701, 999989717, 999989737, 999989777, 999989797, 999989801, 999989857, 999989863, 999989899, 999989957, 999989981, 999990011, 999990029, 999990071, 999990091, 999990097, 999990109, 999990143, 999990227, 999990239, 999990259, 999990289, 999990293, 999990301, 999990319, 999990347, 999990353, 999990359, 999990373, 999990419, 999990421, 999990461, 999990479, 999990517, 999990569, 999990571, 999990581, 999990583, 999990599, 999990631, 999990709, 999990763, 999990787, 999990809, 999990833, 999990841, 999990851, 999990853, 999990857, 999990869, 999990877, 999990911, 999990913, 999990923, 999990931, 999990947, 999990973, 999990977, 999990991, 999990997, 999991009, 999991037, 999991061, 999991063, 999991067, 999991081, 999991123, 999991133, 999991141, 999991151, 999991163, 999991207, 999991229, 999991231, 999991241, 999991277, 999991283, 999991301, 999991327, 999991331, 999991339, 999991351, 999991367, 999991373, 999991423, 999991441, 999991453, 999991463, 999991469, 999991507, 999991547, 999991571, 999991591, 999991627, 999991661, 999991669, 999991819, 999991829, 999991843, 999991847, 999991873, 999991919, 999991921, 999991973, 999992023, 999992029, 999992039, 999992057, 999992087, 999992099, 999992101, 999992107, 999992111, 999992129, 999992131, 999992153, 999992177, 999992209, 999992221, 999992263, 999992267, 999992281, 999992293, 999992339, 999992347, 999992359, 999992387, 999992407, 999992423, 999992447, 999992509, 999992527, 999992537, 999992573, 999992579, 999992639, 999992641, 999992647, 999992677, 999992723, 999992731, 999992737, 999992753, 999992759, 999992783, 999992837, 999992867, 999992891, 999992899, 999992927, 999992977, 999992999, 999993031, 999993041, 999993061, 999993067, 999993083, 999993119, 999993143, 999993179, 999993221, 999993229, 999993289, 999993311, 999993367, 999993377, 999993439, 999993461, 999993469, 999993481, 999993571, 999993581, 999993583, 999993623, 999993637, 999993641, 999993653, 999993671, 999993697, 999993707, 999993719, 999993721, 999993733, 999993739, 999993763, 999993791, 999993811, 999993817, 999993821, 999993823, 999993833, 999993851, 999993887, 999993899, 999993901, 999993913, 999993947, 999993971, 999994003, 999994007, 999994081, 999994091, 999994097, 999994123, 999994129, 999994157, 999994159, 999994189, 999994201, 999994241, 999994267, 999994273, 999994277, 999994297, 999994309, 999994313, 999994321, 999994337, 999994343, 999994357, 999994379, 999994381, 999994397, 999994423, 999994427, 999994433, 999994439, 999994487, 999994507, 999994531, 999994537, 999994549, 999994603, 999994609, 999994613, 999994649, 999994651, 999994691, 999994693, 999994703, 999994741, 999994747, 999994753, 999994763, 999994771, 999994781, 999994813, 999994823, 999994837, 999994843, 999994861, 999994867, 999994883, 999994903, 999994913, 999994951, 999994973, 999994979, 999994987, 999995093, 999995107, 999995111, 999995141, 999995239, 999995257, 999995261, 999995273, 999995291, 999995341, 999995377, 999995393, 999995413, 999995419, 999995431, 999995531, 999995561, 999995567, 999995599, 999995611, 999995621, 999995627, 999995629, 999995651, 999995663, 999995677, 999995681, 999995701, 999995713, 999995741, 999995749, 999995803, 999995809, 999995813, 999995819, 999995903, 999995911, 999995921, 999995959, 999995993, 999996007, 999996029, 999996031, 999996037, 999996043, 999996071, 999996073, 999996091, 999996113, 999996131, 999996149, 999996181, 999996199, 999996223, 999996227, 999996247, 999996259, 999996269, 999996301, 999996307, 999996311, 999996317, 999996329, 999996341, 999996359, 999996383, 999996407, 999996469, 999996493, 999996541, 999996587, 999996611, 999996643, 999996649, 999996671, 999996677, 999996689, 999996707, 999996709, 999996727, 999996749, 999996779, 999996827, 999996901, 999996913, 999996919, 999996983, 999996989, 999997021, 999997049, 999997067, 999997081, 999997099, 999997133, 999997181, 999997237, 999997241, 999997249, 999997267, 999997279, 999997301, 999997309, 999997331, 999997357, 999997403, 999997457, 999997489, 999997543, 999997561, 999997567, 999997571, 999997577, 999997589, 999997627, 999997639, 999997643, 999997673, 999997679, 999997697, 999997717, 999997769, 999997771, 999997787, 999997793, 999997811, 999997871, 999997891, 999997967, 999998003, 999998017, 999998023, 999998059, 999998081, 999998107, 999998119, 999998137, 999998141, 999998143, 999998147, 999998173, 999998183, 999998203, 999998243, 999998261, 999998269, 999998309, 999998339, 999998369, 999998423, 999998459, 999998501, 999998507, 999998509, 999998533, 999998537, 999998563, 999998609, 999998617, 999998621, 999998627, 999998639, 999998641, 999998653, 999998663, 999998683, 999998687, 999998689, 999998693, 999998777, 999998789, 999998801, 999998843, 999998863, 999998869, 999998903, 999998917, 999998921, 999998929, 999998957, 999998959, 999998971, 999998981, 999999001, 999999017, 999999029, 999999043, 999999059, 999999067, 999999103, 999999107, 999999113, 999999131, 999999137, 999999151, 999999163, 999999181, 999999191, 999999193, 999999197, 999999223, 999999229, 999999323, 999999337, 999999353, 999999391, 999999433, 999999487, 999999491, 999999503, 999999527, 999999541, 999999587, 999999599, 999999607, 999999613, 999999667, 999999677, 999999733, 999999739, 999999751, 999999757, 999999761, 999999797, 999999883, 999999893, 999999929, 999999937 };
var ps = new long[3];
var rnd = new Random();
for (int i = 0; i < ps.Length; i++) ps[i] = rnd.Next(ps_all.Length - i);
for (int i = ps.Length - 1; i >= 0; i--)
for (int j = i + 1; j < ps.Length; j++)
if (ps[j] >= ps[i]) ps[j]++;
for (int i = 0; i < ps.Length; i++) ps[i] = ps_all[ps[i]];
int n = ri;
ReadArray(out (string s, long t)[] st, n, () => (rs, rl));
bool ans = true;
foreach (var p in ps)
{
long b = rnd.Next(10000) + 1000;
long hash = 0, rhash = 0;
long q = 1;
foreach (var (s, t) in st)
{
var bp = Pow(b, s.Length, p);
long h = 0, rh = 0;
for (int i = 0; i < s.Length; i++) h = (h * b + s[i]) % p;
for (int i = s.Length - 1; i >= 0; i--) rh = (rh * b + s[i]) % p;
long z = PowSum(bp, t, p);
h = h * z % p;
rh = rh * z % p;
var bpp = Pow(bp, t, p);
hash = (hash * bpp + h) % p;
rhash = (rhash + q * rh) % p;
q = q * bpp % p;
}
ans &= hash == rhash;
}
Yn(ans);
}
long Pow(long x, long n, long m)
{
long y = 1;
while (n > 0)
{
if (n % 2 == 1) y = y * x % m;
x = x * x % m;
n /= 2;
}
return y;
}
long PowSum(long x, long n, long m)
{
long p = 1;
long y = 0, z = 1;
while (n > 0)
{
if (n % 2 == 1)
{
y = (y + z * p) % m;
p = p * x % m;
}
z = z * (x + 1) % m;
x = x * x % m;
n /= 2;
}
return y;
}
#pragma warning disable CS0162, CS8618
public Solver() { if (!MultiTestCase) Solve(); else for (int t = ri; t > 0; t--) Solve(); }
#pragma warning restore CS0162, CS8618
const int IINF = 1 << 30;
const long INF = 1L << 60;
int ri { [MethodImpl(256)] get => (int)sc.Integer(); }
long rl { [MethodImpl(256)] get => sc.Integer(); }
uint rui { [MethodImpl(256)] get => (uint)sc.UInteger(); }
ulong rul { [MethodImpl(256)] get => sc.UInteger(); }
double rd { [MethodImpl(256)] get => sc.Double(); }
string rs { [MethodImpl(256)] get => sc.Scan(); }
string rline { [MethodImpl(256)] get => sc.Line(); }
public StreamScanner sc = new StreamScanner(Console.OpenStandardInput());
void ReadArray(out int[] a, int n) { a = new int[n]; for (int i = 0; i < a.Length; i++) a[i] = ri; }
void ReadArray(out long[] a, int n) { a = new long[n]; for (int i = 0; i < a.Length; i++) a[i] = rl; }
void ReadArray<T>(out T[] a, int n, Func<T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); }
void ReadArray<T>(out T[] a, int n, Func<int, T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(i); }
}
static class Program
{
static public void Main(string[] args)
{
SourceExpander.Expander.Expand();
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
new Solver();
Console.Out.Flush();
}
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace Lib{public partial class StreamScanner{public StreamScanner(Stream stream){str=stream;}private readonly Stream str;private readonly byte[]buf=new byte[1024];private int len,ptr;public bool isEof=false;public bool IsEndOfStream{get{return isEof;}}[MethodImpl(256)]private byte Read(){if(isEof)throw new EndOfStreamException();if(ptr>=len){ptr=0;if((len=str.Read(buf,0,1024))<=0){isEof=true;return 0;}}return buf[ptr++];}[MethodImpl(256)]public char Char(){byte b;do b=Read();while(b<33||126<b);return(char)b;}[MethodImpl(256)]public string Line(){var sb=new StringBuilder();for(var b=Char();b!=10&&!isEof;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public string Scan(){var sb=new StringBuilder();for(var b=Char();b>=33&&b<=126;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public long Integer(){long ret=0;var ng=false;byte b;do b=Read();while(b!='-'&&(b<'0'||'9'<b));if(b=='-'){ng=true;b=Read();}for(;'0'<=b&&b<='9';b=Read())ret=ret*10+(b^'0');return ng?-ret:ret;}[MethodImpl(256)]public ulong UInteger(){ulong ret=0;byte b;do b=Read();while(b<'0'||'9'<b);for(;'0'<=b&&b<='9';b=Read())ret=ret*10+(ulong)(b^'0');return ret;}[MethodImpl(256)]public double Double()=>double.Parse(Scan());}}
namespace Lib{public static class OutputLib{[MethodImpl(256)]public static void WriteJoin<T>(string s,IEnumerable<T>t)=>Console.WriteLine(string.Join(s,t));[MethodImpl(256)]public static void WriteMat<T>(T[,]a,string sep=" "){int sz1=a.GetLength(0),sz2=a.GetLength(1);var b=new T[sz2];for(int i=0;i<sz1;i++){for(int j=0;j<sz2;j++)b[j]=a[i,j];WriteJoin(sep,b);}}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,string sep=" "){foreach(var ar in a)WriteJoin(sep,ar);}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,Func<T,string>map,string sep=" "){foreach(var ar in a)WriteJoin(sep,ar.Select(x=>map(x)));}[MethodImpl(256)]public static void Write(object t)=>Console.WriteLine(t.ToString());[MethodImpl(256)]public static void Write(params object[]arg)=>Console.WriteLine(string.Join(" ",arg.Select(x=>x.ToString())));[MethodImpl(256)]public static void Write(string str)=>Console.WriteLine(str);[MethodImpl(256)]public static void WriteFlush(object t){Console.WriteLine(t.ToString());Console.Out.Flush();}[MethodImpl(256)]public static void WriteError(object t)=>Console.Error.WriteLine(t.ToString());[MethodImpl(256)]public static void Flush()=>Console.Out.Flush();[MethodImpl(256)]public static void YN(bool t)=>Console.WriteLine(t?"YES":"NO");[MethodImpl(256)]public static void Yn(bool t)=>Console.WriteLine(t?"Yes":"No");[MethodImpl(256)]public static void yn(bool t)=>Console.WriteLine(t?"yes":"no");[MethodImpl(256)]public static void DeleteLine()=>Console.Write("\x1b[1A\x1b[2K");[MethodImpl(256)]public static void ProgressBar(long now,long total,int blocks=50){int x=(int)((2*now*blocks+1)/(2*total));Console.Write($"\x1b[G[\x1b[42m{string.Concat(Enumerable.Repeat("_",x))}\x1b[0m{string.Concat(Enumerable.Repeat("_",blocks-x))}] : {now} / {total}");}}}
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