結果
問題 | No.916 Encounter On A Tree |
ユーザー | EmKjp |
提出日時 | 2019-10-25 22:43:28 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 5,820 bytes |
コンパイル時間 | 1,359 ms |
コンパイル使用メモリ | 113,468 KB |
実行使用メモリ | 33,728 KB |
最終ジャッジ日時 | 2024-09-13 06:14:39 |
合計ジャッジ時間 | 5,145 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 27 ms
26,196 KB |
testcase_01 | AC | 26 ms
24,052 KB |
testcase_02 | AC | 48 ms
32,024 KB |
testcase_03 | AC | 47 ms
31,676 KB |
testcase_04 | AC | 49 ms
33,576 KB |
testcase_05 | AC | 49 ms
31,668 KB |
testcase_06 | AC | 48 ms
31,916 KB |
testcase_07 | AC | 49 ms
31,552 KB |
testcase_08 | AC | 30 ms
24,688 KB |
testcase_09 | AC | 32 ms
25,588 KB |
testcase_10 | AC | 26 ms
23,988 KB |
testcase_11 | AC | 26 ms
22,192 KB |
testcase_12 | AC | 48 ms
31,560 KB |
testcase_13 | AC | 48 ms
31,600 KB |
testcase_14 | AC | 48 ms
31,804 KB |
testcase_15 | AC | 48 ms
33,724 KB |
testcase_16 | AC | 32 ms
23,220 KB |
testcase_17 | AC | 47 ms
31,668 KB |
testcase_18 | AC | 26 ms
25,960 KB |
testcase_19 | AC | 48 ms
31,544 KB |
testcase_20 | AC | 49 ms
33,728 KB |
testcase_21 | AC | 48 ms
31,660 KB |
testcase_22 | AC | 48 ms
31,676 KB |
testcase_23 | AC | 47 ms
31,764 KB |
testcase_24 | AC | 48 ms
31,676 KB |
testcase_25 | AC | 48 ms
31,540 KB |
testcase_26 | AC | 38 ms
25,404 KB |
testcase_27 | AC | 38 ms
29,496 KB |
testcase_28 | AC | 33 ms
25,716 KB |
testcase_29 | AC | 48 ms
31,848 KB |
testcase_30 | AC | 48 ms
31,548 KB |
testcase_31 | AC | 49 ms
33,720 KB |
testcase_32 | AC | 48 ms
31,784 KB |
testcase_33 | AC | 38 ms
27,804 KB |
testcase_34 | AC | 33 ms
25,536 KB |
testcase_35 | AC | 30 ms
24,376 KB |
testcase_36 | AC | 48 ms
31,540 KB |
testcase_37 | AC | 48 ms
31,688 KB |
testcase_38 | AC | 33 ms
27,320 KB |
testcase_39 | AC | 48 ms
33,712 KB |
testcase_40 | AC | 48 ms
33,572 KB |
testcase_41 | AC | 27 ms
24,044 KB |
testcase_42 | AC | 27 ms
26,084 KB |
testcase_43 | AC | 27 ms
24,048 KB |
testcase_44 | AC | 26 ms
24,244 KB |
testcase_45 | AC | 29 ms
24,364 KB |
testcase_46 | AC | 27 ms
23,928 KB |
testcase_47 | AC | 26 ms
24,184 KB |
testcase_48 | AC | 27 ms
26,168 KB |
testcase_49 | AC | 26 ms
23,924 KB |
testcase_50 | AC | 26 ms
26,280 KB |
testcase_51 | AC | 26 ms
24,048 KB |
testcase_52 | AC | 27 ms
24,108 KB |
testcase_53 | AC | 26 ms
22,068 KB |
testcase_54 | AC | 26 ms
24,180 KB |
testcase_55 | AC | 27 ms
26,316 KB |
testcase_56 | AC | 27 ms
24,308 KB |
testcase_57 | AC | 26 ms
24,304 KB |
testcase_58 | AC | 27 ms
24,372 KB |
testcase_59 | AC | 28 ms
24,168 KB |
testcase_60 | AC | 27 ms
24,220 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.Globalization; using System.IO; using System.Linq; using E = System.Linq.Enumerable; internal partial class Solver { const int mod = 1000000000 + 7; private int GetDepth(int x) { for (int depth = 1; depth < 30; depth++) { var lower = 1 << (depth - 1); var upper = lower * 2; if (lower <= x && x < upper) return depth; } throw new Exception(); } public void Run() { var d = ni(); var l = ni(); var r = ni(); var k = ni(); var depthL = GetDepth(l) - 1; var depthR = GetDepth(r) - 1; var diff = Math.Abs(depthL - depthR); var fact = new long[(1 << d) + 10]; fact[0] = fact[1] = 1; for (int i = 2; i < fact.Length; i++) { fact[i] = fact[i - 1] * i % mod; } long choose = 1; for (int i = 0; i < d; i++) { var p = 1 << i; if (depthL == i) p--; if (depthR == i) p--; choose *= fact[p]; choose %= mod; } long ans = 0; if ((k - diff) >= 0 && (k - diff) % 2 == 0) { var x = (k - diff) / 2; //new { x, diff }.Dump(); var lcpDepth = Math.Min(depthL, depthR) - x; if (lcpDepth >= 0) { if (x == 0) { ans = choose; ans *= 1 << lcpDepth; ans %= mod; ans *= 1 << diff; ans %= mod; } else { ans = 2 * choose; ans %= mod; ans *= 1 << lcpDepth; ans %= mod; var freeDepthL = Math.Max(x - 1, 0); var freeDepthR = Math.Max(x + diff - 1, 0); ans *= 1L << freeDepthL; ans %= mod; ans *= 1L << freeDepthR; ans %= mod; } } } cout.WriteLine(ans); } } // PREWRITEN CODE BEGINS FROM HERE internal partial class Solver : Scanner { public static void Main(string[] args) { #if LOCAL new Solver(Console.In, Console.Out).Run(); #else Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver(Console.In, Console.Out).Run(); Console.Out.Flush(); #endif } #pragma warning disable IDE0052 private readonly TextReader cin; private readonly TextWriter cout; #pragma warning restore IDE0052 public Solver(TextReader reader, TextWriter writer) : base(reader) { cin = reader; cout = writer; } public Solver(string input, TextWriter writer) : this(new StringReader(input), writer) { } #pragma warning disable IDE1006 #pragma warning disable IDE0051 private int ni() { return NextInt(); } private int[] ni(int n) { return NextIntArray(n); } private long nl() { return NextLong(); } private long[] nl(int n) { return NextLongArray(n); } private double nd() { return NextDouble(); } private double[] nd(int n) { return NextDoubleArray(n); } private string ns() { return Next(); } private string[] ns(int n) { return NextArray(n); } #pragma warning restore IDE1006 #pragma warning restore IDE0051 } internal static class LinqPadExtension { public static T Dump<T>(this T obj) { #if LOCAL return LINQPad.Extensions.Dump(obj); #else return obj; #endif } } public class Scanner { private readonly TextReader Reader; private readonly Queue<string> TokenQueue = new Queue<string>(); private readonly CultureInfo ci = CultureInfo.InvariantCulture; public Scanner() : this(Console.In) { } public Scanner(TextReader reader) { Reader = reader; } public int NextInt() { return int.Parse(Next(), ci); } public long NextLong() { return long.Parse(Next(), ci); } public double NextDouble() { return double.Parse(Next(), ci); } public string[] NextArray(int size) { string[] array = new string[size]; for (int i = 0; i < size; i++) { array[i] = Next(); } return array; } public int[] NextIntArray(int size) { int[] array = new int[size]; for (int i = 0; i < size; i++) { array[i] = NextInt(); } return array; } public long[] NextLongArray(int size) { long[] array = new long[size]; for (int i = 0; i < size; i++) { array[i] = NextLong(); } return array; } public double[] NextDoubleArray(int size) { double[] array = new double[size]; for (int i = 0; i < size; i++) { array[i] = NextDouble(); } return array; } public string Next() { if (TokenQueue.Count == 0) { if (!StockTokens()) { throw new InvalidOperationException(); } } return TokenQueue.Dequeue(); } public bool HasNext() { if (TokenQueue.Count > 0) { return true; } return StockTokens(); } private static readonly char[] _separator = new[] { ' ', '\t' }; private bool StockTokens() { while (true) { string line = Reader.ReadLine(); if (line == null) { return false; } string[] tokens = line.Split(_separator, StringSplitOptions.RemoveEmptyEntries); if (tokens.Length == 0) { continue; } foreach (string token in tokens) { TokenQueue.Enqueue(token); } return true; } } }