#487692 (C#(csc)) No.1307 Rotate and Accumulate

提出ソース

結果

問題	No.1307 Rotate and Accumulate
ユーザー	keymoon
提出日時	2020-05-28 15:28:20
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	1,101 ms / 5,000 ms
コード長	6,066 bytes
コンパイル時間	4,113 ms
コンパイル使用メモリ	117,516 KB
実行使用メモリ	64,540 KB
最終ジャッジ日時	2024-09-14 08:46:10
合計ジャッジ時間	13,064 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	37 ms 27,188 KB
testcase_01	AC	37 ms 27,316 KB
testcase_02	AC	37 ms 25,144 KB
testcase_03	AC	38 ms 25,272 KB
testcase_04	AC	38 ms 25,268 KB
testcase_05	AC	37 ms 25,400 KB
testcase_06	AC	37 ms 27,484 KB
testcase_07	AC	38 ms 27,344 KB
testcase_08	AC	1,013 ms 49,996 KB
testcase_09	AC	1,023 ms 51,520 KB
testcase_10	AC	570 ms 48,104 KB
testcase_11	AC	531 ms 47,568 KB
testcase_12	AC	567 ms 47,140 KB
testcase_13	AC	117 ms 33,896 KB
testcase_14	AC	294 ms 41,968 KB
testcase_15	AC	1,101 ms 62,616 KB
testcase_16	AC	1,098 ms 64,412 KB
testcase_17	AC	1,098 ms 62,720 KB
testcase_18	AC	961 ms 54,364 KB
testcase_19	AC	1,041 ms 64,536 KB
testcase_20	AC	985 ms 64,540 KB
testcase_21	AC	38 ms 27,336 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    public static void Main()
    {
        var mod1 = 998244353;
        ModInt.Mod = mod1;
        var nq = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var n = nq[0];
        var q = nq[1];
        var a = Console.ReadLine().Split().Select(x => new ModInt(int.Parse(x))).ToArray();
        var b = new ModInt[n];
        foreach (var item in Console.ReadLine().Split().Select(int.Parse).ToArray())
        {
            b[item == 0 ? 0 : n - item] += 1;
        }
        ModInt.Mod = mod1;
        var res1 = NumberTheoreticTransform.Convolute(a, b);
        var mod2 = 469762049;
        ModInt.Mod = mod2;
        var res2 = NumberTheoreticTransform.Convolute(a, b);

        var inv = 1 / new ModInt(mod1);
        var fftres = res1.Zip(res2, (x, y) => (long)(((int)y - (int)x) * inv) * mod1 + (int)x).ToArray();
        long[] res = new long[n];
        for (int i = 0; i < n; i++)
        {
            long item = 0;
            if (i < fftres.Length) item += fftres[i];
            if (n + i < fftres.Length) item += fftres[n + i];
            res[i] = item;
        }

        Console.WriteLine(string.Join(" ", res));
    }


    static long ExtGCD(long a, long b, out long x, out long y)
    {
        long div;
        long x1 = 1, y1 = 0, x2 = 0, y2 = 1;
        while (true)
        {
            if (b == 0) { x = x1; y = y1; return a; }
            div = a / b; x1 -= x2 * div; y1 -= y2 * div; a %= b;
            if (a == 0) { x = x2; y = y2; return b; }
            div = b / a; x2 -= x1 * div; y2 -= y1 * div; b %= a;
        }
    }
}

class NumberTheoreticTransform
{
    const int primitive_root = 3;
    static NumberTheoreticTransform() { }
    public static ModInt[] Convolute(ModInt[] A, ModInt[] B)
    {
        int sz = A.Length + B.Length - 1;
        int N = 1; while (N < sz) N <<= 1;

        var G = new ModInt[N];
        Array.Copy(A, G, A.Length);
        var H = new ModInt[N];
        Array.Copy(B, H, B.Length);

        NTT(G); NTT(H);
        for (int i = 0; i < N; i++) G[i] *= H[i];
        NTT(G, -1);

        Array.Resize(ref G, sz);
        return G;
    }
    static void NTT(ModInt[] F, int rev = 1)
    {
        int N = F.Length;

        ModInt h = ModInt.Pow(primitive_root, (ModInt.Mod - 1) / N);
        if (rev == -1) h = 1 / h;
        for (int i = 0, j = 1; j < N - 1; j++)
        {
            for (int k = N >> 1; k > (i ^= k); k >>= 1) ;
            if (j < i)
            {
                var tmp = F[i];
                F[i] = F[j];
                F[j] = tmp;
            }
        }

        for (int i = 2; i <= N; i <<= 1)
        {
            int m = i >> 1;
            // zeta = exp(rev * PI / m * i)
            ModInt zeta = ModInt.Pow(h, N / i);

            for (int j = 0; j < N; j += i)
            {
                ModInt zeta_pow = 1;
                for (int u = j, v = j + m; v < j + i; u++, v++)
                {
                    ModInt vl = F[u], vr = zeta_pow * F[v];
                    F[u] = vl + vr;
                    F[v] = vl - vr;
                    zeta_pow = zeta_pow * zeta;
                }
            }
        }

        if (rev == -1)
        {
            ModInt n_inv = (ModInt)1 / N;
            for (int i = 0; i < F.Length; i++)
            {
                F[i] *= n_inv;
            }
        }
    }
}


struct ModInt
{
    public static int mod;
    public static int Mod
    {
        get { return mod; }
        set { POSITIVIZER = ((long)value) << 31; mod = value; }
    }

    static long POSITIVIZER;
    long Data;
    public ModInt(long data) { if ((Data = data % Mod) < 0) Data += Mod; }
    public static implicit operator long(ModInt modInt) => modInt.Data;
    public static implicit operator ModInt(long val) => new ModInt(val);
    public static ModInt operator +(ModInt a, int b) => new ModInt() { Data = (a.Data + b + POSITIVIZER) % Mod };
    public static ModInt operator +(ModInt a, long b) => new ModInt(a.Data + b);
    public static ModInt operator +(ModInt a, ModInt b) { long res = a.Data + b.Data; return new ModInt() { Data = res >= Mod ? res - Mod : res }; }
    public static ModInt operator -(ModInt a, int b) => new ModInt() { Data = (a.Data - b + POSITIVIZER) % Mod };
    public static ModInt operator -(ModInt a, long b) => new ModInt(a.Data - b);
    public static ModInt operator -(ModInt a, ModInt b) { long res = a.Data - b.Data; return new ModInt() { Data = res < 0 ? res + Mod : res }; }
    public static ModInt operator *(ModInt a, int b) => new ModInt(a.Data * b);
    public static ModInt operator *(ModInt a, long b) => a * new ModInt(b);
    public static ModInt operator *(ModInt a, ModInt b) => new ModInt() { Data = a.Data * b.Data % Mod };
    public static ModInt operator /(ModInt a, ModInt b) => new ModInt() { Data = a.Data * GetInverse(b) % Mod };
    public static bool operator ==(ModInt a, ModInt b) => a.Data == b.Data;
    public static bool operator !=(ModInt a, ModInt b) => a.Data != b.Data;
    public override string ToString() => Data.ToString();
    public override bool Equals(object obj) => (ModInt)obj == this;
    public override int GetHashCode() => (int)Data;
    static long GetInverse(long a)
    {
        long div, p = Mod, x1 = 1, y1 = 0, x2 = 0, y2 = 1;
        while (true)
        {
            if (p == 1) return x2 + Mod; div = a / p; x1 -= x2 * div; y1 -= y2 * div; a %= p;
            if (a == 1) return x1 + Mod; div = p / a; x2 -= x1 * div; y2 -= y1 * div; p %= a;
        }
    }


    public static ModInt Pow(ModInt n, long m)
    {
        ModInt pow = n;
        ModInt res = 1;
        while (m > 0)
        {
            if ((m & 1) == 1) res *= pow;
            pow *= pow;
            m >>= 1;
        }
        return res;
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード