CF666C Codeword 組合數

2022-09-22 21:55:00 字數 897 閱讀 8936

戳這裡

\(o(n^2)\) 的 dp ,\(f[i][j]=f[i-1][j-1]+f[i][j-1]*25\)

我們發現 dp 方程與原串的形態無關,然後觀察(題解) 式子,發現它可以通過組合數優化

\(f_=c_^\times 25^+c_i^\times 26\)

這個遞推式的含義就是:

前 \(j-1\) 位匹配上了原來 \(i-1\) 個,為了避免算重,每一位的取值不能等於下一個要匹配的數,所以取值種類有 25 種,空餘位置有 \(j-i\) 個

前 \(j-1\) 位匹配完了,之後隨意取

然後我們對於長度對應的答案進行記憶化,由於不同長度的串的種類數最多隻有 \(\sqrt\) 種,所以複雜度是 \(o(n\sqrt)\)

#includeusing namespace std;

namespace zzc

while (isdigit(ch))

return x*f; }

const int maxn = 1e5+5;

const int mod = 1e9+7;

char ch[maxn];

vectorf[maxn];

int fac[maxn],inv[maxn],pw[maxn];

bool vis[maxn];

int n,len;

void init()

long long c(long long n,long long m)

void solve()

printf("%d\n",f[len][read()]%mod); }

void work()

else solve();

} }}int main()

CF666C Codeword 結論題 暴力

題意 一開始有一個字串s,有m個事件,每個事件形如 1 用一個新的字串t來替換s 2 給出n,問有多少個長度為n的小寫字母組成的字串滿足包含s作為其一個子序列?答案 mod 10 9 7 m n sum t le 10 5 題解 有一個結論 答案只與n和 s 有關,與s到底是什麼無關。我們只考...