結果

問題 No.1905 PURE PHRASE
ユーザー 👑 kakel-sankakel-san
提出日時 2023-11-18 09:25:12
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 14,115 bytes
コンパイル時間 7,915 ms
コンパイル使用メモリ 158,600 KB
実行使用メモリ 196,388 KB
最終ジャッジ日時 2023-11-18 09:25:29
合計ジャッジ時間 15,503 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 117 ms
47,524 KB
testcase_01 AC 116 ms
47,524 KB
testcase_02 AC 124 ms
47,524 KB
testcase_03 AC 118 ms
47,524 KB
testcase_04 AC 119 ms
47,524 KB
testcase_05 AC 118 ms
47,524 KB
testcase_06 AC 117 ms
47,524 KB
testcase_07 AC 114 ms
47,524 KB
testcase_08 AC 116 ms
47,524 KB
testcase_09 AC 115 ms
47,524 KB
testcase_10 AC 116 ms
47,524 KB
testcase_11 AC 117 ms
47,524 KB
testcase_12 AC 123 ms
47,524 KB
testcase_13 AC 117 ms
47,524 KB
testcase_14 AC 116 ms
47,524 KB
testcase_15 AC 117 ms
47,524 KB
testcase_16 AC 117 ms
47,524 KB
testcase_17 AC 119 ms
47,524 KB
testcase_18 AC 118 ms
47,524 KB
testcase_19 AC 119 ms
47,524 KB
testcase_20 AC 117 ms
47,524 KB
testcase_21 AC 123 ms
47,524 KB
testcase_22 AC 117 ms
47,524 KB
testcase_23 AC 117 ms
47,524 KB
testcase_24 AC 117 ms
47,524 KB
testcase_25 AC 117 ms
47,524 KB
testcase_26 AC 118 ms
47,524 KB
testcase_27 AC 117 ms
47,524 KB
testcase_28 AC 118 ms
47,524 KB
testcase_29 AC 116 ms
47,524 KB
testcase_30 AC 125 ms
47,524 KB
testcase_31 AC 116 ms
47,524 KB
testcase_32 AC 115 ms
47,524 KB
testcase_33 AC 116 ms
47,524 KB
testcase_34 AC 118 ms
47,524 KB
testcase_35 AC 117 ms
47,524 KB
testcase_36 AC 117 ms
47,524 KB
testcase_37 AC 116 ms
47,524 KB
testcase_38 AC 116 ms
47,524 KB
testcase_39 AC 123 ms
47,524 KB
testcase_40 AC 117 ms
196,388 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (115 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
  main -> /home/judge/data/code/bin/Release/net7.0/main.dll
  main -> /home/judge/data/code/bin/Release/net7.0/publish/

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static double[] NList => ReadLine().Split().Select(double.Parse).ToArray();
    public static void Main()
    {
        Solve();
        // Test();
        // Test2();
    }
    static void Test()
    {
        var n = NN;
        var a = NList;
        for (var i = 0; i < a.Length; ++i) a[i] *= 0.54 - 0.46 * Math.Cos(2 * Math.PI * i / (n - 1));
        var fft = FFT.Calc2(a);
        WriteLine(string.Join("\n", fft));
        // WriteLine(string.Join("\n", a));
    }
    static void Test2()
    {
        var f = 100;
        var fs = 1000;
        var n = 64;
        var t = new double[n];
        for (var i = 0; i < t.Length; ++i) t[i] = (double)i / fs;
        var signal = new double[n];
        for (var i = 0; i < signal.Length; ++i) signal[i] = Math.Sin(2 * Math.PI * f * t[i]);
        var window = new double[n];
        for (var i = 0; i < window.Length; ++i) window[i] = 0.54 - 0.46 * Math.Cos(2 * Math.PI * i / (n - 1));
        var a = new double[n];
        for (var i = 0; i < a.Length; ++i) a[i] = signal[i] * window[i];
        var fft = FFT.Calc2(a);
        WriteLine(string.Join("\n", fft));
        // WriteLine(string.Join("\n", signal));
        // WriteLine(string.Join("\n", window));
    }
    static void Solve()
    {
        var n = NN;
        var a = NList;
        for (var i = 0; i < a.Length; ++i) a[i] *= 0.54 - 0.46 * Math.Cos(2 * Math.PI * i / (n - 1));
        var f = FFT.Calc2(a);
        var w = new double[] { 261.6, 294.3, 327, 348.8, 392.4, 436, 490.5 };
        var s = new string[] { "C4", "D4", "E4", "F4", "G4", "A4", "B4" };
        var maxr = 0.0;
        var ans = "";
        for (var i = 0; i < w.Length; ++i)
        {
            // var pos = (int)(44100 / w[i]);
            var pos = (int)w[i];
            // WriteLine($"f[{pos}] = {f[pos]} ({f[pos].Magnitude})");
            if (maxr < Math.Abs(f[pos].Magnitude))
            {
                maxr = Math.Abs(f[pos].Magnitude);
                ans = s[i];
            }
        }
        WriteLine(ans);
    }
    class FFT
    {
        public static System.Numerics.Complex[] DFT(int[] a)
        {
            var xi = new System.Numerics.Complex[a.Length];
            for (var i = 0; i < xi.Length; ++i) xi[i] = new System.Numerics.Complex(Math.Cos(i * 2 * Math.PI / xi.Length), Math.Sin(i * 2 * Math.PI / xi.Length));
            var ans = new System.Numerics.Complex[a.Length];
            for (var i = 0; i < a.Length; ++i) for (var j = 0; j < a.Length; ++j)
            {
                ans[i] += a[j] * xi[i * j % xi.Length];
            }
            return ans;
        }
        public static System.Numerics.Complex[] Calc(int[] a)
        {
            if (a.Length == 0) return new System.Numerics.Complex[0];
            var len = 1;
            while (len < a.Length) len <<= 1;
            var c = new int[len];
            Array.Copy(a, c, a.Length);
            var dp = new System.Numerics.Complex[len];
            var xi = new System.Numerics.Complex[len];
            for (var i = 0; i < xi.Length; ++i) xi[i] = new System.Numerics.Complex(Math.Cos(i * 2 * Math.PI / len), Math.Sin(i * 2 * Math.PI / len));
            _Calc(dp, xi, c);
            return dp;
        }
        static void _Calc(System.Numerics.Complex[] dp, System.Numerics.Complex[] xi, int[] c)
        {
            if (dp.Length == 1)
            {
                dp[0] = c[0];
                return;
            }
            var len = dp.Length / 2;
            var dp0 = new System.Numerics.Complex[len];
            var dp1 = new System.Numerics.Complex[len];
            var c0 = new int[len];
            var c1 = new int[len];
            var x0 = new System.Numerics.Complex[len];
            for (var i = 0; i < len; ++i)
            {
                c0[i] = c[i * 2];
                c1[i] = c[i * 2 + 1];
                x0[i] = xi[i * 2];
            }
            _Calc(dp0, x0, c0);
            _Calc(dp1, x0, c1);
            for (var i = 0; i < dp.Length; ++i)
            {
                dp[i] = dp0[i % len] + xi[i] * dp1[i % len];
            }
        }
        public static System.Numerics.Complex[] Calc2(double[] a)
        {
            if (a.Length == 0) return new System.Numerics.Complex[0];
            var dp = new System.Numerics.Complex[a.Length];
            for (var i = 0; i < a.Length; ++i) dp[i] = a[i];
            _Calc2(dp);
            return dp;
        }
        static void _Calc2(System.Numerics.Complex[] dp)
        {
            if (dp.Length == 1) return;
            var len = dp.Length / 2;
            var dp0 = new System.Numerics.Complex[len];
            var dp1 = new System.Numerics.Complex[len];
            for (var i = 0; i < len; ++i)
            {
                dp0[i] = dp[i * 2];
                dp1[i] = dp[i * 2 + 1];
            }
            _Calc2(dp0);
            _Calc2(dp1);
            var now = new System.Numerics.Complex(1, 0);
            var zeta = new System.Numerics.Complex(Math.Cos(2 * Math.PI / dp.Length), Math.Sin(2 * Math.PI / dp.Length));
            for (var i = 0; i < dp.Length; ++i)
            {
                dp[i] = dp0[i % len] + now * dp1[i % len];
                now *= zeta;
            }
        }
    }
    // 畳み込みを mod で計算する
    class ConvolutionCalculator
    {
        int mod;
        public ConvolutionCalculator(int mod)
        {
            this.mod = mod;
        }
        public int[] Calc(long[] a, long[] b)
        {
            var _a = new int[a.Length];
            var _b = new int[b.Length];
            for (var i = 0; i < a.Length; ++i) _a[i] = (int)(a[i] % mod);
            for (var i = 0; i < b.Length; ++i) _b[i] = (int)(b[i] % mod);
            return Calc(_a, _b);
        }
        public int[] Calc(int[] a, int[] b)
        {
            var n = a.Length;
            var m = b.Length;
            if (n == 0 || m == 0)
            {
                return new int[0];
            }
            if (Math.Min(n, m) <= 100)
            {
                return ShortComvolution(a, b);
            }
            var z = 1 << CeilPow(n + m - 1);
            var za = new int[z];
            var zb = new int[z];
            Array.Copy(a, za, a.Length);
            Array.Copy(b, zb, b.Length);
            InitButterfly();
            Butterfly(za);
            Butterfly(zb);
            for (var i = 0; i < z; ++i)
            {
                za[i] = (int)((long)za[i] * zb[i] % mod);
            }
            ButterflyInv(za);
            var iz = PowMod(z, mod - 2, mod);
            var ans = new int[n + m - 1];
            for (var i = 0; i < ans.Length; ++i)
            {
                ans[i] = (int)((long)za[i] * iz % mod);
            }
            return ans;
        }
        int[] ShortComvolution(int[] a, int[] b)
        {
            var ans = new int[a.Length + b.Length - 1];
            for (var i = 0; i < a.Length; ++i)
            {
                for (var j = 0; j < b.Length; ++j)
                {
                    ans[i + j] = (int)((ans[i + j] + (long)a[i] * b[j] % mod) % mod);
                }
            }
            return ans;
        }
        int[] sume = new int[30];
        int[] sumie = new int[30];
        void InitButterfly()
        {
            var g = PrimitiveRoot(mod);
            var es = new int[30];
            var ies = new int[30];
            var cnt2 = BSF(mod - 1);
            var e = PowMod(g, mod - 1 >> cnt2, mod);
            var ie = PowMod(e, mod - 2, mod);
            for (var i = cnt2; i >= 2; --i)
            {
                es[i - 2] = e;
                ies[i - 2] = ie;
                e = (int)((long)e * e % mod);
                ie = (int)((long)ie * ie % mod);
            }
            var now = 1L;
            var inow = 1L;
            for (var i = 0; i < cnt2 - 2; ++i)
            {
                sume[i] = (int)(es[i] * now % mod);
                now = now * ies[i] % mod;
                sumie[i] = (int)(ies[i] * inow % mod);
                inow = inow * es[i] % mod;
            }
        }

        void Butterfly(int[] a)
        {
            var h = CeilPow(a.Length);

            for (var ph = 1; ph <= h; ++ph)
            {
                var w = 1 << (ph - 1);
                var p = 1 << (h - ph);
                var now = 1L;
                for (var s = 0; s < w; ++s)
                {
                    var offset = s << (h - ph + 1);
                    for (var i = 0; i < p; ++i)
                    {
                        var l = a[i + offset];
                        var r = (int)(a[i + offset + p] * now % mod);
                        a[i + offset] = (l + r) % mod;
                        a[i + offset + p] = (int)((long)mod + l - r) % mod;
                    }
                    now = now * sume[BSF(~(uint)s)] % mod;
                }
            }
        }
        void ButterflyInv(int[] a)
        {
            var h = CeilPow(a.Length);

            for (var ph = h; ph >= 1; --ph)
            {
                var w = 1 << (ph - 1);
                var p = 1 << (h - ph);
                var inow = 1L;
                for (var s = 0; s < w; ++s)
                {
                    var offset = s << (h - ph + 1);
                    for (var i = 0; i < p; ++i)
                    {
                        var l = a[i + offset];
                        var r = a[i + offset + p];
                        a[i + offset] = (l + r) % mod;
                        a[i + offset + p] = (int)(((long)mod + l - r) * inow % mod);
                    }
                    inow = inow * sumie[BSF(~(uint)s)] % mod;
                }
            }
        }
        static int PowMod(int n, int p, int mod)
        {
            long _n = n % mod;
            var _p = p;
            var result = 1L;
            if ((_p & 1) == 1)
            {
                result *= _n;
            }
            while (_p > 0)
            {
                _n = _n * _n % mod;
                _p >>= 1;
                if ((_p & 1) == 1)
                {
                    result = (result * _n) % mod;
                }
            }
            return (int)result;
        }
        static int PrimitiveRoot(int m)
        {
            if (m == 2) return 1;
            if (m == 167772161) return 3;
            if (m == 469762049) return 3;
            if (m == 754974721) return 11;
            if (m == 998244353) return 3;
            if (m == 1000000007) return 5;
            var divs = new int[20];
            divs[0] = 2;
            var cnt = 1;
            var x = (m - 1) / 2;
            while (x % 2 == 0) x /= 2;
            for (var i = 3; (long)i * i <= x; i += 2)
            {
                if (x % i == 0)
                {
                    divs[cnt++] = i;
                    while (x % i == 0) x /= i;
                }
            }
            if (x > 1) divs[cnt++] = x;
            for (var g = 2;; ++g)
            {
                var ok = true;
                for (var i = 0; i < cnt; ++i)
                {
                    if (PowMod(g, (m - 1) / divs[i], m) == 1)
                    {
                        ok = false;
                        break;
                    }
                }
                if (ok) return g;
            }
        }
        static int CeilPow(int n)
        {
            var x = 0;
            while ((1U << x) < (uint)n) x++;
            return x;
        }
        static int BSF(int n)
        {
            if (n == 0) return 0;
            var count = 0;
            while ((n & 1) == 0)
            {
                ++count;
                n >>= 1;
            }
            return count;
        }
        static int BSF(uint n)
        {
            if (n == 0) return 0;
            var count = 0;
            while ((n & 1) == 0)
            {
                ++count;
                n >>= 1;
            }
            return count;
        }
        public long[] ConvolutionLL(long[] a, long[] b)
        {
            if (a.Length == 0 && b.Length == 0) return new long[0];
            const ulong MOD1 = 754_974_721;
            const ulong MOD2 = 167_772_161;
            const ulong MOD3 = 469_762_049;
            const ulong M2M3 = 78_812_994_116_517_889;
            const ulong M1M3 = 354_658_471_880_163_329;
            const ulong M1M2 = 126_663_740_442_542_081;
            const ulong M1M2M3 = 560_135_205_046_714_369;
            const ulong i1 = 190_329_765;
            const ulong i2 = 58_587_104;
            const ulong i3 = 187_290_749;
            ulong[] offset = new ulong[] { 0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3 };
            var c1 = new ConvolutionCalculator((int)MOD1).Calc(a, b);
            var c2 = new ConvolutionCalculator((int)MOD2).Calc(a, b);
            var c3 = new ConvolutionCalculator((int)MOD3).Calc(a, b);
            var ans = new long[a.Length + b.Length - 1];
            for (var i = 0; i < ans.Length; ++i)
            {
                ulong x = 0;
                x += (ulong)c1[i] * i1 % MOD1 * M2M3;
                x += (ulong)c2[i] * i2 % MOD2 * M1M3;
                x += (ulong)c3[i] * i3 % MOD3 * M1M2;
                var diff = c1[i] - SafeMod((long)x, (long)MOD1);
                if (diff < 0) diff += (long)MOD1;
                x -= offset[diff % 5];
                ans[i] = (long)x;
            }
            return ans;
        }
        static long SafeMod(long a, long b)
        {
            a %= b;
            if (a < 0) a += b;
            return a;
        }
    }
}
0