自动搬运

查看原文

来自洛谷，原作者为

	VenusM1nT 醉后不知天在水 满船清梦压星河 | 明日方舟群 348956527

搬运于2025-08-24 22:05:19，当前版本为作者最后更新于2018-10-11 07:36:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

也就是说，$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;
}