P7473 - Equal Sentences

内存限制：128 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：15 通过：12

Sometimes, changing the order of the words in a sentence doesn't influence understanding. For example, if we change "what time is it", into "what time it is"; or change "orz zhang three ak world final", into "zhang orz three world ak final", the meaning of the whole sentence doesn't change a lot, and most people can also understand the changed sentences well.

Formally, we define a sentence as a sequence of words. Two sentences

S and

T are almost-equal if the two conditions holds:

1. The multiset of the words in

S is the same as the multiset of the words in

T.
2. For a word

α, its

ith occurrence in

S and its

ith occurrence in

T have indexes differing no more than

1. (The

kth word in the sentence has index

k.) This holds for all

α and

i, as long as the word

α appears at least

i times in both sentences.

Please notice that "almost-equal" is not a equivalence relation, unlike its name. That is, if sentences

A and

B are almost-equal,

B and

C are almost-equal, it is possible that

A and

C are not almost-equal.

Zhang3 has a sentence

S consisting of

n words. She wants to know how many different sentences there are, which are almost-equal to

S, including

S itself. Two sentences are considered different, if and only if there is a number

i such that the

ith word in the two sentences are different. As the answer can be very large, please help her calculate the answer modulo

109+7.

The first line of the input gives the number of test cases,

T(1≤T≤100).

Ttest cases follow.
For each test case, the first line contains an integer

n(1≤n≤105), the number of words in the sentence.
The second line contains the sentence

Sconsisting of

nwords separated by spaces. Each word consists of no more than

10lowercase English letters.
The sum of

nin all test cases doesn't exceed

2×105.

For each test case, print a line with an integer, representing the answer, modulo

109+7.

2
6
he he zhou is watching you
13
yi yi si wu yi si yi jiu yi jiu ba yao ling

8
233

2020 Multi-University Training Contest 4

7473: Equal Sentences

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签