题目描述

Scarlet妄图构造字符集为kkk，长度为LLL的字符串，满足没有任何一个长度超过111的回文连续子串。

看起来这样的字符串太多了，Scarlet随手加了个限制：她指定了字符串的第sss位为www。

这下Scarlet不会做了，请你来帮她计算究竟有多少满足条件的字符串。按照套路，你只要求出答案对ppp取模后的结果。

输入格式

第一行三个整数k,Lk,Lk,L和ppp，分别表示构造的字符串的的字符集、长度和模数。

第二行两个整数s,ws,ws,w，描述Scarlet给的限制。

注意：s=0s=0s=0表示该数据点中Scarlet十分良心地没有添加限制

输出格式

一行一个整数，表示答案对ppp的取模后的结果。

输入输出样例

输入 #1

3 3 2331 1

输出 #1

2

【解题思路】

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

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

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

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

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

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

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

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

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

注意：由于粘贴的问题每串字符会重复三次，影响阅读体验

【code】

1 #include
     
       2 #define ll long long 3 using namespace std; 4 ll k,l,Mod,s,w,ans=1; 5 ll poww(ll a,ll b)//快速幂 6 { 7     ll sum=1; 8     a%=Mod; 9     while(b!=0)10     {11         if(b&1!=0) sum=sum*a%Mod;12         b=b >> 1;13         a=a*a%Mod;14     }15     return sum;16 }17 int main()18 {19     scanf("%lld %lld %lld %lld %lld",&k,&l,&Mod,&s,&w);20     k%=Mod;//先膜为敬21     if(l==1)//特判特殊情况22     {23         if(s) printf("1");24         else printf("%lld",k);25     }26     if(s) ans=ans*(k-1)%Mod;27     else ans=ans*k*(k-1)%Mod;//根据有没有指定字符进行分别计算28     k-=2;29     ans=(ans*poww(k,l-2))%Mod;30     printf("%lld",ans);//输出答案31     return 0;32 }