自动搬运

查看原文

来自洛谷，原作者为

	天泽龟 理想与孤独 | My Blog: http://tzturtle.moe

搬运于2025-08-24 21:24:30，当前版本为作者最后更新于2018-10-23 01:16:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数论题与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，废品店以旧换新了解一下。