A182172.Yuilice 的滚筒标签

普及/提高-

官方

通过率:0%

时间限制:2.00s

内存限制:256MB

题目描述

Yuilice 的标签机中有 nn 行标签,从上到下编号为 11 到 nn。每行标签都是一个长度为 mm、只含小写英文字母的字符串,第 ii 行记为 sis_i。

她需要选择一个整数 kk,满足 0≤k<m0\le k<m,然后将所有字符串同时向左循环移动 kk 位。具体来说,将一个字符串开头的 kk 个字符按原顺序移到末尾;当 k=0k=0 时,字符串不变。所有行必须使用相同的 kk,行与行之间不能交换位置。

移动完成后,Yuilice 希望这些字符串按从上到下的顺序,满足字典序非降,即每一行都不大于下一行。两个等长字符串比较字典序时,从左到右找到第一处不同的字符,字母较小的一方字典序较小;如果没有不同字符,则两个字符串相等。

请计算有多少个不同的整数 kk 满足要求。即使两个不同的 kk 得到的全部字符串恰好相同,它们仍算作两种选择。

输入格式

第一行包含两个整数 n,mn,m,分别表示标签行数和每行字符串的长度。

接下来 nn 行,第 ii 行包含一个长度为 mm 的字符串 sis_i,表示第 ii 行标签的内容。字符串只含小写英文字母。

输出格式

输出一行一个整数,表示合法的整数 kk 的数量。没有合法选择时输出 00。

输入输出样例

  • 输入#1

    3 4
    abca
    abcb
    abda
    

    输出#1

    3
    
  • 输入#2

    2 3
    aba
    aba
    

    输出#2

    3
    

说明/提示

样例解释

样例 #1 中,k=0k=0、k=1k=1、k=2k=2 均合法。例如,k=2k=2 时,三行依次为 caab、cbab、daab,满足字典序非降。

当 k=3k=3 时,三行依次为 aabc、babc、aabd,第二行大于第三行,因此不合法。答案为 33。

样例 #2 中,两行内容相同。无论选择 k=0k=0、k=1k=1 还是 k=2k=2,移动后两行仍然相等,因此三种选择都合法。

数据范围

对于所有测试数据,满足 1≤n,m≤1061\le n,m\le10^6,n×m≤106n\times m\le10^6。所有字符串长度均为 mm,且只含小写英文字母。

测试点编号 nn mm n×mn\times m
1∼41\sim4 1≤n≤20001\le n\le2000 1≤m≤20001\le m\le2000 n×m≤2000n\times m\le2000
5∼205\sim20 1≤n≤1061\le n\le10^6 1≤m≤1061\le m\le10^6 n×m≤106n\times m\le10^6

输入解题思路,AI测评打分。不知道怎么写?

首页