CFR 156 C. Cipher ( DP )
題意:
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; }