結果

問題 No.1307 Rotate and Accumulate
ユーザー さかぽん
提出日時 2021-02-22 09:55:10
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,267 ms / 5,000 ms
コード長 2,393 bytes
コンパイル時間 3,667 ms
コンパイル使用メモリ 116,156 KB
実行使用メモリ 78,836 KB
最終ジャッジ日時 2024-09-21 07:37:48
合計ジャッジ時間 17,046 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
プレゼンテーションモードにする

using System;
using System.Linq;
class D
{
static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
static (int, int) Read2() { var a = Read(); return (a[0], a[1]); }
static long[] ReadL() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
static void Main()
{
var (n, q) = Read2();
var a = ReadL();
var r = Read();
a = a.Concat(a).ToArray();
var b = Tally(r, n - 1);
Array.Reverse(b);
var c = Ntt.Convolution(a, b);
Console.WriteLine(string.Join(" ", c[(n - 1)..(2 * n - 1)]));
}
static long[] Tally(int[] a, int max)
{
var c = new long[max + 1];
foreach (var x in a) ++c[x];
return c;
}
}
public class Ntt
{
//const long p = 469762049, g = 3;
//const long p = 754974721, g = 11;
//const long p = 1004535809, g = 3;
const long p = 998244353, g = 3;
public static int ToPowerOf2(int length)
{
var n = 1;
while (n < length) n <<= 1;
return n;
}
static long MPow(long b, long i)
{
long r = 1;
for (; i != 0; b = b * b % p, i >>= 1) if ((i & 1) != 0) r = r * b % p;
return r;
}
static long[] NthRoots(int n)
{
var w = MPow(g, (p - 1) / n);
var r = new long[n + 1];
r[0] = 1;
for (int i = 0; i < n; ++i) r[i + 1] = r[i] * w % p;
return r;
}
int n;
long nInv;
long[] roots;
public Ntt(int length)
{
n = ToPowerOf2(length);
nInv = MPow(n, p - 2);
roots = NthRoots(n);
}
void FftInternal(long[] c, bool inverse)
{
var m = c.Length;
if (m == 1) return;
var m2 = m / 2;
var nm = n / m;
var c1 = new long[m2];
var c2 = new long[m2];
for (int i = 0; i < m2; ++i)
{
c1[i] = c[2 * i];
c2[i] = c[2 * i + 1];
}
FftInternal(c1, inverse);
FftInternal(c2, inverse);
for (int i = 0; i < m2; ++i)
{
var z = c2[i] * roots[nm * (inverse ? m - i : i)] % p;
c[i] = (c1[i] + z) % p;
c[m2 + i] = (c1[i] - z + p) % p;
}
}
// { f(w^i) }
// n OK
public long[] Fft(long[] c, bool inverse = false)
{
var r = new long[n];
c.CopyTo(r, 0);
FftInternal(r, inverse);
if (inverse) for (int i = 0; i < n; ++i) r[i] = r[i] * nInv % p;
return r;
}
// n OK
public static long[] Convolution(long[] a, long[] b)
{
var ntt = new Ntt(a.Length + b.Length - 1);
var fa = ntt.Fft(a);
var fb = ntt.Fft(b);
for (int i = 0; i < ntt.n; ++i) fa[i] = fa[i] * fb[i] % p;
return ntt.Fft(fa, true);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0