历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

洛谷 4-6. [CSP-J2019 江西] 非回文串原题链接中等

作者：

Amari0613 , 2024-10-03 17:24:08 , 所有人可见 , 阅读 25

题目描述

[CSP-J2019 江西] 非回文串

题目描述

Alice 有 $n$ 个字符，它们都是英文小写字母，从 $1 \sim n$ 编号，分别为 $c_1,c_2, \dots , c_n$。
Bob 准备将这些字符重新排列，组成一个字符串 $S$。Bob 知道 Alice 有强迫症，所以他打算将 $S$ 组成一个非回文串来折磨 Alice。

现在 Bob 想知道他共有多少种不同的排列字符的方案，能使得 $S$ 是个非回文串。一种排列字符的方案指的是一个 $1 \sim n$ 的排列 $p_i$，它所组成的 $S = c_{p_1}c_{p_2} \dots c_{p_n}$。

一个字符串是非回文串，当且仅当它的逆序串与原串不同。例如 abcda 的逆序串为 adcba，与原串不同，故 abcda 是非回文串。而 abcba 的逆序串与原串相同，是回文串。

由于最后的结果可能很大，你只需要告诉 Bob 总方案数对 $10^9+7$ 取模后的值。

输入格式

第一行一个正整数 $n$ 表示字符个数。
第二行 $n$ 个英文小写字母 $c_i$。

输出格式

仅一行一个整数表示答案。答案对 $10^9+7$ 取模。

样例 #1

样例输入 #1

3
aba

样例输出 #1

样例 #2

样例输入 #2

8
aabbbbcc

样例输出 #2

提示

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

思路：

对于这题，我们先假设相同字符是相同的。(相同字符之间不存在先后顺序）

则可以求出所有能构成字符串个数 res1（结合前置芝士）。

正难则反，我们可以求出能构成回文串的个数res2。

接下来是如何求解res2:

n 为奇数且出现个数为奇数的字符不止一个或 n 为偶数且并不是全部字符出现个数为偶数时，res2=0。
如果不满足上面情况，则说明一定存在回文串。根据回文串的对称性，我们可以通过确定字符串的前半部分的状态，以此确定后半部分。而确定前半部分状态不存在任何限制，使用前置芝士即可求出 res2。
则在相同字符相同前提下的答案为 res1−res2res1−res2。

最后记得给相同字符全排列，最终答案为 (res1−res2)×∏(字母a…c出现个数)!(res1−res2)×∏(字母a…c出现个数)!。

时间复杂度 O(n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int s[26];
int fac(int n){
    long long cnt=1;
    for(int i=1;i<=n;i++)cnt=(cnt*i)%mod;
    return cnt;
}
int fact(int n){
    long long cnt=1;
    for(int i=n/2+1;i<=n;i++)cnt=(cnt*i)%mod;
    return cnt;
}
signed main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        char x;cin>>x;
        s[x-'a']++;
    }
    int cnt=0,ans=fac(n);
    for(int i=0;i<26;i++)if(s[i]%2==1)cnt++;
    if(cnt>1){
        cout<<ans;return 0;}
    else{
        long long cnt2=1;
        for(int i=0;i<26;i++)cnt2=(cnt2*fact(s[i]))%mod;
        cnt2=cnt2*fac(n/2)%mod;
        cout<<(ans-cnt2+mod)%mod;

    }
    return 0; 
}

T4 P5684 [CSP-J2019 江西] 非回文串

发现正向构造非回文串较复杂，于是考虑先计算全排列数量，再减去回文情况。记得及时取模，以及乘法逆元的运用

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int maxn=2005;
ll n;
string s;
ll c[maxn];
ll f[maxn];
void init(){
    f[0]=1;
    for(int i=1;i<maxn;i++) f[i]=f[i-1]*i,f[i]%=MOD;
}
ll Pow(ll a,ll b){
    ll Base=a;
    ll Re=1;
    while(b){
        if(b&1){
            Re*=Base;
            Re%=MOD;
        }
        Base*=Base;
        Base%=MOD;
        b>>=1;
    }
    return Re;
} 
int main(){
    init();
    cin >> n;
    cin >> s;
    for(int i=0;i<n;i++){
        c[s[i]-'a'+1]++; 
    }
    ll Base=f[n];
    bool flag=!(n%2);
    ll Dt=f[n/2];
    for(int i=1;i<=26;i++){
        if(c[i]%2==1){
            if(flag){
                cout << Base;
                return 0;
            }       
            flag=true;
        }   
        Dt*=f[c[i]];
        Dt%=MOD;
        Dt*=Pow(f[c[i]/2],MOD-2);
        Dt%=MOD;
    }
    cout << ((Base-Dt)%MOD+MOD)%MOD;
    return 0;
}

或这个代码

include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;
const long long MOD = 1000000007LL;
typedef long long ll;
void gcd(ll a , ll b , ll &d , ll &x , ll &y) {
    if(!b) {d = a; x = 1; y = 0;}
    else { gcd(b , a%b,d,y , x); y -= x * (a/b); }
}
ll inv(ll a , ll n) {
    ll d , x , y;
    gcd(a , n , d,  x , y);
    return d == 1 ? (x+n)%n : -1;
}
ll f[maxn];
int n, cnt[26];
string s;
void init() {
    f[0] = 1;
    for (int i = 1; i < maxn; i ++) f[i] = f[i-1] * i % MOD;
}
ll C(int n, int m) {
    ll res = f[n];
    res = res * inv(f[n-m], MOD) % MOD;
    res = res * inv(f[m], MOD) % MOD;
    return res;
}
int main() {
    init();
    cin >> n >> s;
    for (int i = 0; i < n; i ++) cnt[s[i] - 'a'] ++;
    int cc = 0;
    for (int i = 0; i < 26; i ++) if (cnt[i]%2) cc ++;
    if (cc > 1) {
        cout << f[n] << endl;
        return 0;
    }
    ll tmp = f[n/2];
    for (int i = 0; i < 26; i ++) if (cnt[i]) {
        tmp = tmp * C(cnt[i], cnt[i]/2) % MOD;
        tmp = tmp * f[cnt[i] - cnt[i]/2] % MOD;
    }
    cout << (f[n] - tmp + MOD) % MOD << endl;
    return 0;
}

jx重考的题有点小水，连wjy(格林集团董事长（今日头条）)这样的蒟蒻都能AK，于是我就心血来潮骑它去赶集写一篇题解。

对于这题我们可以先求出所有字母全排列有多少种不同的方案。

这么一来非回文的方案数就是总方案数减去回文的方案数。

然后我们就可以开心的桶排，先判断他们能不能回文。如果不能回文直接输出总方案数就行了。

如果有回文，我们就可以先把奇数个的一个放在真中央，然后把他的个数减去1。

然后把所有剩下的字母个数除以2(因为如果回文左边确定了，右边也确定了，所以只考虑左边就可以了)。

然后根据我们认真的复习了初赛知识点得知。

设每个字母有ai个。
那么方案数就是:
(a1+a2……+an)!/a1!a2!a3!……*an!
由于字母原本的下标不同算不同的方案。

所以还要乘以每个字母个数的全排列个数（是总共的个数）

然后一减再逆元取模了

注意事项&常见错误原因
WA on #2，#8，请注意你的公式是不是写错了。
大红大紫，请注意你的模数是不是没有初始化，另外看看数组为了节省而开小了一个。
WA on #3，#5，#6，#7，#9，这个没有别的方法，只能把公式分开写，放在一起会导致溢出。
对于逆元的解决，只需在纸上写一下，就能发现可以约分，还是一个连乘，具体见代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int s[26];
int fac(int n){
    long long cnt=1;
    for(int i=1;i<=n;i++)cnt=(cnt*i)%mod;
    return cnt;
}
int fact(int n){
    long long cnt=1;
    for(int i=n/2+1;i<=n;i++)cnt=(cnt*i)%mod;
    return cnt;
}
signed main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        char x;cin>>x;
        s[x-'a']++;
    }
    int cnt=0,ans=fac(n);
    for(int i=0;i<26;i++)if(s[i]%2==1)cnt++;
    if(cnt>1){
        cout<<ans;return 0;}
    else{
        long long cnt2=1;
        for(int i=0;i<26;i++)cnt2=(cnt2*fact(s[i]))%mod;
        cnt2=cnt2*fac(n/2)%mod;
        cout<<(ans-cnt2+mod)%mod;

    }
    return 0; 
}

一些说明
因为代码中涉及到除法取模，所以需要用到扩展欧几里得算法来实现求逆，代码实现中的 gcd 函数是扩展欧几里得，inv 函数用于求解 a 在模 n 条件下的逆。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;
const long long MOD = 1000000007LL;
typedef long long ll;
void gcd(ll a , ll b , ll &d , ll &x , ll &y) {
    if(!b) {d = a; x = 1; y = 0;}
    else { gcd(b , a%b,d,y , x); y -= x * (a/b); }
}
ll inv(ll a , ll n) {
    ll d , x , y;
    gcd(a , n , d,  x , y);
    return d == 1 ? (x+n)%n : -1;
}
ll f[maxn];
int n, cnt[26];
string s;
void init() {
    f[0] = 1;
    for (int i = 1; i < maxn; i ++) f[i] = f[i-1] * i % MOD;
}
ll C(int n, int m) {
    ll res = f[n];
    res = res * inv(f[n-m], MOD) % MOD;
    res = res * inv(f[m], MOD) % MOD;
    return res;
}
int main() {
    init();
    cin >> n >> s;
    for (int i = 0; i < n; i ++) cnt[s[i] - 'a'] ++;
    int cc = 0;
    for (int i = 0; i < 26; i ++) if (cnt[i]%2) cc ++;
    if (cc > 1) {
        cout << f[n] << endl;
        return 0;
    }
    ll tmp = f[n/2];
    for (int i = 0; i < 26; i ++) if (cnt[i]) {
        tmp = tmp * C(cnt[i], cnt[i]/2) % MOD;
        tmp = tmp * f[cnt[i] - cnt[i]/2] % MOD;
    }
    cout << (f[n] - tmp + MOD) % MOD << endl;
    return 0;
}

T4 P5684 [CSP-J2019 江西] 非回文串

发现正向构造非回文串较复杂，于是考虑先计算全排列数量，再减去回文情况。记得及时取模，以及乘法逆元的运用

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int maxn=2005;
ll n;
string s;
ll c[maxn];
ll f[maxn];
void init(){
    f[0]=1;
    for(int i=1;i<maxn;i++) f[i]=f[i-1]*i,f[i]%=MOD;
}
ll Pow(ll a,ll b){
    ll Base=a;
    ll Re=1;
    while(b){
        if(b&1){
            Re*=Base;
            Re%=MOD;
        }
        Base*=Base;
        Base%=MOD;
        b>>=1;
    }
    return Re;
} 
int main(){
    init();
    cin >> n;
    cin >> s;
    for(int i=0;i<n;i++){
        c[s[i]-'a'+1]++; 
    }
    ll Base=f[n];
    bool flag=!(n%2);
    ll Dt=f[n/2];
    for(int i=1;i<=26;i++){
        if(c[i]%2==1){
            if(flag){
                cout << Base;
                return 0;
            }       
            flag=true;
        }   
        Dt*=f[c[i]];
        Dt%=MOD;
        Dt*=Pow(f[c[i]/2],MOD-2);
        Dt%=MOD;
    }
    cout << ((Base-Dt)%MOD+MOD)%MOD;
    return 0;
}

接下来来自洛谷网友QwQ~~

https://www.luogu.com.cn/article/eghgdgs0

个人认为这道题和道路拆除P5683比较有思维难度，道路拆除的题解已经写过了，好了现在进入正题。

思路：还是正难则反，非回文串不是太好求，所以我们可以用总的方案数减去回文串的数量不就行了吗？

总方案数很好求就是
n!，那回文串的数量怎么求呢？

我们想回文串肯定是对称的，所以每个字母都应该是偶数个，特殊情况下最多只能有一个字母的数量是奇数个，否则就不能组成回文串，直接输出总方案数就行了。

所以我们可以预处理出每个字母出现的个数
sum[i]表示，如果有一个字母的数量是奇数，
sum[i]−−就行了，因为那一个字母必然在中间。

好了，现在还有一个问题，回文串的数量怎么求呢，先来看一张图：

code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int n,sum[30],s;
ll jc[2010],ans = 1;
char a[2010];
bool f;
ll q_pow(ll x,ll y)//用费马小定理求逆元，要用到快速幂。 
{
    ll ans = 1;
    while(y)
    {
        if(y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}
void getjc()//可以预处理出阶乘数组。 
{
    jc[0] = 1;
    for(int i = 1;i <= n;i++) jc[i] = (ll)jc[i - 1] * i % mod;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",a + 1);
    getjc();
    for(int i = 1;i <= n;i++)
    sum[a[i] - 'a' + 1]++;//预处理出每个字母出现的个数。 
    for(int i = 1;i <= 26;i++)
    if(sum[i] != 0 && sum[i] % 2)//统计有没有奇数个字母。 
    {
        if(f)//如果数量还>1，一定没法组成回文串，直接输出n!。 
        {
            printf("%lld",jc[n]);
            return 0;
        } 
        f = 1;
        s = sum[i]--;//字母奇数个出现的次数-1，因为那一个字母只能放到中间。 
    }
    for(int i = 1;i <= 26;i++)//求A要用到逆元。 
    {
        if(!sum[i]) continue;
        ans *= (ll)jc[sum[i]] * q_pow(jc[sum[i] / 2],mod - 2) % mod;//逆元。 
        ans %= mod;
    }
    ans = ans * jc[n / 2] % mod;//公式。 
    if(f) ans = ans * s % mod;//如果有奇数别忘了乘nx，也就是s。 
    ans = jc[n] - ans;
    if(ans < 0) ans += mod;//这里要注意，ans有可能是负数。 
    printf("%lld",ans);
    return 0;
}

/管理员大大不求过，thanks/

重要提醒：

逆元可以线性O（n）求

啊啊啊，我封了
不懂A和C，但是懂WA

继续偷题解

一些说明
因为代码中涉及到除法取模，所以需要用到扩展欧几里得算法来实现求逆，代码实现中的 gcd 函数是扩展欧几里得，inv 函数用于求解 a 在模 n 条件下的逆。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;
const long long MOD = 1000000007LL;
typedef long long ll;
void gcd(ll a , ll b , ll &d , ll &x , ll &y) {
    if(!b) {d = a; x = 1; y = 0;}
    else { gcd(b , a%b,d,y , x); y -= x * (a/b); }
}
ll inv(ll a , ll n) {
    ll d , x , y;
    gcd(a , n , d,  x , y);
    return d == 1 ? (x+n)%n : -1;
}
ll f[maxn];
int n, cnt[26];
string s;
void init() {
    f[0] = 1;
    for (int i = 1; i < maxn; i ++) f[i] = f[i-1] * i % MOD;
}
ll C(int n, int m) {
    ll res = f[n];
    res = res * inv(f[n-m], MOD) % MOD;
    res = res * inv(f[m], MOD) % MOD;
    return res;
}
int main() {
    init();
    cin >> n >> s;
    for (int i = 0; i < n; i ++) cnt[s[i] - 'a'] ++;
    int cc = 0;
    for (int i = 0; i < 26; i ++) if (cnt[i]%2) cc ++;
    if (cc > 1) {
        cout << f[n] << endl;
        return 0;
    }
    ll tmp = f[n/2];
    for (int i = 0; i < 26; i ++) if (cnt[i]) {
        tmp = tmp * C(cnt[i], cnt[i]/2) % MOD;
        tmp = tmp * f[cnt[i] - cnt[i]/2] % MOD;
    }
    cout << (f[n] - tmp + MOD) % MOD << endl;
    return 0;
}

我是丑恶的分割线

okokok了

题解写完了

十分建议收藏QwQ

大佬们点个赞再走可以吗QwQ~~

0 评论

App 内打开

洛谷 4-6. [CSP-J2019 江西] 非回文串 原题链接 中等

题目描述

[CSP-J2019 江西] 非回文串

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

重要提醒：

逆元可以线性O（n）求

0 评论

洛谷 4-6. [CSP-J2019 江西] 非回文串原题链接中等