【CSP-J2019 江西】非回文串

【CSP-J2019 江西】非回文串

NOIP 专栏：CSP-J 2019 江西
算法竞赛：数学，组合数学，组合计数，排列组合，全排列，不可重复的排列，字符串，传统题（标准 OI）
题目链接：

题目描述：
Alice 有 n n n 个字符，它们都是英文小写字母，从 1 ∼ n 1 \sim n 1∼n 编号，分别为 c 1 , c 2 , … , c n c_1,c_2, \dots , c_n c1​,c2​,…,cn​。
Bob 准备将这些字符重新排列，组成一个字符串 S S S。Bob 知道 Alice 有强迫症，所以他打算将 S S S 组成一个非回文串来折磨 Alice。
现在 Bob 想知道他共有多少种不同的排列字符的方案，能使得 S S S 是个非回文串。一种排列字符的方案指的是一个 1 ∼ n 1 \sim n 1∼n 的排列 p i p_i pi​，它所组成的 S

c p 1 c p 2 … c p n S = c_{p_1}c_{p_2} \dots c_{p_n} S=cp1​​cp2​​…cpn​​。
一个字符串是非回文串，当且仅当它的逆序串与原串不同。例如 abcda 的逆序串为 adcba，与原串不同，故 abcda 是非回文串。而 abcba 的逆序串与原串相同，是回文串。
由于最后的结果可能很大，你只需要告诉 Bob 总方案数对 1 0 9 + 7 10^9+7 109+7 取模后的值。

输入格式：
第一行一个正整数 n n n 表示字符个数。
第二行 n n n 个英文小写字母 c i c_i ci​。
输出格式：
仅一行一个整数表示答案。答案对 1 0 9 + 7 10^9+7 109+7 取模。

数据范围：
对于 20 % 20% 20% 的数据， n ≤ 8 n \le 8 n≤8；
对于 50 % 50% 50% 的数据， n ≤ 20 n \le 20 n≤20；
另有 30 % 30% 30% 的数据，字符只包含 a 和 b；
对于 100 % 100% 100% 的数据， 3 ≤ n ≤ 2000 3 \le n \le 2000 3≤n≤2000。

题目分析

给定一个长度为 n n n 的仅由小写字母构成的字符串 S [ 1 ∼ n ] S[1\sim n] S[1∼n]，求出字符串 S [ 1 ∼ n ] S[1\sim n] S[1∼n] 的排列中不为回文串的数量。

回文串即左右字符成轴对称的字符串，如 abbccbba,acbca 为回文串，aabbcc,abcabc 不是回文串。

注意：不同位置的相同字母的编号不同，如 aba 的回文串有两个，即 a 1 b a 2 , a 2 b a 1 a_1ba_2,a_2ba_1 a1​ba2​,a2​ba1​。

算法知识

1. 全排列，无重复排列
2. 快速幂
3. 费马小定理（逆元）
4. 模运算

排列组合

（1）排列概念

这里用到组合数学中的排列（全排列，无重复排列）。

排列（permutation），即从 n n n 个不同的元素中，任取 m , ( m ≤ n ) m,(m\le n) m,(m≤n) 个元素，按照一定的顺序排成一列，这就叫做从 n n n 个不同元素中取出 m m m 个元素的一个排列。特别地，当 m

n m=n m=n 时，这个排列被称作全排列（all permutation）。

排列根据元素的重复性要求可以分为两种，重复排列（permutation with repetition） 和 无重复排列（permutations without repeatable），通常来说，无重复排列使用频率较高，排列也常指无重复排列，在本文中，排列的讨论范围即无重复排列。

无重复排列（permutations without repeatable），即从 n n n 个不同的元素中，任取 m , ( m ≤ n ) m,(m\le n) m,(m≤n) 个不同的元素元素（即 n n n 个元素中的每一个元素至多被选一次），按照一定的顺序排成一列，这就叫做从 n n n 个不同元素中取出 m m m 个不同元素的一个排列。

从 n n n 个不同元素中取出 m m m 个不同元素的所有不同排列（无重复排列）的个数称为排列种数或称排列数，记为 P n m P_n^m Pnm​ 或 A n m A_n^m Anm​ 或 n P m _nP_m n​Pm​。特殊的，全排列的个数记为 P n n P_n^n Pnn​ 或 A n n A_n^n Ann​ 或 P n P_n Pn​。

（2）排列数公式

选排列：

P n m

A n m

n ( n − 1 ) ( n − 2 ) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ( n − m + 1 )

n ! ( n − m ) ! P_n^m=A_n^m=n(n-1)(n-2)\cdot\cdot\cdot\cdot\cdot\cdot(n-m+1)=\frac{n!}{(n-m)!} Pnm​=Anm​=n(n−1)(n−2)⋅⋅⋅⋅⋅⋅(n−m+1)=(n−m)!n!​

全排列：

P n n

P n

n ( n − 1 ) ( n − 2 ) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 3 × 2 × 1

n ! P_n^n=P_n=n(n-1)(n-2)\cdot\cdot\cdot\cdot\cdot\cdot3\times2\times1=n! Pnn​=Pn​=n(n−1)(n−2)⋅⋅⋅⋅⋅⋅3×2×1=n!

证明也比较简单，组合与排列的基础就是乘法原理和加法原理，公式也就是根据定义得出的，将公式对应于定义（从集合中选数）不难理解。

算法思路

直接求不是回文串的排列数量不好求，可以间接地求，先求出全部排列的数量，再求出回文串的数量香煎即可，回文串的数量比较好求。

全部排列的数量不难得出即为 P n

n ! P_n=n! Pn​=n!，而回文串的排列数量分为以下几个步骤来求。

先统计一下每个字母出现的个数，如果出现奇数个的字母超过 1 1 1 个，则不存在回文串，否则就一定存在回文串（ n ≥ 3 n\ge 3 n≥3）。如果有 1 1 1 个字母 α \alpha α 出现的次数为基数，则 n n n 为奇数，且 S [ ⌈ x / 2 ⌉ ]

α S[\left \lceil x/2\right \rceil]=\alpha S[⌈x/2⌉]=α。

假设现在有一个回文串 S ′ S' S′，则形如 S ′ S' S′ 的回文串一共有 ∏ i

1 n s u m [ s [ i ] ] ! \prod_{i=1}^{n} sum[s[i]]! ∏i=1n​sum[s[i]]! 个， s u m [ α ] sum[\alpha] sum[α] 表示字母 α \alpha α 出现的次数。这个计算公式中的阶乘是字母的全排列数，因为每个字母可以到其他相同字母的位置，而这不改变字符串形式，如 a 1 b a 2 b a 3 , a 1 b a 3 b a 2 , a 2 b a 1 b a 3 , a 2 b a 3 b a 1 , a 3 b a 1 b a 2 , a 3 b a 2 b a 1 a_1ba_2ba_3,\hspace{1mm}a_1ba_3ba_2,\hspace{1mm}a_2ba_1ba_3,\hspace{1mm}a_2ba_3ba_1,\hspace{1mm}a_3ba_1ba_2,\hspace{1mm}a_3ba_2ba_1 a1​ba2​ba3​,a1​ba3​ba2​,a2​ba1​ba3​,a2​ba3​ba1​,a3​ba1​ba2​,a3​ba2​ba1​ 这些回文串；而连乘积符号表示不同字母间的关系为互不影响，相乘的关系（乘法原理），如 a 1 b 1 a 2 b 2 a 3 , a 1 b 1 a 3 b 2 a 2 , a 2 b 1 a 1 b 2 a 3 , a 2 b 1 a 3 b 2 a 1 , a 3 b 1 a 1 b 2 a 2 , a 3 b 1 a 2 b 2 a 1 , a 1 b 2 a 2 b 1 a 3 , a 1 b 2 a 3 b 1 a 2 , a 2 b 2 a 1 b 1 a 3 , a 2 b 2 a 3 b 1 a 1 , a 3 b 2 a 1 b 1 a 2 , a 3 b 2 a 2 b 1 a 1 a_1b_1a_2b_2a_3,\hspace{1mm}a_1b_1a_3b_2a_2,\hspace{1mm}a_2b_1a_1b_2a_3,\hspace{1mm}a_2b_1a_3b_2a_1,\hspace{1mm}a_3b_1a_1b_2a_2,\hspace{1mm}a_3b_1a_2b_2a_1,\hspace{3mm}a_1b_2a_2b_1a_3,\hspace{1mm}a_1b_2a_3b_1a_2,\hspace{1mm}a_2b_2a_1b_1a_3,\hspace{1mm}a_2b_2a_3b_1a_1,\hspace{1mm}a_3b_2a_1b_1a_2,\hspace{1mm}a_3b_2a_2b_1a_1 a1​b1​a2​b2​a3​,a1​b1​a3​b2​a2​,a2​b1​a1​b2​a3​,a2​b1​a3​b2​a1​,a3​b1​a1​b2​a2​,a3​b1​a2​b2​a1​,a1​b2​a2​b1​a3​,a1​b2​a3​b1​a2​,a2​b2​a1​b1​a3​,a2​b2​a3​b1​a1​,a3​b2​a1​b1​a2​,a3​b2​a2​b1​a1​

这些回文串。

上述是有一个形如 S ′ S' S′ 的回文串，求出相同形式的回文串的个数，那我们还需要知道有多少个不同形式的回文串，计算公式为

⌊ n / 2 ⌋ ! − ∏ i

1 n ⌊ s u m [ s [ i ] ] / 2 ⌋ ! \left \lfloor n/2 \right \rfloor ! - \prod_{i=1}^{n} \left \lfloor sum[s[i]]/2 \right \rfloor ! ⌊n/2⌋!−i=1∏n​⌊sum[s[i]]/2⌋!

⌊ n / 2 ⌋ \left \lfloor n/2 \right \rfloor ⌊n/2⌋ 表示字符串的一半边，由于字符串为回文串，则左右对称，确定了一半边后另一半边也就确定了，本文以左半边为例作为要确定的对象。

⌊ n / 2 ⌋ ! \left \lfloor n/2 \right \rfloor ! ⌊n/2⌋! 表示左半边的全排列数，这里必定存在一些回文串，先将每个字母平均地分到左右两边（奇数个数的除外，分 ⌊ s u m [ α ] ⌋ \left \lfloor sum[\alpha] \right \rfloor ⌊sum[α]⌋ 个到左边和右边），只有右边的字母对应着左边的字母排放即可形成回文串。左边的排列数有 ⌊ n / 2 ⌋ ! \left \lfloor n/2 \right \rfloor ! ⌊n/2⌋! 个，但是这些不全是不同形式的，可能存在相同形式，这就是要减去 ∏ i

1 n ⌊ s u m [ s [ i ] ] / 2 ⌋ ! \prod_{i=1}^{n} \left \lfloor sum[s[i]]/2 \right \rfloor ! ∏i=1n​⌊sum[s[i]]/2⌋! 的原因，具体细节与上文所述的求相同形式的回文串的个数个公式相似。

具体在求排列数（阶乘）时有一些相关的模运算，和逆元的应用，具体见下文代码。

AC Code

（1）Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010,mod = 1e9+7;
LL a[N];
string str;
map<char,int>mp;
void init(int n)
{
	a[0]=1;
	for (int i=1;i<=n;i++)
		a[i]=((LL)a[i-1]*i)%mod;
}
LL qmi(int a,int k)
{
	LL res=1;
	while (k)
	{
		if (k&1) res=res*a%mod;
		a=(LL)a*a%mod;
		k>>=1;
	}
	return res;
}
int main()
{
	int n,tot=0;
	cin>>n>>str;
	init(n);
	LL k=1;
	for (int i=0;i<n;i++)
		mp[str[i]]++;
	for (auto it=mp.begin();it!=mp.end();it++)
	{
		if (it->second&1) tot++;
		k=k*a[it->second/2]%mod;
	}
	LL ans=a[n],num=a[n/2]*qmi(k,mod-2)%mod;
	if (tot>1) printf("%lld",ans);
	else
	{
		for (auto it=mp.begin();it!=mp.end();it++)
            num=num*a[it->second]%mod;
		printf("%lld\n",(ans-num+mod)%mod);
	}
	return 0;
}

（2）一些细节

1、模运算的一些运算公式与法则不适用与除法，需要使用逆元，否则：

2、在有关模运算时，如用到减法，需要记得先加模数再取模，如 printf("%lld\n",(ans-num+mod)%mod);，否则：

END

感谢观看，如有问题欢迎指出。

更新日志

1. 2025/09/07 开始书写本篇 CSDN 博客，并完稿发布。