/**
La aceasta problema numarul de interogari este foarte mare, ceea ce ne duce
cu gandul sa precalculam rezultatele pentru a putea raspunde in o(1)
vom face asta in vectorul sol
sol[L][p-'a'][u-'a'] = cate cuvinte de lungime L au penultima litera
a p-a a alfabetului si ultima litera a u-a. Apar mai sus constructiile -'a'
pentru ca noi vom tine a doua si a treia dimensiune intre 0 si 25.
In prima etapa vom calcula D[i][j][k] = cate cuvinte incep de la pozitia i
sau dupa ea si care se termina in literele jk, in aceasta ordine.
Trebuie sa intelegem bine semnificatia dinamicelor:
- la sol primul indice este lungime de cuvant iar la D el este pozitie din srul dat
- la sol al doilea si al treile a indice reprezinta litere ale alfabetului si nu pozitii
Calculam intai pe D si apoi vom vedea cum il folosim pentru a obtine pe sol
Pentru calculul lui D parcurgem cu i indicii din sirul dat invers
si daca la pozitia i avem litera j, D[i][j][ultima] = D[i][j+1][ultima] + R[i+1][ultima]
unde R[i+1][ultima] = de cate ori apare litera "ultima" dupa pozitia j
Pe R il calculam tot invers, R[i][ultima] = 1 = R[i+1][ultima], daca s[i] = ultima
si R[i][ultima] = R[i+1][ultima] in caz contrar.
Semnificatia formulei de mai sus pentru D este ca daca la pozitia i este
chiar litera j, ne intereseaza de cate ori apare litera ultima dupa pozitia curenta,
acesta fiind numarul de perechi noi de forma j, ultima (nu uitam ca pepozitia i este litera j) care se adauga
In celalalt caz,D[i][j][ultima] = D[i+1][j][ultima], deci ce vine din urma
Asa calculat D, sa vedem cum il obtinem pe sol.
pentru sol[L][p][u], ne-ar interesa aparitiile in sirul s ale literei p.
Pe acestea le tinem intr-o lista a lui p pe care noi o numim poz[p].
Pe acest poz noi in construim la citire
pentru a obtine sol[L][p][u], noi parcurgem poz[p] si adunam la
solutie D[ i ][p][u] * combinari[i-1][L-2].
De unde cele de mai sus? in primulrand i este pozitie din poz[p]
ne intereseaza doar valori i mai mari sau egale cu L-1 (adica sa putem)
avea in total L litere. Daca la pozitia i este penultima litera,0
mai avem de selectat din fata pozitiei i in toate modurule L-2 caractere
acest lucru se faca in combinari["cate elemente are multimea de extras"]
luate ["cate elemente extrag"] moduri.
Combinarile le precalculam cu triunghiul lui pascal, intr-o matrice cu o
dinamica clasica C[a][b] = C[a-1][b-1] + C[a-1][b].
Complexitatea este de ordinil len*len*26 si ajungem la ea in etapa de calcul
a lui sol. Forul care parcurge pe poz pentru o litera
imperecheat cu un for ce parurge literele face len (lungimea sirului initial)
**/
#include <cstdio>
#include <cstring>
#include <vector>
#define MOD 1000000007
using namespace std;
char p, u, s[2002];
long long R[2002][26];
long long D[2002][26][26], sol[2002][26][26];
long long C[2002][2002];
vector<long long> poz[26];
long long n, i, j, k, t, L;
int main () {
scanf("%s", s+1);
n = strlen(s+1);
C[0][0] = 1;
for (i=1;i<=n;i++) {
C[i][0] = 1;
for (j=1;j<=i;j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]);
if (C[i][j] >= MOD)
C[i][j] -= MOD;
}
}
for (i=1;i<=n;i++)
poz[s[i]-'a'].push_back(i);
for (i=n;i>=1;i--) {
for (j=0;j<26;j++)
if (s[i] == j+'a') {
R[i][j] = 1 + R[i+1][j];
}
else {
R[i][j] = R[i+1][j];
}
}
for (i=n;i>=1;i--) {
for (j=0;j<26;j++)
for (k=0;k<26;k++)
if (s[i] == j+'a')
D[i][j][k] = /**D[i+1][j][k] +**/ R[i+1][k];
else
D[i][j][k] = D[i+1][j][k];
}
for (L=2;L<=n;L++)
for (j=0;j<26;j++)
for (t=0;t<poz[j].size();t++) {
i=poz[j][t];
if (i >= L-1)
for (k=0;k<26;k++) {
sol[L][j][k] += ((D[i][j][k] * C[i-1][L-2])%MOD);
if (sol[L][j][k] >= MOD)
sol[L][j][k] -= MOD;
}
}
scanf("%lld", &t);
for (;t--;) {
scanf("%lld %c %c", &L, &p, &u);
printf("%lld\n", sol[L][p-'a'][u-'a']);
}
return 0;
}
Compilation message
mate.cpp: In function 'int main()':
mate.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (t=0;t<poz[j].size();t++) {
~^~~~~~~~~~~~~~
mate.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s+1);
~~~~~^~~~~~~~~~~
mate.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &t);
~~~~~^~~~~~~~~~~~
mate.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %c %c", &L, &p, &u);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1300 KB |
Output is correct |
| 5 |
Correct |
51 ms |
5240 KB |
Output is correct |
| 6 |
Correct |
54 ms |
5396 KB |
Output is correct |
| 7 |
Correct |
42 ms |
5004 KB |
Output is correct |
| 8 |
Correct |
39 ms |
4828 KB |
Output is correct |
| 9 |
Correct |
534 ms |
53516 KB |
Output is correct |
| 10 |
Correct |
543 ms |
53552 KB |
Output is correct |
