题解 P1385 【密令】

· · 题解

数论题与DP结合应该是很常见了，尤其是背包问题，经常可以换汤不换药的考很多种题目。。

本题一个最显著的特征就是：对于一个序列，不论你进行多少此操作，其字典序总和不变（因为操作会加一减一，抵消了），进一步推进的话，就会发现一个序列无论长成啥样都无所谓，因为答案只和他的字典序总和有关（因为你一定可以通过一系列操作将两个字典序和相同的字符串互换）

然后就不会了然后经我校背包大佬提醒，可以设f[i][j]为当有i个字符时，总和为j的种类数，因为j一定可以从一个比它小的数在加上一个字符转移过来，于是就有了一下这个式子：

f[i][j]={\sum \limits_{0<=k<26}f[i-1][j-k]}

其中k即为当前字符的字典序数（本蒟蒻一开始死套背包公式，用k<j导了半天）。

然后初始化的话也应该只标记0~25，因为一个字符的字典序数不会超过25（又被卡了很久(:з」∠)）

最后膜一下就可以啦！上丑陋的代码：

#include <iostream>
#define mo 1000000007
using namespace std;
int t;
string s;
long long f[110][5000];//前i个，和是j的种类数；类似背包选数 
int main()
{
    cin>>t;
    for (int i=0;i<26;i++) f[1][i]=1; //初始化的范围也应该只在(a~z)!! 
    for (int i=2;i<=100;i++)
    {
        f[i][0]=1;
        for (int j=1;j<=2700;j++)
            for (int k=0;k<26;k++) //每次修改只会增加1~26的值(a~z) 
                if (j-k>=0) f[i][j]=(f[i][j]%mo+f[i-1][j-k]%mo)%mo;
    }

    while (t--)
    {
        cin>>s; int sum=0;
        for (int i=0;i<s.size();i++) sum+=s[i]-'a';
        cout<<f[s.size()][sum]%mo-1<<endl;
    }
    return 0;
}

最后讲个鬼故事：此程序不知为何在我的电脑上跑的贼慢（3s）但lg上就100ms，废品店以旧换新了解一下。