結果

問題 No.562 超高速一人かるた small
ユーザー Risen
提出日時 2017-08-27 12:05:26
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 6,553 bytes
コンパイル時間 1,038 ms
コンパイル使用メモリ 115,680 KB
実行使用メモリ 30,472 KB
最終ジャッジ日時 2024-11-06 06:38:15
合計ジャッジ時間 3,025 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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;
    }
}

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 removes = parents.Select(p => p.Item1).ToArray();
        var patterns = removes.Select(r => r <= removeCount ? CalcPermutation(removeCount, r) : 0).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 = CalcPermutation(otherCount, removeCount) - 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;
        }
    }
}
0