3653. 她的名字

10175101121

可直接暴力
不过要预处理 不然会超时

JamesHuang77

题目大意

题面有点难以理解,传送门

思路分析

我用的方法是组合数+预处理打表,直接暴力,DP没有想到
1. 题目要求后缀为XY,长度为N,因此要用到的组合数就是C(len,N-2),从长度为len的可选字符中选择n-2个字符与XY进行组合。
2. 然后对于给定的字符串S,求出后缀从00~99的所有长度的字符串个数,存入表中。
3. 要求结果即为res[l][t]

具体代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL; 

const int MAX_N=2e3+5;
const LL MOD=1e9+7;
int Q;
LL d[MAX_N][MAX_N]; // 存储组合数
LL res[MAX_N][105]; //打表,res[len][type]表示长度的len,结尾为type类型的个数
int dd[105]; //dd[i]表示当前遍历到的子字符串中,后缀为i(XY = i十进制)的个数
int main()
{
    string s;
    cin>>s;
    int n;
    n=s.length();
    d[0][0]=1;
    //打一个组合数的表,同时取摸
    for(int i=1;i<=n;++i)
    {
        d[i][0]=1;
        for(int j=1;j<=i;++j)
            d[i][j]=(d[i-1][j]+d[i-1][j-1])%MOD;
    }
    int t;
    //遍历字符串s
    for(int i=0;i<n-1;++i)
    {
        memset(dd,0,sizeof(dd));
        for(int j=i+1;j<n;++j)
        {
            t=(s[i]-'0')*10+s[j]-'0';
            ++dd[t];
        }
        //关键步骤,记录在字符串每个长度下,后缀从00~99的个数
        for(int j=0;j<=i;++j)
            for(int k=0;k<=99;++k)
                res[j+2][k]=(res[j+2][k]+d[i][j]*dd[k]%MOD)%MOD;
    }
    cin>>Q;
    int l;
    while(Q--){
        cin>>l>>t;
        if(l>n) cout<<0<<endl;
        else    cout<<res[l][t]<<endl;
    }

    return 0;
}
你当前正在回复 博客/题目
存在问题!