結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
![]() |
提出日時 | 2021-01-15 22:37:45 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 487 ms / 2,000 ms |
コード長 | 3,009 bytes |
コンパイル時間 | 4,298 ms |
コンパイル使用メモリ | 109,312 KB |
実行使用メモリ | 22,912 KB |
最終ジャッジ日時 | 2024-11-27 23:14:15 |
合計ジャッジ時間 | 11,584 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
コンパイルメッセージ
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;using System.Collections.Generic;using System.Diagnostics;using System.IO;using System.Linq;using System.Numerics;using System.Text;using System.Text.RegularExpressions;using System.Threading.Tasks;using static System.Math;using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;public static class P{public static void Main(){var nmt = Console.ReadLine().Split().Select(long.Parse).ToArray();var n = (int)nmt[0];var m = (int)nmt[1];var t = nmt[2];Matrix mat = new Matrix(n, n);for (int i = 0; i < m; i++){var ab = Console.ReadLine().Split().Select(int.Parse).ToArray();var a = ab[0];var b = ab[1];mat[b, a] = true;}Matrix iv = new Matrix(n, 1);iv[0, 0] = true;var res = Power(mat, t) * iv;Console.WriteLine(Enumerable.Range(0, n).Count(x => res[x, 0]));}static Matrix Power(Matrix n, long m){Matrix pow = n;Matrix res = Matrix.Delta(n.Height, true);while (m > 0){if ((m & 1) == 1) res *= pow;pow *= pow;m >>= 1;}return res;}}class Matrix{public readonly int Height;public readonly int Width;bool[] data;[MethodImpl(MethodImplOptions.AggressiveInlining)]public Matrix(int height, int width){data = new bool[height * width];Height = height;Width = width;}public bool this[int i, int j]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get { return data[i * Width + j]; }[MethodImpl(MethodImplOptions.AggressiveInlining)]set { data[i * Width + j] = value; }}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Matrix Delta(int n, bool val){var res = new Matrix(n, n);for (int i = 0; i < n; i++) res[i, i] = val;return res;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Matrix Add(Matrix a, Matrix b){var res = new Matrix(a.Height, a.Width);for (int i = 0; i < a.Height; i++) for (int j = 0; j < a.Width; j++) res[i, j] = a[i, j] | b[i, j];return res;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Matrix Mul(Matrix a, Matrix b){var res = new Matrix(a.Height, b.Width);for (int i = 0; i < a.Height; i++) for (int j = 0; j < b.Width; j++) for (int k = 0; k < a.Width; k++) res[i, j] |= a[i, k] & b[k, j];return res;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Matrix operator +(Matrix a, Matrix b) => Add(a, b);[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Matrix operator *(Matrix a, Matrix b) => Mul(a, b);}