题解 P4925 【[1007]Scarlet的字符串不可能这么可爱】

· · 题解

题目其实不难……赛场上手推了一下居然推出来了

首先很明显地，指定字符的位置和值都没有用……

也就是说，w这个变量可以直接扔掉了……至于s，我们只需要用它是不是正的

接下来开始推吧……

假设字符集大小为4，长度为5，如果没有限制的话，很明显，答案为4*3*2*2*2=96，因为我们要求一个没有回文串的字符串，所以一个位置会对后面两位进行限制，也就是说第一位可以用k种，但是第二位就会因为前面一个位置的限制而少掉1种字符的使用，然后从第三位开始一直是k-2种了。

至此我们得出结论，当s==0，k>=2、l>=2时，ans=k*(k-1)*(k-2)^{l-2}（当然，0^0还是不行滴）

如果指定字符呢？其实也没有什么大不了的，在前面我们可以发现每一个字符会对后两位进行限制，那么这个指定的字符只是会对前后两位有限制，

比如上方原本的例子，原来是4*3*2*2*2，我们可以先假设它限制的是1~5中的一位，再进行计算，结果如下

第一位：X*3*2*2*2

第二位：3*X*2*2*2

第三位：3*2*X*2*2

而第四第五种事实上是等价于第一第二种的，由此我们得出结论，在有限制条件的情况下，ans=(k-1)*(k-2)^{l-2}

那么我们只需要判断有没有限制字符，再直接计算即可，值得注意的是，我们这里需要用到快速幂，且一开始就需要对k取余，否则就会WA掉。

（注：证明过程可能不严谨，这里只是给出了我自己在推结论时的思路，仅供参考）

具体实现见代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll k,l,Mod,s,w,ans=1;
ll poww(ll a,ll b)//快速幂
{
    ll sum=1;
    a%=Mod;
    while(b!=0)
    {
        if(b&1!=0) sum=sum*a%Mod;
        b=b >> 1;
        a=a*a%Mod;
    }
    return sum;
}
int main()
{
    scanf("%lld %lld %lld %lld %lld",&k,&l,&Mod,&s,&w);
    k%=Mod;//先膜为敬
    if(l==1)//特判特殊情况
    {
        if(s) printf("1");
        else printf("%lld",k);
    }
    if(s) ans=ans*(k-1)%Mod;
    else ans=ans*k*(k-1)%Mod;//根据有没有指定字符进行分别计算
    k-=2;
    ans=(ans*poww(k,l-2))%Mod;
    printf("%lld",ans);//输出答案
    return 0;
}