UOJ Logo

NOI.AC

2S 512MB

#35. string

统计

字符串

题目描述

小 $D$ 现在正在研究一种特殊的字符串:仅由 $A,B,C,D$ 四种字母组成的字符串。

对于这样的一个字符串 $S$,小 $D$ 可以用以下两种方式之一修改这个字符串:

  • 交换 $S$ 中的相邻两个字母;
  • 使用一种魔法。小 $D$ 共有 $m$ 种魔法,其中第 $i$ 种可以将 $S$ 中一个等于 $X_i$ 的子串(如果你不知道他是什么,可以参考 “数据规模与约定” 一节)替换为 $Y_i$。保证 $\lvert X_i\rvert=\lvert Y_i\rvert$。

小 $D$ 觉得通过修改得到不同的字符串非常有意思,于是他想要知道:对于所有这样的(即仅由 $A,B,C,D$ 四种字母组成的字符串)长度为 $n$ 的字符串 $S$,经过的字符串最多的修改序列是哪个(注意:如果一个字符串被经过了多次,他也只能被计算一次)?

你并不愿意帮助他,但是盛情难却,所以你只要帮他求出最多的那个修改序列经过了多少字符串即可。

输入格式

第一行两个空格隔开的整数 $n,m$,表示字符串的长度和魔法的个数。

接下来 $m$ 行,每行两个空格隔开的字符串 $X_i,Y_i$ 表示一种魔法。保证 $X_i,Y_i$ 仅由 $A,B,C,D$ 四种字母组成。

输出格式

输出一行一个整数表示答案。

样例输入 1

2 3
A B
A C
D D

样例输出 1

5

样例解释 1

其中一种最优方案为 $AA\to AB\to BA\to BC\to CB$,这样共经过了 $5$ 个字符串。可以证明这是最优答案。

样例输入 2

6 6
AABBC AACCB
AAAADA DAAABC
AAACA AAAAD
CABAA ABCBA
AAAAAA AABAAA
BAAAA AACAA

样例输出 2

499

样例输入输出 3 & 4

ex_string3.in/out 以及 ex_string4.in/out

数据规模与约定

本题共 $20$ 个测试点,每个测试点 $5$ 分。

对于所有测试数据,保证 $1\le n\le 50$,$1\le m\le 100$,$1\le \lvert X_i\rvert=\lvert Y_i\rvert\le n$。注意可能有的魔法出现多次,也可能有的魔法中 $X_i=Y_i$。以下为每个测试数据的数据规模:

测试数据编号 $n\le$ $m\le$ 测试数据编号 $n\le$ $m\le$
$1$ $3$ $3$ $11$ $20$ $30$
$2$ $3$ $5$ $12$ $30$ $30$
$3$ $5$ $5$ $13$ $30$ $40$
$4$ $5$ $7$ $14$ $30$ $45$
$5$ $7$ $7$ $15$ $30$ $50$
$6$ $7$ $10$ $16$ $30$ $65$
$7$ $10$ $10$ $17$ $50$ $80$
$8$ $10$ $20$ $18$ $50$ $90$
$9$ $10$ $25$ $19$ $50$ $95$
$10$ $10$ $30$ $20$ $50$ $100$

友情提醒:本题答案可能很大,甚至有可能超过 $64$ 位整数的表示范围(即 C/C++unsigned long long 以及 Pascalqword)。同时,NOI 系列赛事均禁止使用非标准的 __int128(对于 C/C++ 语言),请选手注意。

子串的定义:对于字符串 $S=S_1S_2S_3\cdots S_{n-1}S_n$,$T$ 是 $S$ 的子串,当且仅当存在 $1\le l\le r\le n$,满足 $T=S_lS_{l+1}S_{l+2}\cdots S_{r-1}S_r$。

时间限制:$2\mathtt{s}$

空间限制:$512\mathtt{MB}$

样例数据

样例数据