string-j9国际

1630: string

时间限制: 2000 ms  内存限制: 512 MB
提交: 1  解决: 1
[提交][状态][讨论版]

题目描述

于一个长度 为 $n$ 的串, 有 $2^n$ 个子序列 (包括空串), 但有些是相同的, 例如 "abb" 只有 6 种不同的子序列: ""(空串), "a", "b", "ab", "bb", "abb".

现有 $n$ 个仅包含小写字母的串, 有 $n!$ 种不同的方法把他们拼接在一起, 求其中多少种拼接方法使得得到的串的不同的子序列个数是偶数个.

输入

第一行一个整数 $n$.

接下来 $n$ 行, 每行一个字符串表示 $s_i$.

  • $1\le n\le 20$
  • $\sum_{i=1}^n |s_i| \le 10^5$

输出

一行一个整数, 表示答案

样例输入

3
a
a
baa

样例输出

4

提示

按 "a","a","baa" 拼接有 14 各不同的子序列, "a","baa","a" 有 13 个, "baa","a","a" 有 10 个.

来源

2022-cccc-xtsc

[提交][状态][讨论版]