結果
問題 | No.563 超高速一人かるた large |
ユーザー | Risen |
提出日時 | 2017-08-27 15:49:01 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 7,485 bytes |
コンパイル時間 | 2,660 ms |
コンパイル使用メモリ | 116,692 KB |
実行使用メモリ | 48,552 KB |
最終ジャッジ日時 | 2024-11-06 06:44:54 |
合計ジャッジ時間 | 9,649 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
28,152 KB |
testcase_01 | AC | 48 ms
28,260 KB |
testcase_02 | AC | 44 ms
25,608 KB |
testcase_03 | AC | 426 ms
33,928 KB |
testcase_04 | AC | 2,668 ms
38,920 KB |
testcase_05 | TLE | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
コンパイルメッセージ
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.Numerics; using System.Linq; using static Common; public static class Common { public const int Mod = 1000000007; // nPk private static Dictionary<Tuple<int, int>, BigInteger> perms = new Dictionary<Tuple<int, int>, BigInteger>(); public static BigInteger CalcPermutation(int n, int k) { var key = Tuple.Create(n, k); if (perms.ContainsKey(key)) { return perms[key]; } var v = Enumerable.Range(n - k + 1, k).Aggregate(BigInteger.One, (p, next) => p * next); perms[key] = v; return v; } // nCk private static Dictionary<Tuple<int, int>, BigInteger> combs = new Dictionary<Tuple<int, int>, BigInteger>(); public static BigInteger CalcCombination(int n, int k) { var key = Tuple.Create(n, k); if (combs.ContainsKey(key)) { return combs[key]; } var v = CalcPermutation(n, k); for (int i = 2; i <= k; i++) { v /= i; } combs[key] = v; return v; } } public class PatriciaNode { public string Fullstr { private set; get; } public string Str; public PatriciaNode Parent; public List<PatriciaNode> Children = new List<PatriciaNode>(); public int DescendantCount { private set; get; } public PatriciaNode() { } public PatriciaNode(string str) { Fullstr = str; } public void SetFullStr(string parentName = "") { Fullstr = parentName + Str; foreach (var child in Children) { child.SetFullStr(Fullstr); } } public int SetDescendantCount() { int count = 0; foreach (var child in Children) { count += child.SetDescendantCount(); } DescendantCount = count; return Math.Max(1, DescendantCount); } public long GetExpectedLength(int removeCount, int otherCount) { // 削除する必要のある子孫の数, 決まり字までの文字列長 var parents = new List<Tuple<int, int>>(); for (var node = Parent; node != null; node = node.Parent) { var len = node.Parent == null ? 1 : node.Parent.Fullstr.Length + 1; parents.Add(Tuple.Create(node.DescendantCount - 1, len)); } var allPattern = CalcPermutation(otherCount, removeCount); var removes = parents.Select(p => p.Item1).ToArray(); var patterns = removes.Select(r => { if (r > removeCount) { return 0; } // 削除対象の組み合わせ * 残りの組み合わせ * 並べ方 var remComb = CalcCombination(r, r); var otherComb = CalcCombination(otherCount - r, removeCount - r); return remComb * otherComb * CalcPermutation(removeCount, removeCount); }).ToList(); patterns.Add(0); long expects = 0; for (int i = 0; i < parents.Count; i++) { // 重複するので,上位のパターンを除く expects += (long)(((patterns[i] - patterns[i + 1]) * parents[i].Item2) % Mod); } var remainPattern = allPattern - patterns.First(); expects += (long)((remainPattern * (Parent.Fullstr.Length + 1)) % Mod); expects %= Mod; return expects; } public override string ToString() { return $" {Fullstr}: DescendantCount:{DescendantCount}"; } } public class PatriciaTree { public PatriciaNode Root; public PatriciaTree() { Root = new PatriciaNode(); Root.Str = ""; } public void Add(string str) { var node = new PatriciaNode(str); if (Root == null) { node.Str = str; Root = node; return; } var parent = Root; for (var s = str; ;) { // 部分的にしか合致しないので,共通部を親にして子になる if (!s.StartsWith(parent.Str)) { int sameCount; for (sameCount = 0; true; sameCount++) { if (s[sameCount] != parent.Str[sameCount]) { break; } } var overlap = s.Substring(0, sameCount); var newParent = new PatriciaNode { Str = overlap, Parent = parent.Parent }; newParent.Parent.Children.Remove(parent); newParent.Parent.Children.Add(newParent); newParent.Children.Add(parent); newParent.Children.Add(node); parent.Parent = newParent; parent.Str = parent.Str.Substring(sameCount); node.Parent = newParent; node.Str = s.Substring(sameCount); return; } s = s.Substring(parent.Str.Length); bool found = false; foreach (var child in parent.Children) { if (s[0] == child.Str[0]) { parent = child; found = true; break; } } // 新しいChildになる if (!found) { node.Str = s; node.Parent = parent; parent.Children.Add(node); return; } } } public List<PatriciaNode> GetEdges() { var edges = new List<PatriciaNode>(); var nodes = new List<PatriciaNode> { Root }; while (nodes.Count > 0) { var children = new List<PatriciaNode>(); foreach (var node in nodes) { if (node.Children.Count == 0) { edges.Add(node); } else { children.AddRange(node.Children); } } nodes = children; } return edges; } public void UpdateTree() { Root.SetFullStr(); Root.SetDescendantCount(); } public override string ToString() { var s = ""; var nodes = new List<PatriciaNode> { Root }; while (nodes.Count > 0) { var next = new List<PatriciaNode>(); foreach (var node in nodes) { s += node + "\n"; next.AddRange(node.Children); } nodes = next; } return s; } } class Solution { static void Main() { var n = int.Parse(Console.ReadLine()); var tree = new PatriciaTree(); for (int i = 0; i < n; i++) { var s = Console.ReadLine() + " "; tree.Add(s); } tree.UpdateTree(); var edges = tree.GetEdges(); long expected = 0; for (int remove = 0; remove < n; remove++) { foreach (var e in edges) { expected += e.GetExpectedLength(remove, n - 1); expected %= Mod; } Console.WriteLine(expected); expected *= (n - remove - 1); expected %= Mod; } } }