PASSWORD1 Mật khẩu

Điểm: 1,50 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, PyPy, Python, Scratch

Link đề (bài 1):

https://www.chuyentin.pro/2022/10/e-thi-olympic-duyen-hai-bac-bo-khoi-11.html

Sample Input 1

9 5
m1i1s2y1o1u3
isyou

Sample Output 1

Sample Input 2

11 3
m1i1s2i1s2i1p2i1
isi

Sample Output 2

Bình luận

Dung2015

đã bình luận lúc 2, Tháng 11, 2025, 13:25

include <bits/stdc++.h>

using namespace std; using int64 = long long; const int64 MOD = 1000000007;

int64 modpow(int64 a, int64 e){ int64 r = 1; while(e){ if(e&1) r = (ra)%MOD; a = (aa)%MOD; e >>= 1; } return r; }

int main(){ ios::syncwithstdio(false); cin.tie(nullptr); long long n; int m; if(!(cin >> n >> m)) return 0; string TE, P; cin >> TE >> P;

// Parse TE: sequence of (char, count)
vector&lt;pair&lt;char, long long>> runs;
int i = 0;
while(i < (int)TE.size()){
    char c = TE[i++];
    long long num = 0;
    if(i >= (int)TE.size()){
        // malformed but ignore
        break;
    }
    while(i < (int)TE.size() && isdigit((unsigned char)TE[i])){
        num = num*10 + (TE[i]-'0');
        ++i;
    }
    runs.emplace_back(c, num);
}

// Precompute factorials and invfactorials up to m
vector<int64> fact(m+1,1), invfact(m+1,1);
for(int j=1;j<=m;++j) fact[j] = fact[j-1]*j % MOD;
invfact[m] = modpow(fact[m], MOD-2);
for(int j=m;j>0;--j) invfact[j-1] = invfact[j]*j % MOD;

auto comb = [&](long long L, int t)->int64{
    if(t == 0) return 1;
    if(t < 0) return 0;
    // compute C(L, t) = L*(L-1)*...*(L-t+1) / t!
    int64 num = 1;
    for(int k=0;k&lt;t;++k){
        long long term = (L - k) % MOD;
        if(term < 0) term += MOD;
        num = (num * term) % MOD;
    }
    num = num * invfact[t] % MOD;
    return num;
};

// Precompute maximum run of identical chars in P starting at each position
// P is length m
vector<int> sameLen(m+1, 0); // sameLen[pos] = length of consecutive same char starting at pos (0-based). sameLen[m] = 0
for(int pos = m-1; pos >= 0; --pos){
    if(pos+1 < m && P[pos] == P[pos+1]) sameLen[pos] = sameLen[pos+1] + 1;
    else sameLen[pos] = 1;
}

// dp[j] = number of ways to match first j chars of P (j from 0..m)
vector<int64> dp(m+1, 0), dpNew(m+1,0);
dp[0] = 1;

for(auto &pr : runs){
    char c = pr.first;
    long long L = pr.second;
    fill(dpNew.begin(), dpNew.end(), 0);
    for(int pref = 0; pref <= m; ++pref){
        if(dp[pref] == 0) continue;
        // from prefix length = pref, we may match t next characters if P[pref..pref+t-1] all == c
        if(pref == m){
            // already full matched, only t=0 option
            dpNew[pref] = (dpNew[pref] + dp[pref]) % MOD;
            continue;
        }
        if(P[pref] != c){
            // cannot extend, only t = 0
            dpNew[pref] = (dpNew[pref] + dp[pref]) % MOD;
        } else {
            int maxConsec = sameLen[pref]; // >=1
            int maxT = min<int>(maxConsec, m - pref);
            // also limited by L
            if(L < maxT) maxT = (int)L;
            // t = 0..maxT
            for(int t = 0; t <= maxT; ++t){
                int idx = pref + t;
                int64 ways = comb(L, t);
                dpNew[idx] = (dpNew[idx] + dp[pref] * ways) % MOD;
            }
        }
    }
    dp.swap(dpNew);
}

cout << dp[m] % MOD << "\n";
return 0;

}