結果

問題 No.1307 Rotate and Accumulate
ユーザー さかぽんさかぽん
提出日時 2021-02-22 09:55:10
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,281 ms / 5,000 ms
コード長 2,393 bytes
コンパイル時間 3,702 ms
コンパイル使用メモリ 111,320 KB
実行使用メモリ 76,188 KB
最終ジャッジ日時 2023-10-21 06:28:22
合計ジャッジ時間 17,757 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
25,604 KB
testcase_01 AC 35 ms
25,608 KB
testcase_02 AC 35 ms
25,608 KB
testcase_03 AC 35 ms
25,612 KB
testcase_04 AC 35 ms
25,600 KB
testcase_05 AC 35 ms
25,596 KB
testcase_06 AC 35 ms
25,612 KB
testcase_07 AC 35 ms
25,624 KB
testcase_08 AC 589 ms
60,024 KB
testcase_09 AC 602 ms
59,032 KB
testcase_10 AC 612 ms
59,196 KB
testcase_11 AC 568 ms
59,788 KB
testcase_12 AC 603 ms
59,204 KB
testcase_13 AC 118 ms
41,680 KB
testcase_14 AC 300 ms
52,560 KB
testcase_15 AC 1,249 ms
76,188 KB
testcase_16 AC 1,243 ms
76,188 KB
testcase_17 AC 1,260 ms
76,124 KB
testcase_18 AC 1,224 ms
75,852 KB
testcase_19 AC 1,281 ms
75,996 KB
testcase_20 AC 1,281 ms
76,060 KB
testcase_21 AC 35 ms
25,536 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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);
	}
}
0