21冬基础营A：串 排列组合做法

link
这个乍一看梦回高中的排列之定序问题，但是由于这个不是排列有重复的情况，想去重的方法想了好久，最后发现还是求反情况再求补集靠谱QAQ
正难反易，我们去求反解：
当串长为n时：
首先，对于每一位如果我们假设被开除字母籍，不取s那么显然就没有us串 所以所以不含s的方案都是可行方案 就是pow(25,n) 种方案。
然后考虑取s的情况下，就不能有u位于s之前：用n=4来举例：
我们把第1，2，3，4位置分别取s的情况统计，（容易想到s会对前面的位置限制其不能取u，其他位取不取s的说法详情看下面）
考虑u不在s前面的情况，
@1:若s在最后一位显然前面三个都不能取u 则有 25*25*25*1= pow(25,n-1)个方案。
@2:s在倒数第二位前两个就不能取u 有25*25种前两位取法，而最后一位不考虑重复的情况下是26个字母都可以取，但是若取s则和上一种情况重合 so又是25*25*1*25 = pow(25,3)=25^(n-1)种方案。
@3:s in 倒数第三位（正数第二位）就有第一位25，而后两位若第三位取s则与@2重复，若末位取s则与@1相重复，so同上都不能取s 于是又是25*1*25*25 = 25^(n-1)种
@4:s in 第一位，后面三位避让上面重复情况，同样是1*25*25*25=pow(25,3)种方案。
所以所有反解nums = pow(25,3)*4+pow(25,4)种解法。
那么全集减去num集合=pow(26,n)- nums 就是正解了。
ps:取mod计算最后如果结果小于零不要怕只要再加个if(ans<0)ans+=mod就好了QAQ比赛的时候一直好多数据输出负数都给我搞破防了orz。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
ll mod = 1e9+7;
#define mp make_pair
ll pow25[1000100];
ll pow26[1000100];
void init(){
    pow25[0]=pow26[0]=1;
    for(int i=1;i<1000100;i++){
        pow25[i] =(pow25[i-1]*25)%mod;
        pow26[i]=(pow26[i-1]*26)%mod;
    }
}
ll mpow(int a,int b){
    if(a==25)return pow25[b];
    else return pow26[b];
}

ll solve(int n){
    if(n<=1)return 0;
    return mpow(26,n) -( mpow(25,n-1)*(25+n) )%mod;

}
int main()
{
    init();
    int n;
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=solve(i)%mod;
        ans%=mod;
    }
    if(ans<0)ans+=mod;
    cout<<ans;
    return 0;
}