0w1

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.

解法:
如果不考慮 T,我會做動態規劃,第二維表示當前變化量總和,最後要有變化量總和 0,但這方法會依賴 S。
仔細想想,其實就是要字符總和相同的字串,因此就只須依賴 S 的字符總和。
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;
}