# CFR 156 C. Cipher ( DP )

Problem - 156C - Codeforces

T 筆測資。每次給一個字串。有一種操作可以進行：選取兩個不同位置的字符，一個變成字典序小一的字符，另一個變成字典序大一的字符。特別的，a 沒有字典序小一的字符，z 沒有字典序大一的字符，而沒有相應的字符就不能進行該操作。求存在幾種字串，是給定的字串操作至少一次可以達到的。輸出方案數對 1e9 + 7 取模。

The input data contains several tests. The first line contains the only integer t (1 ≤ t ≤ 1e4) — the number of tests.
Next t lines contain the words, one per line. Each word consists of lowercase Latin letters and has length from 1 to 100, inclusive. Lengths of words can differ.

dp[ i ][ j ] : 已考慮前 i 個字符，當前的字符總和為 j，此時的方案數。

O( T * | S | + SIGMA * | S |^2 ) / O( SIGMA * | S |^2 )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
const int MOD = ( int ) 1e9 + 7;

int dp[ MAXN + 1 ][ 25 * MAXN + 1 ];

signed main(){
{
dp[ 0 ][ 0 ] = 1;
for( int i = 0; i < MAXN; ++i ){
for( int j = 0; j <= 25 * i; ++j ){
for( int k = 0; k < 26; ++k ){
( dp[ i + 1 ][ j + k ] += dp[ i ][ j ] ) %= MOD;
}
}
}
}
ios::sync_with_stdio( 0 );
int T; cin >> T;
for( int ti = 0; ti < T; ++ti ){
string seq; cin >> seq;
int sum = 0;
for( int i = 0; i < seq.size(); ++i ){
sum += seq[ i ] - 'a';
}
cout << dp[ seq.size() ][ sum ] - 1 << "\n";
}
return 0;
}
```