結果
問題 | No.184 たのしい排他的論理和(HARD) |
ユーザー | utaka |
提出日時 | 2019-09-27 20:24:07 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 138 ms / 5,000 ms |
コード長 | 12,340 bytes |
コンパイル時間 | 1,186 ms |
コンパイル使用メモリ | 110,336 KB |
実行使用メモリ | 38,144 KB |
最終ジャッジ日時 | 2024-07-04 12:32:13 |
合計ジャッジ時間 | 5,219 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 23 ms
17,536 KB |
testcase_01 | AC | 22 ms
17,664 KB |
testcase_02 | AC | 21 ms
17,536 KB |
testcase_03 | AC | 23 ms
17,792 KB |
testcase_04 | AC | 24 ms
17,920 KB |
testcase_05 | AC | 23 ms
17,792 KB |
testcase_06 | AC | 23 ms
17,792 KB |
testcase_07 | AC | 23 ms
17,664 KB |
testcase_08 | AC | 109 ms
35,072 KB |
testcase_09 | AC | 44 ms
20,356 KB |
testcase_10 | AC | 85 ms
27,392 KB |
testcase_11 | AC | 71 ms
24,960 KB |
testcase_12 | AC | 116 ms
36,352 KB |
testcase_13 | AC | 123 ms
37,120 KB |
testcase_14 | AC | 82 ms
26,880 KB |
testcase_15 | AC | 138 ms
37,632 KB |
testcase_16 | AC | 118 ms
35,968 KB |
testcase_17 | AC | 123 ms
36,864 KB |
testcase_18 | AC | 24 ms
17,792 KB |
testcase_19 | AC | 22 ms
17,664 KB |
testcase_20 | AC | 71 ms
24,832 KB |
testcase_21 | AC | 138 ms
37,888 KB |
testcase_22 | AC | 133 ms
38,144 KB |
testcase_23 | AC | 23 ms
17,792 KB |
testcase_24 | AC | 23 ms
17,536 KB |
testcase_25 | AC | 22 ms
17,664 KB |
testcase_26 | AC | 23 ms
17,920 KB |
testcase_27 | AC | 23 ms
17,536 KB |
testcase_28 | AC | 91 ms
28,288 KB |
testcase_29 | AC | 123 ms
36,736 KB |
testcase_30 | AC | 109 ms
35,456 KB |
testcase_31 | AC | 100 ms
33,536 KB |
testcase_32 | AC | 116 ms
36,096 KB |
testcase_33 | AC | 136 ms
37,760 KB |
testcase_34 | AC | 129 ms
37,376 KB |
testcase_35 | AC | 133 ms
37,888 KB |
testcase_36 | AC | 133 ms
37,760 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
#if true && UTAKA_LOCAL //#if false #define UTAKA_DEBUG #endif using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.IO; using System.Linq; using System.Net.Mime; using System.Text; namespace UtakaApp { public partial class Program { public const string SiteName = "Yukicoder"; public const string ContestName = "184"; public const string ProblemName = ""; public static void Main(string[] args) { #if UTAKA_LOCAL //#if false new TestCaseCheckerForAtCoder().TestProblems(); #else var console = new MyConsole(); new Program().Solve(System.Console.In, console); console.Flush(); #endif var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false}; } public void Solve(TextReader textReader, IConsole console) { var cin = new ConsoleInput(textReader); int N = cin.ReadInt; long[] A = cin.ReadLongArray(N); int rank = GaussJordanBit.CalcReverse(A, 64, false); long x = 0; // var ans = Math.Pow(2, rank); var ans = ModPow(2, rank, long.MaxValue); console.WriteLine(ans.ToString()); } long LongMax(long x, long y) { return (x > y) ? x : y; } [Conditional("UTAKA_DEBUG")] public void DebugWriteEnumerable<T>(IEnumerable<T> A, string delimiter = " ") { var sb = new StringBuilder(); foreach (T v in A) { sb.Append(v); sb.Append(" "); } if (sb.Length > 0) { sb.Length--; } Console.WriteLine(sb.ToString()); } /// <summary> /// a^n mod.n を計算する /// </summary> public long ModPow(long a, long n, long mod = 1000000007) { long res = 1; while (n > 0) { if ((n & 1) != 0) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } } /// 0 1 の掃き出し法 public static class GaussJordanBit { /// 桁の大きい方から掃き出す /// rankを返す public static int CalcReverse(long[] A, int n, bool isExtended = false) { int m = A.Length; int rank = 0; for (int col = n; col >= 0; col--) { if (isExtended && col == 0) break; int pivot = -1; for (int row = rank; row < m; row++) { if ((A[row] & 1L << col) != 0) { pivot = row; break; } } if (pivot == -1) continue; Swap(ref A[pivot], ref A[rank]); for (int row = 0; row < m; row++) { if (row != rank && (A[row] & 1L << col) != 0) { A[row] ^= A[rank]; } } rank++; } return rank; } public static int LinearEquationReverse(long[] inputA, bool[] b, int n, out bool[] result) { int m = inputA.Length; // 拡張する ただしinputAに1列分の余裕が必要 long[] A = new long[m]; for (int row = 0; row < m; row++) { A[row] |= (A[row] << 1) & (b[row] ? 1 : 0); } // out引数に値を入れておく result = new bool[m]; // 解があるか求める int rank = CalcReverse(A, n, true); for (int row = rank; row < m; row++) { if ((A[row] & 1) > 0) return -1; } // 解を求める for (int row = 0; row < rank; row++) { result[row] = (A[row] & 1) != 0; } return rank; } /// 掃き出す /// rankを返す public static int Calc(long[] A, int n, bool isExtended = false) { int m = A.Length; int rank = 0; for (int col = 0; col < n; col++) { if (isExtended && col == n - 1) break; int pivot = -1; for (int row = rank; row < m; row++) { if ((A[row] & 1L << col) != 0) { pivot = row; break; } } if (pivot == -1) continue; Swap(ref A[pivot], ref A[rank]); for (int row = 0; row < m; row++) { if (row != rank && (A[row] & 1L << col) != 0) { A[row] ^= A[rank]; } } rank++; } return rank; } public static int LinearEquation(long[] inputA, bool[] b, int n, out bool[] result) { int m = inputA.Length; // 拡張する ただしinputAに1列分の余裕が必要 long[] A = new long[m]; for (int row = 0; row < m; row++) { if (b[row]) { A[row] |= 1L << n; } } // out引数に値を入れておく result = new bool[m]; // 解があるか求める int rank = Calc(A, n, true); for (int row = rank; row < m; row++) { if ((A[row] & 1L << n) > 0) return -1; } // 解を求める for (int row = 0; row < rank; row++) { result[row] = (A[row] & 1L << n) != 0; } return rank; } public static void Swap<T>(ref T a, ref T b) { T c = a; a = b; b = c; } } public partial class Program { public const int ModLarge = 1000000007; } public class ConsoleInput { private readonly TextReader _stream; private readonly char _separator = ' '; private readonly Queue<string> inputStream; public ConsoleInput(TextReader stream, char separator = ' ') { _separator = separator; _stream = stream; inputStream = new Queue<string>(); } public string Read { get { if (inputStream.Count != 0) { return inputStream.Dequeue(); } var tmp = _stream.ReadLine().Split(_separator); for (var i = 0; i < tmp.Length; ++i) { inputStream.Enqueue(tmp[i]); } return inputStream.Dequeue(); } } public string ReadLine => _stream.ReadLine(); public int ReadInt => int.Parse(Read); public long ReadLong => long.Parse(Read); public double ReadDouble => double.Parse(Read); public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) { ret[i] = Read; } return ret; } public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadInt; } return ret; } public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadLong; } return ret; } } public interface IConsole { void Flush(); void Write(string str); void WriteLine(string str); } public class MyConsole : IConsole { public MyConsole() { var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false}; Console.SetOut(sw); } public void Flush() { Console.Out.Flush(); } public void Write(string str) { Console.Write(str); } public void WriteLine(string str) { Console.WriteLine(str); } } #if UTAKA_LOCAL public class DebugConsole : IConsole { private readonly StringBuilder mSb; public DebugConsole() { mSb = new StringBuilder(); } public void Flush() { // 何もしない } public void Write(string str) { mSb.Append(str); } public void WriteLine(string str) { mSb.AppendLine(str); } public string GetAllOutput() { return mSb.ToString(); } } #endif #if UTAKA_LOCAL public class TestCaseCheckerForAtCoder { private string GetDirectoryPath() { var problemPart = string.IsNullOrEmpty(Program.ProblemName) ? "" : $"/{Program.ProblemName}"; return $"{System.Environment.GetFolderPath(Environment.SpecialFolder.UserProfile)}/AlgorithmPrac/{Program.SiteName}/{Program.ContestName}{problemPart}"; } private string GetInputFilePath(int testCaseNumber) { return $"{GetDirectoryPath()}/sample-{testCaseNumber}.in"; } private string GetOutputFilePath(int testCaseNumber) { return $"{GetDirectoryPath()}/sample-{testCaseNumber}.out"; } public bool TestProblem(int testCaseNumber) { var inputFilePath = GetInputFilePath(testCaseNumber); var outputFilePath = GetOutputFilePath(testCaseNumber); TextReader inputStream = new StreamReader(inputFilePath); var debugConsoleWriter = new DebugConsole(); new Program().Solve(inputStream, debugConsoleWriter); var output = debugConsoleWriter.GetAllOutput(); TextReader outputStream = new StreamReader(outputFilePath); var outputAnswer = outputStream.ReadToEnd(); Dbg.WriteLine(output); Dbg.WriteLine(outputAnswer); var isCorrect = output == outputAnswer; return isCorrect; } public void TestProblems() { var isSuccessAll = true; var testCaseNumber = 1; while (true) { var inputFileName = GetInputFilePath(testCaseNumber); if (!File.Exists(inputFileName)) { break; } Console.WriteLine($"TestCase {testCaseNumber} ====================================================="); var result = TestProblem(testCaseNumber); if (result) { Console.WriteLine("Success"); } else { isSuccessAll = false; Console.WriteLine("Failure *****"); } testCaseNumber++; } if (isSuccessAll) { Console.WriteLine("!!!!!!!!! All Success !!!!!!!!!"); } } } #endif #if UTAKA_LOCAL public static class Dbg { public static void WriteLine(string str) { Console.WriteLine(str); } public static void Write(string str) { Console.Write(str); } } #else public static class Dbg { public static void WriteLine(string str) { } public static void Write(string str) { } } #endif }