Türkçe

\(|\Sigma | = \mathbf{M}\) olmak üzere oluşturulacak dil \(L\)'de kullanılacak alfabeyi \(\Sigma = \{h_1,h_2,h_3,\dots,h_M\}\) şeklinde tanımlayabiliriz. \(1 \leq i \leq \mathbf{M}\) olmak üzere \(c_i\), \(h_i\) karakterinin dildeki herhangi bir sözcükte arka arkaya en fazla kaç kere gelebileceğini belirleyen kısıtlama olsun.

\(w \in L\), \(h_i\) ile biten, uzunluğu \(n\) olan bir sözcük ise \(w\) aşağıdaki şekillerde oluşturulabilir:

• \(h_i\) ile bitmeyen \(w_1 \in L \land |w_1|=(n-1)\) için; \(w_1h_i\)
• \(h_i\) ile bitmeyen \(w_2 \in L \land |w_2|=(n-2)\) için; \(w_2h_ih_i\)
• \(h_i\) ile bitmeyen \(w_3 \in L \land |w_3|=(n-3)\) için; \(w_3h_ih_ih_i\)

\(\qquad \qquad \vdots\)

• \(h_{c_i}\) ile bitmeyen \(w_{c_i} \in L \land |w_{c_i}|=(n-c_i)\) için; \(w_{c_i}h_i^{c_i}\)

Burada iki ayrıntıya dikkat etmek gerekiyor:

1. \(n\)'in \(c_i\)'ye göre büyüklüğü. Eğer \(n\) \(c_i\)'den daha küçükse uzunluğu 0'dan küçük bir sözcüğe yeterli miktarda \(h_i\) ekleyerek \(w\) sözcüklerinden birini türetmeye çalışmış oluruz. Bu yüzden yukarıdaki durumların hepsinde \(|w_i| \geq 0\) doğruluğundan emin olmamız gerekli. Ayrıca uzunluğu 0 olan biricik bir sözcük olduğunu kabul edebiliriz (empty string, \(e\)). \(n \leq c_i\) durumunda empty string'e \(n\) adet \(h_i\) ekleyerek \(w\) sözcüklerinden birini elde edebiliriz (\(eh_i^n = h_i^n\)).

2. \(h_i\) ile biten \(w\) sözcüklerinden her biri yukarıdaki yöntemlerden sadece bir tanesiyle oluşturulabilir. Herhangi iki yöntemle oluşturulabilen sözcüklerin kümeleri ayrıktır. Bu yüzden bu işlemleri bütün \(i\) değerleri için yapıp sonuçları topladığımızda \(L\)'de uzunluğu \(n\) olan sözcüklerin sayısını bulmuş oluruz.

Bu açıklamalardan hareketle sorunun çözümünü basamaklara ayıralım. Önce herhangi bir \(n\) uzunluğu için \(|w| = n\) olan ve \(h_i\) ile biten sözcük sayısını bulalım.

\(S(h_i, x)\) uzunluğu \(x\) olan ve \(h_i\) ile biten sözcüklerin sayısını gösteren fonksiyon olsun. \(A(x)\) uzunluğu \(x\) olan bütün sözcüklerin sayısını gösteren fonksiyon olsun. \[S(h_i, x) = \begin{cases}0, & x \leq 0\\ \sum_{k=1}^{c_i}{A(x-k) - S(h_i, x - k)}, & otherwise\end{cases}\]

\[A(x) = \begin{cases}0, & x < 0\\ 1, & x = 0\\ \sum_{i=1}^{\mathbf{M}}{S(h_i, x)},& otherwise\end{cases}\]

Son olarak 1'den istenen uzunluğa yani \(n\)'e kadar olan \(A(x)\) değerlerini toplayarak cevabı buluruz.

\[\sum_{t=1}^{n}A(x)\]

English

For \(|\Sigma | = \mathbf{M}\), we can define the alphabet used for the language \(L\) as \(\Sigma = \{h_1,h_2,h_3,\dots,h_M\}\). For \(1 \leq i \leq \mathbf{M}\), let \(c_i\) be the constraint for \(h_i\) on \(L\), limiting the maximum count of consecutive \(h_i\)'s that can take place in a word in \(L\).

For any \(w \in L\) that ends with \(h_i\) and has length \(n\), \(w\) can be constructed as the following:

• \(w_1 \in L \land |w_1|=(n-1)\) \(w_1\), does not end with \(h_i\): \(\quad\)\(w_1h_i\)
• \(w_2 \in L \land |w_2|=(n-2)\) \(w_2\), does not end with \(h_i\): \(\quad\)\(w_2h_ih_i\)
• \(w_3 \in L \land |w_3|=(n-3)\) \(w_3\), does not end with \(h_i\): \(\quad\)\(w_3h_ih_ih_i\)

\(\qquad \qquad \vdots\)

• \(w_{c_i} \in L \land |w_{c_i}|=(n-c_i)\), \(w_{c_i}\) does not end with \(h_i\): \(\quad\) \(w_{c_i}h^{c_i}\)

Notice the following two details:

1. Pay attention to the value of \(n\) compared to that of \(c_i\). If \(n\) is less then \(c_i\), then we might be trying to append a sufficient number of \(h_i\)'s to a word whose length is less than 0 to construct a \(w\). To avoid this case, we need to ensure that \(|w_i| \geq 0\) is true. Also, we assume that there is a single word whose length is 0, that is the empty string or \(e\). For \(n \leq c_i\) we can construct a \(w\) by appending a sufficient number of \(h_i\)'s to the empty string (\(eh_i^n = h_i^n\)).

2. A \(w\) ending with \(h_i\) can only be constructed with one of the aforementioned methods, and the set of words yielded by the methods are distinct. Therefore, applying these methods for all possible values of \(i\) and summing the results yields us the count of words whose length is \(n\) in \(L\).

Now, we can divide the solution of the problem to two parts. First, for any \(n\), we can find the count of words \(|w| = n\) that end with \(h_i\) as the following:

\[S(h_i, x) = \begin{cases}0, & x \leq 0\\ \sum_{k=1}^{c_i}{A(x-k) - S(h_i, x - k)}, & otherwise\end{cases}\] Where \(S(h_i, x)\) is the function for finding the count of words ending with \(h_i\) whose length is \(x\).

\[A(x) = \begin{cases}0, & x < 0\\ 1, & x = 0\\ \sum_{i=1}^{\mathbf{M}}{S(h_i, x)},& otherwise\end{cases}\] Where \(A(x)\) is the function for finding the count of words ending with any symbol from \(\Sigma\) whose length is \(x\).

Finally, the summation of \(A(x)\) values for \(x\) is from 1 to \(n\) yields us the solution.

\[\sum_{t=1}^{n}A(x)\]

Örnek Çözüm / Sample Solution

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

typedef long long Int;
typedef pair<int,int> PII;
typedef vector<int> VInt;

#define FOR(i, a, b) for(i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(i = (a) - 1; i >= (b); --i)
#define EACH(it, a) for(auto it = (a).begin(); it != (a).end(); ++it)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define SIZE(a) int((a).size())
#define ALL(a) (a).begin(),(a).end()
#define MP make_pair

#define MOD ((int)(1e9+7))

int A[1 << 10];
Int R[1 << 10][1 << 10];
Int S[1 << 10][1 << 10];
Int Z[1 << 10];

int main()
{
    CLEAR(A, 0);
    CLEAR(R, 0);
    CLEAR(S, 0);
    CLEAR(Z, 0);

    int n, m;
    cin >> n >> m;
    int i, j;
    FOR(i, 0, m) cin >> A[i];

    Int res = 0;
    R[0][m] = 1;
    FOR(i, 1, n + 1)
    {
        FOR(j, 0, m + 1) S[i][j] = (S[i - 1][j] + R[i - 1][j]) % MOD;
        FOR(j, 0, m + 1) Z[i] = (Z[i] + S[i][j]) % MOD;
        FOR(j, 0, m) 
        {
            R[i][j] = (Z[i] - Z[max(0, i - A[j])] + MOD - S[i][j] + S[max(0, i - A[j])][j] + MOD) % MOD;
            res = (res + R[i][j]) % MOD;
        }
    }

    cout << res << endl;
}