結果
| 問題 |
No.2770 Coupon Optimization
|
| コンテスト | |
| ユーザー |
 kakel-san
|
| 提出日時 | 2024-05-31 23:22:53 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,971 bytes |
| コンパイル時間 | 16,554 ms |
| コンパイル使用メモリ | 168,256 KB |
| 実行使用メモリ | 256,812 KB |
| 最終ジャッジ日時 | 2024-12-21 01:40:14 |
| 合計ジャッジ時間 | 27,550 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 2 |
| other | WA * 16 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (122 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/
ソースコード
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);
WriteLine(string.Join(" ", a));
WriteLine(string.Join(" ", 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;
}
}
}