P5241 序列

    • 65通过
    • 714提交
  • 题目提供者 Created_equal1 管理员
  • 评测方式 云端评测
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1000ms-3500ms / 1024MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    构建一个N个点的有向图G,初始没有任何边。接下来构建一个长度为E的边的序列A,序列中每条边都是满足1≤s,t≤N且s≠t的有向边(s,t),且序列中的边互不相同。按照顺序把这些边加入到G中,每次加入后计算当前图的强连通分量个数并记录下来,得到一个新的长度为E的正整数序列B。如果两个边的序列得到的B相同则称它们本质相同。

    请问有多少种本质不同的边的序列,你只要求出答案对$10^9+7$取模后的结果。

    输入输出格式

    输入格式:

    输入一行,一个正整数N表示有向图G的点数。

    输出格式:

    输出一行N×(N-1)个由空格隔开的整数,第i个数表示当E=i时的答案。

    输入输出样例

    输入样例#1: 复制
    3
    
    输出样例#1: 复制
    1 2 4 7 7 7
    

    说明

    Subtask 1 (5pts):N≤5。

    Subtask 2 (10pts):N≤10。

    Subtask 3 (15pts):N≤20。

    Subtask 4 (15pts):N≤30。

    Subtask 5 (15pts):N≤50。

    Subtask 6 (20pts):N≤100。

    Subtask 7 (20pts):无特殊限制

    对于全部数据:1≤N≤400。

    前6个子任务限时1s,第7个3.5s。

    代码长度限制:10kb 超过这个限制赛后将会被标记为无效。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。