列表

详情


DP61. 串

描述

长度不超过,且包含子序列“us”的、只由小写字母构成的字符串有多少个? 答案对取模。
所谓子序列,指一个字符串删除部分字符(也可以不删)得到的字符串。
例如,"unoacscc"包含子序列"us",但"scscucu"则不包含子序列"us"

输入描述

一个正整数

输出描述

一个正整数,为满足条件的字符串数量对取模的值

示例1

输入:

2

输出:

1

说明:

仅有“us”这一个字符串合法

示例2

输入:

3

输出:

77

说明:

长度为3的字符串里,
形状是"u?s"的共有26个
形状是"?us"的共有26个
形状是"us?"的共有26个。
但是,"uss"和"uus"被各多计算了1次,应该减去,
所以共有26*3-2=76个。
再加上长度为2的"us",所以长度不超过3的合法字符串共有77个。

示例3

输入:

874520

输出:

16471619

原站题解

C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2021-12-11

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll p(ll x, ll n)
{
	ll a = 1;
	while (n)
	{
		if (n&1)
			a = a*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return a;
}

ll d(ll n)
{
	return p(n, mod-2);
}

int main()
{
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	cout << (26*(p(26, n)-1+mod)%mod*d(25)%mod - 25*(p(25, n)-1+mod)%mod*d(24)%mod + ((p(25, n)-1+mod)%mod*d(24)%mod-n*p(25,n)%mod+mod)*d(24)%mod + mod)%mod<< endl;
	return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2021-12-21

#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f) 
{
    f=0;T fu=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-'){fu=-1;}c=getchar();}
    while(c>='0'&&c<='9') {f=(f<<3)+(f<<1)+(c&15);c=getchar();}
    f*=fu;
}
template <typename T>
void print(T x) 
{
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+48);
    else print(x/10),putchar(x%10+48);
}
template <typename T>
void print(T x, char t) 
{
    print(x);putchar(t);
}
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> PII;
const ll mod=1e9+7;
ll powmod(ll a,ll b)
{
    ll res=1;
    a%=mod;
    assert(b>=0);
    for(;b;b>>=1)
    {
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
ll _,n;
namespace linear_seq
{
    const int N=10010;
    ll res[N],base[N],_c[N],_md[N];
    std::vector<ll>Md;
    void mul(ll *a,ll *b,int k)
    {
        for(int i=0;i<k+k;i++)
            _c[i]=0;
        for(int i=0;i<k;i++)
            if(a[i])
                for(int j=0;j<k;j++)
                    _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
        for(int i=k+k-1;i>=k;i--)
            if(_c[i])
                for(int j=0;j<((int)(Md).size());j++)
                    _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
        for(int i=0;i<k;i++)
            a[i]=_c[i];
    }
    int solve(ll n,VI a,VI b)
    {
        ll ans=0,pnt=0;
        int k=((int)(a).size());
        assert(((int)(a).size())==((int)(b).size()));
        for(int i=0;i<k;i++)
            _md[k-1-i]=-a[i];
        _md[k]=1;
        Md.clear();
        for(int i=0;i<k;i++)
            if(_md[i]!=0)
                Md.push_back(i);
        for(int i=0;i<k;i++)
            res[i]=base[i]=0;
        res[0]=1;
        while((1ll<<pnt)<=n)
            pnt++;
        for(int p=pnt;p>=0;p--)
        {
            mul(res,res,k);
            if((n>>p)&1)
            {
                for(int i=k-1;i>=0;i--)
                    res[i+1]=res[i];
                res[0]=0;
                for(int j=0;j<((int)(Md).size());j++)
                    res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
            }
        }
        for(int i=0;i<k;i++)
            ans=(ans+res[i]*b[i])%mod;
        if(ans<0)
            ans+=mod;
        return ans;
    }
    VI BM(VI s)
    {
        VI C(1,1),B(1,1);
        int L=0,m=1,b=1;
        for(int n=0;n<((int)(s).size());n++)
        {
            ll d=0;
            for(int i=0;i<L+1;i++)
                d=(d+(ll)C[i]*s[n-i])%mod;
            if(d==0)
                ++m;
            else if(2*L<=n)
            {
                VI T=C;
                ll c=mod-d*powmod(b,mod-2)%mod;
                while(((int)(C).size())<((int)(B).size())+m)
                    C.push_back(0);
                for(int i=0;i<((int)(B).size());i++)
                    C[i+m]=(C[i+m]+c*B[i])%mod;
                L=n+1-L;
                B=T;
                b=d;
                m=1;
            }
            else
            {
                ll c=mod-d*powmod(b,mod-2)%mod;
                while(((int)(C).size())<((int)(B).size())+m)
                    C.push_back(0);
                for(int i=0;i<((int)(B).size());i++)
                    C[i+m]=(C[i+m]+c*B[i])%mod;
                ++m;
            }
        }
        return C;
    }
    int gao(VI a,ll n)
    {
        VI c=BM(a);
        c.erase(c.begin());
        for(int i=0;i<((int)(c).size());i++)
            c[i]=(mod-c[i])%mod;
        return solve(n,c,VI(a.begin(),a.begin()+((int)(c).size())));
    }
};
void solve()
{
    scanf("%lld",&n);
    vector<int>v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(77);
    v.push_back(3928);
    v.push_back(166554);
    v.push_back(6347955);
    v.push_back(225658131);
    v.push_back(636707033);
    printf("%lld",linear_seq::gao(v,n-1)%mod);
}
int main()
{
    #ifdef AC
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    clock_t program_start_clock=clock();
    solve();
    fprintf(stderr,"\nTotal Time: %lf ms",double(clock()-program_start_clock)/(CLOCKS_PER_SEC/1000));
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 496KB, 提交时间: 2022-05-08

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll p(ll x, ll n) {
    ll a = 1;
    while (n) {
        if (n & 1)
            a = a * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return a;
}
ll d(ll n) {
    return p(n, mod - 2);
}
int main() {
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    cout << (26 * (p(26, n) - 1 + mod) % mod * d(25) % mod - 25 * (p(25,
             n) - 1 + mod) % mod * d(24) % mod + ((p(25,
                     n) - 1 + mod) % mod * d(24) % mod - n * p(25,
                             n) % mod + mod)*d(24) % mod + mod) % mod << endl;
    return 0;
}

C 解法, 执行用时: 8ms, 内存消耗: 352KB, 提交时间: 2021-12-03

#include <stdio.h>

#define MOD (1000000000+7)

int main()
{
    int n;
    long long dp[1000001][3]={0};
    long long count = 0;
    scanf("%d",&n);
    dp[1][0]=25;
    dp[1][1]=1;
    dp[1][2]=0;
    for(int i=2;i<=n;++i)
    {
        dp[i][0] = (dp[i-1][0]*25)%MOD;
        dp[i][1] = (dp[i-1][0]+dp[i-1][1]*25)%MOD;
        dp[i][2] = (dp[i-1][1]+dp[i-1][2]*26)%MOD;
        count = (count + dp[i][2]) % MOD;
    }
    printf("%lld",count);
    return 0;
}

C++ 解法, 执行用时: 8ms, 内存消耗: 432KB, 提交时间: 2021-11-13

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
int dp[3];
int main()
{
    int n;
    int ans = 0;
    scanf("%d" , &n);
    dp[0] = 1;
    for(int i=1;i<=n;++i)
    {
        dp[2]=(1ll*dp[1]+26ll*dp[2])%MOD;
        dp[1]=(1ll*dp[0]+25ll*dp[1])%MOD;
        dp[0]=25ll*dp[0]%MOD;
        ans=(1ll*ans+dp[2])%MOD;
    }
    printf("%lld\n",ans);
}

上一题