結果
問題 | 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.
ソースコード
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);}}