結果
問題 | No.1696 Nonnil |
ユーザー | eSeF |
提出日時 | 2020-10-28 18:37:34 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,366 ms / 3,500 ms |
コード長 | 9,137 bytes |
コンパイル時間 | 2,898 ms |
コンパイル使用メモリ | 114,380 KB |
実行使用メモリ | 279,388 KB |
最終ジャッジ日時 | 2023-09-26 15:32:39 |
合計ジャッジ時間 | 33,340 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 62 ms
21,868 KB |
testcase_01 | AC | 62 ms
22,112 KB |
testcase_02 | AC | 62 ms
19,920 KB |
testcase_03 | AC | 1,041 ms
276,816 KB |
testcase_04 | AC | 77 ms
21,876 KB |
testcase_05 | AC | 63 ms
21,988 KB |
testcase_06 | AC | 63 ms
23,956 KB |
testcase_07 | AC | 63 ms
23,864 KB |
testcase_08 | AC | 1,004 ms
279,244 KB |
testcase_09 | AC | 135 ms
43,148 KB |
testcase_10 | AC | 179 ms
48,748 KB |
testcase_11 | AC | 133 ms
36,536 KB |
testcase_12 | AC | 167 ms
49,660 KB |
testcase_13 | AC | 129 ms
37,076 KB |
testcase_14 | AC | 1,084 ms
250,240 KB |
testcase_15 | AC | 261 ms
58,892 KB |
testcase_16 | AC | 1,212 ms
279,112 KB |
testcase_17 | AC | 954 ms
229,184 KB |
testcase_18 | AC | 526 ms
124,120 KB |
testcase_19 | AC | 61 ms
23,928 KB |
testcase_20 | AC | 62 ms
21,936 KB |
testcase_21 | AC | 733 ms
188,040 KB |
testcase_22 | AC | 783 ms
181,936 KB |
testcase_23 | AC | 678 ms
166,760 KB |
testcase_24 | AC | 650 ms
156,624 KB |
testcase_25 | AC | 1,038 ms
222,056 KB |
testcase_26 | AC | 999 ms
229,520 KB |
testcase_27 | AC | 1,171 ms
274,204 KB |
testcase_28 | AC | 753 ms
168,136 KB |
testcase_29 | AC | 823 ms
207,236 KB |
testcase_30 | AC | 602 ms
150,652 KB |
testcase_31 | AC | 1,008 ms
243,776 KB |
testcase_32 | AC | 1,083 ms
263,128 KB |
testcase_33 | AC | 849 ms
190,100 KB |
testcase_34 | AC | 765 ms
198,464 KB |
testcase_35 | AC | 884 ms
215,912 KB |
testcase_36 | AC | 1,349 ms
279,320 KB |
testcase_37 | AC | 1,366 ms
279,388 KB |
testcase_38 | AC | 1,353 ms
275,132 KB |
testcase_39 | AC | 1,197 ms
278,088 KB |
testcase_40 | AC | 1,253 ms
274,872 KB |
testcase_41 | AC | 391 ms
72,596 KB |
testcase_42 | AC | 890 ms
248,764 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; using System.IO; using System.Text; using System.Numerics; using System.Threading; using System.Runtime.CompilerServices; using System.Diagnostics; using static System.Math; using static System.Array; using static AtCoder.Cout; using static AtCoder.Tool; using static AtCoder.ModInt; namespace AtCoder { class AC { //const int MOD = 1000000007; const int MOD = 998244353; const int INF = int.MaxValue / 2; const long SINF = long.MaxValue / 3; static readonly int[] dI = { 0, 1, 0, -1, 1, -1, -1, 1 }; static readonly int[] dJ = { 1, 0, -1, 0, 1, 1, -1, -1 }; static void Main(string[] args) { //var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw); /*var th = new Thread(Run, 1 << 26); th.Start(); th.Join();*/ Run(); Console.Out.Flush(); } static void Run() { int Testcase = 1; //Testcase = Cin.Int; for (var _ = 0; _ < Testcase; _++) Solve(); } static void Solve() { Cin.Scanf(out int N, out int K); int M = Cin.Int; var R = new int[K + 1];//終点が i の区間のうち L の最大値(存在しないなら-1) Fill(R, -1); for(var i = 0; i < M; i++) { Cin.Scanf(out int ll, out int rr); R[rr] = Max(R[rr], ll); } for(var i = K; i >= 1; i--) { var ok = true; for(var j = i - 1; j >= 1; j--) { ok &= R[j] < R[i]; } if (!ok) R[i] = -1; } var dpj = new long[K + 1][][]; var dpjk = new long[K + 1][][]; for(var i = 0; i <= K; i++) { dpj[i] = new long[K + 1][]; dpjk[i] = new long[K + 1][]; for(var j = 0; j <= K; j++) { dpj[i][j] = new long[2]; dpjk[i][j] = new long[2]; } } dpj[0][0][0] = 1; dpjk[0][0][0] = 1; for(var j = 1; j <= K; j++) { for(var k = 0; k <= K; k++) { long[] nx = { 0, 0 }; if (R[j] != -1 && k > 0) { int L = R[j]; for(var l = 0; l < 2; l++) { nx[l] += dpjk[j - 1][k - 1][l ^ 1]; if (k - (j - L) - 1 >= 0) nx[l] -= dpjk[L - 1][k - (j - L) - 1][l ^ 1]; if (k - (j - L) - 1 >= 0) nx[l] += dpj[L - 1][k - (j - L) - 1][l ^ 1]; nx[l] %= MOD; if (nx[l] < 0) nx[l] += MOD; } } for(var l = 0; l < 2; l++) { dpj[j][k][l] = (dpj[j - 1][k][l] + nx[l]) % MOD; dpjk[j][k][l] = (nx[l]); if (j > 0 && k > 0) dpjk[j][k][l] += dpjk[j - 1][k - 1][l]; dpjk[j][k][l] %= MOD; } } } ModInt ans = 0; for(var k = 0; k <= K; k++) { ans += (dpj[K][k][0] - dpj[K][k][1]) * Modpow(K - k, N); } OutL(ans); } } struct ModInt { public long value; //const int MOD = 1000000007; const int MOD = 998244353; public ModInt(long value) { this.value = value; } public override string ToString() => value.ToString(); public static implicit operator ModInt(long a) { var ret = a % MOD; return new ModInt(ret < 0 ? (ret + MOD) : ret); } public static ModInt operator +(ModInt a, ModInt b) => (a.value + b.value); public static ModInt operator -(ModInt a, ModInt b) => (a.value - b.value); public static ModInt operator *(ModInt a, ModInt b) => (a.value * b.value); public static ModInt operator /(ModInt a, ModInt b) => a * Modpow(b, MOD - 2); public static ModInt operator <<(ModInt a, int n) => (a.value << n); public static ModInt operator >>(ModInt a, int n) => (a.value >> n); public static ModInt operator ++(ModInt a) => a.value + 1; public static ModInt operator --(ModInt a) => a.value - 1; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static ModInt Modpow(ModInt a, long n) { if (n == 0) return 1; if (n < 0) return Modpow(Modpow(a, -n), MOD - 2); var k = a; ModInt ret = 1; while (n > 0) { if ((n & 1) != 0) ret *= k; k *= k; n >>= 1; } return ret; } private static readonly List<long> Factorials = new List<long>() { 1 }; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static ModInt Fac(int n) { if (n < 0) return 0; for (var i = Factorials.Count(); i <= n; i++) { Factorials.Add((Factorials[i - 1] * i) % MOD); } return Factorials[n]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static ModInt nCr(int n, int r) { if (n < 0 || r < 0) return 0; return n < r ? 0 : Fac(n) / (Fac(r) * Fac(n - r)); } public static explicit operator int(ModInt a) => (int)a.value; } static class Cin { public static string[] ReadSplit => Console.ReadLine().Split(); public static int[] ReadSplitInt => ConvertAll(ReadSplit, int.Parse); public static long[] ReadSplitLong => ConvertAll(ReadSplit, long.Parse); public static double[] ReadSplit_Double => ConvertAll(ReadSplit, double.Parse); public static string Str => Console.ReadLine(); public static int Int => int.Parse(Console.ReadLine()); public static long Long => long.Parse(Console.ReadLine()); public static double Double => double.Parse(Console.ReadLine()); public static T Conv<T>(string input) { if (typeof(T).Equals(typeof(ModInt))) { return (T)(dynamic)(long.Parse(input)); } return (T)Convert.ChangeType(input, typeof(T)); } public static void Scanf<T>(out T a) => a = Conv<T>(Console.ReadLine()); public static void Scanf<T, U>(out T a, out U b) { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); } public static void Scanf<T, U, V>(out T a, out U b, out V c) { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); } public static void Scanf<T, U, V, W>(out T a, out U b, out V c, out W d) { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); } public static void Scanf<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e) { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); e = Conv<X>(q[4]); } } static class Cout { public static void OutL(object s) => Console.WriteLine(s); public static void Out_Sep<T>(IEnumerable<T> s) => Console.WriteLine(string.Join(" ", s)); public static void Out_Sep<T>(IEnumerable<T> s, string sep) => Console.WriteLine(string.Join($"{sep}", s)); public static void Out_Sep(params object[] s) => Console.WriteLine(string.Join(" ", s)); public static void Out_One(object s) => Console.Write($"{s} "); public static void Out_One(object s, string sep) => Console.Write($"{s}{sep}"); public static void Endl() => Console.WriteLine(); } public static class Tool { static public void Initialize<T>(ref T[] array, T initialvalue) { array = ConvertAll(array, x => initialvalue); } static public void Swap<T>(ref T a, ref T b) { T keep = a; a = b; b = keep; } static public void Display<T>(T[,] array2d, int n, int m) { for (var i = 0; i < n; i++) { for (var j = 0; j < m; j++) { Console.Write($"{array2d[i, j]} "); } Console.WriteLine(); } } static public long Gcd(long a, long b) { if (a == 0 || b == 0) return Max(a, b); return a % b == 0 ? b : Gcd(b, a % b); } static public bool Bit(long x, int dig) => ((1L << dig) & x) != 0; static public int Sig(long a) => a == 0 ? 0 : (int)(a / Abs(a)); } }