DP 연습용 문제입니다.
출력은 문자열을 구성하는 문자 자체에는 관계 없이, 오직 문자열의 길이에 영향 받습니다.
본 문제는 앞에서부터 $i$번째 문자를 바꾼 횟수가 $a_i$일 때 $\displaystyle\sum_{i=1}^{l}a_i = s$를 만족하는 0 이상 25 이하의 정수 $a_1,a_2,a_3,\cdots,a_l$의 경우의 수를 구하는 것과 같습니다.
따라서, 길이가 $l$인 문자열을 바꾼 수의 합이 $s$가 되도록 하는 경우의 수를 1,000,000,007로 나눈 나머지를 $DP(l,s)$라 하면 다음의 식이 성립합니다.
\[DP(l,s) = \sum_{k=0}^{\min(25,s)} DP(l-1,s-k)\]또한 위 식을 만족하도록 $DP(0,k)$를 정의하면 $k=0$일 때 1, 그렇지 않을 때 0으로 정의할 수 있습니다.
이를 이용하여 코드를 작성하면 다음과 같습니다. 나머지 연산은 매우 무거운 연산이므로 아래의 코드는 TLE를 받습니다. 간단한 방법을 통해 실행시간을 개선할 수 있는데, 그 방법을 고민해보시길 바랍니다.
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod = 1e9+7;
string str;
ll s;
ll mem[3010][3010];
ll f(int p,int rem){
if(p==0)return !rem;
if(mem[p][rem]!=-1)return mem[p][rem];
ll &r = mem[p][rem];
r = 0;
for(int i=0;i<min(26,rem+1);i++){
r+=f(p-1,rem-i);
r%=mod;
}
return r;
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
memset(mem,-1,sizeof(mem));
cin>>s>>str;
cout<<f(str.size(),s)<<"\n";
}