結果

問題 No.2770 Coupon Optimization
ユーザー kakel-sankakel-san
提出日時 2024-05-31 23:23:42
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 1,184 ms / 3,000 ms
コード長 8,889 bytes
コンパイル時間 8,425 ms
コンパイル使用メモリ 169,020 KB
実行使用メモリ 257,488 KB
最終ジャッジ日時 2024-05-31 23:24:08
合計ジャッジ時間 24,300 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
31,104 KB
testcase_01 AC 59 ms
30,848 KB
testcase_02 AC 58 ms
30,976 KB
testcase_03 AC 1,131 ms
93,384 KB
testcase_04 AC 1,168 ms
102,264 KB
testcase_05 AC 115 ms
51,456 KB
testcase_06 AC 1,127 ms
97,200 KB
testcase_07 AC 1,134 ms
89,480 KB
testcase_08 AC 1,160 ms
98,424 KB
testcase_09 AC 589 ms
53,248 KB
testcase_10 AC 585 ms
61,116 KB
testcase_11 AC 573 ms
53,632 KB
testcase_12 AC 1,068 ms
76,052 KB
testcase_13 AC 552 ms
61,908 KB
testcase_14 AC 1,162 ms
98,936 KB
testcase_15 AC 1,149 ms
98,808 KB
testcase_16 AC 1,154 ms
98,536 KB
testcase_17 AC 1,184 ms
257,488 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (108 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.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 int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, m) = (c[0], c[1]);
        var a = NList;
        var b = NList;
        for (var i = 0; i < a.Length; ++i) a[i] /= 100;
        if (b.Length < a.Length)
        {
            var nb = new int[a.Length];
            for (var i = 0; i < b.Length; ++i) nb[i] = b[i];
            b = nb;
        }
        Array.Sort(a);
        var b2 = new int[b.Length];
        for (var i = 0; i < b.Length; ++i) b2[i] = 100 - b[b.Length - i - 1];
        b = b2;
        Array.Sort(b);
        var ans = ConvolutionLL(a, b);
        WriteLine(string.Join("\n", ans.Take(n)));
    }
    static ulong MOD1 = 754_974_721;
    static ulong MOD2 = 167_772_161;
    static ulong MOD3 = 469_762_049;
    static ulong M1M2 = 126_663_740_442_542_081;
    static ulong M1M3 = 354_658_471_880_163_329;
    static ulong M2M3 = 78_812_994_116_517_889;
    static ulong M1M2M3 = 560_135_205_046_714_369;
    static ulong I1 = 190_329_765;
    static ulong I2 = 58_587_104;
    static ulong I3 = 187_290_749;
    static ulong[] offset = new ulong[] { 0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3 };
    static long[] ConvolutionLL(int[] a, int[] b)
    {
        var r1 = new ConvolutionCalculator((int)MOD1);
        var r2 = new ConvolutionCalculator((int)MOD2);
        var r3 = new ConvolutionCalculator((int)MOD3);
        var c1 = r1.Calc(a, b);
        var c2 = r2.Calc(a, b);
        var c3 = r3.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] - (int)(x % MOD1);
            if (diff < 0) diff += (int)MOD1;
            x -= offset[diff % 5];
            ans[i] = (long)x;
        }
        return ans;
    }
    static (long g, long x, long y) XGcd(long a, long b)
    {
        long x0 = 1, y0 = 0, x1 = 0, y1 = 1;
        while (b != 0)
        {
            var q = a / b;
            var prevA = a;
            a = b;
            b = prevA % b;
            var prevX0 = x0;
            var prevY0 = y0;
            x0 = x1;
            x1 = prevX0 - q * x1;
            y0 = y1;
            y1 = prevY0 - q * y1;
        }
        return (a, x0, y0);
    }
    class ConvolutionCalculator
    {
        int keyNum;
        public ConvolutionCalculator(int keyNum)
        {
            this.keyNum = keyNum;
        }
        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) <= 60)
            {
                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] % keyNum);
            }
            ButterflyInv(za);
            var iz = PowMod(z, keyNum - 2, keyNum);
            var ans = new int[n + m - 1];
            for (var i = 0; i < ans.Length; ++i)
            {
                ans[i] = (int)((long)za[i] * iz % keyNum);
            }
            return ans;
        }
        int[] ShortComvolution(int[] a, int[] b)
        {
            if (a.Length < b.Length)
            {
                var tmp = a;
                a = b;
                b = tmp;
            }
            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] % keyNum) % keyNum);
                }
            }
            return ans;
        }
        int[] sume = new int[30];
        int[] sumie = new int[30];
        void InitButterfly()
        {
            var g = PrimitiveRoot(keyNum);
            var es = new int[30];
            var ies = new int[30];
            var cnt2 = BSF(keyNum - 1);
            var e = PowMod(g, keyNum - 1 >> cnt2, keyNum);
            var ie = PowMod(e, keyNum - 2, keyNum);
            for (var i = cnt2; i >= 2; --i)
            {
                es[i - 2] = e;
                ies[i - 2] = ie;
                e = (int)((long)e * e % keyNum);
                ie = (int)((long)ie * ie % keyNum);
            }
            var now = 1L;
            var inow = 1L;
            for (var i = 0; i < cnt2 - 2; ++i)
            {
                sume[i] = (int)(es[i] * now % keyNum);
                now = now * ies[i] % keyNum;
                sumie[i] = (int)(ies[i] * inow % keyNum);
                inow = inow * es[i] % keyNum;
            }
        }

        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 % keyNum);
                        a[i + offset] = (l + r) % keyNum;
                        a[i + offset + p] = (int)((long)keyNum + l - r) % keyNum;
                    }
                    now = now * sume[BSF(~(uint)s)] % keyNum;
                }
            }
        }
        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) % keyNum;
                        a[i + offset + p] = (int)(((long)keyNum + l - r) * inow % keyNum);
                    }
                    inow = inow * sumie[BSF(~(uint)s)] % keyNum;
                }
            }
        }
        static int PowMod(int n, int p, int keyNum)
        {
            long _n = n % keyNum;
            var _p = p;
            var result = 1L;
            if ((_p & 1) == 1)
            {
                result *= _n;
            }
            while (_p > 0)
            {
                _n = _n * _n % keyNum;
                _p >>= 1;
                if ((_p & 1) == 1)
                {
                    result = (result * _n) % keyNum;
                }
            }
            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;
            throw new Exception("undefined primitive root");
        }
        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;
        }
    }
}
0