问题 B:奇妙的冒险
文件提交:无需freopen
内存限制:128 MB
时间限制:1.000 S
评测方式:普通裁判
命题人:
提交:2
解决:2
题目描述
在遥远的编程王国里,蒜头君是一位勇敢聪明的小探险家。今天,蒜头君收到了一份来自智慧老的神秘挑战:帮助计算蒜头岛上所有神奇植物的异同,以便更好地照顾它们。
蒜头岛上生长着 $n$ 棵神奇的二进制树,每棵树可以用一个由 $0$ 和 $1$ 组成的字符串来表示,这些字符串的长度都一样,就像是树木的高度一样整齐。现在,蒜头君需要了解这些树木之间的差异,以便找出最特别的那几棵进行深入研究。
蒜头君需要你帮忙计算,岛上 $n$ 棵二进制树两两之间的“不同点”总数。比如,如果两棵树在一个位置上的数字不同(一个是 $0$,另一个是 $1$),那么就算有一个不同点。我们的目标是算出所有树两两之间的不同点加超来的总数,由于答案可能过大,因此答案对 $10^9+7$ 取模。
举个例子,如果只有两棵树,一棵对是 $111$,另一棵是 $010$,那么它们之间有 $2$ 个不同的位置(第一位和第三位),所以这组的差异度就是 $2$
输入
第一行包含一个整数 $n$
接下来的 $n$ 行,每行输入一个由 $0$ 或 $1$ 组成的字符串
$1\le n\le 10^5$,每个字符串的长度不超过 $100$
输出
输出所有树两两之间不同点加起来的总数,由于答案可能过大,因此答案对 $10^9+7$ 取模
样例输入-1 复制
2
111
010
样例输出-1 复制
2
样例输入-2 复制
3
1001001100
0111001100
1111001101
样例输出-2 复制
8
提示
样例解释2:在第一个位置上,三棵对的表示分别为 $1,0,1$,其中第一棵树与第二棵树不同,第三棵树与第二棵树不同,因此在第一个位置上的总差异度为 $2$,依次类推,计算出最后的答案为 $8$