Michael își petrece vacanța de vară la bunici, în Delta Dunării. În prima zi, se duce la pescuit cu tatăl său în locul în care acesta se ducea în copilărie. Michael își dă seama că traseul ales nu este singura opțiune de a parcurge distanța de la casa bunicilor până la locul unde pescuiesc, așa că, odată ce vizitează întreaga regiune împreună cu bunicul său, se întreabă în câte moduri distincte poate parcurge distanța de la casa bunicilor la locul unde pescuiesc. Regiunea pe care Michael o cunoaște are formă dreptunghiulară, cu rânduri numerotate de la 1 la L și coloane numerotate de la 1 la C. Valorile de 1 reprezintă zone de uscat și valorile de 0 reprezintă zone acoperite de apă. Michael poate merge doar pe uscat, cu următoarea restricție: din zona de coordonate (i, j) se poate duce doar în una din zonele (i – 1, j + 1), (i, j + 1), (i + 1, j + 1) – bineînțeles, doar dacă acestea reprezintă zone de uscat și Michael nu părăsește regiunea. Fiind un băiat inteligent, când Michael vizitează împrejurimile cu bunicul său, își dă seama de următorul lucru: coloanele din matricea care codifică regiunea se repetă identic din K în K. Coloanele 2, K + 2, 2 * K + 2, … sunt identice, coloanele K – 1, K + (K - 1), 2 * K + (K - 1), … sunt identice. Două coloane c1 și c2 sunt identice dacă elementul de pe poziția (i, c1) este egal cu elementul de pe poziția (i, c2), oricare ar fi i de la 1 la L.

Cerința

Știind coordonatele locului unde se află casa bunicilor și coordonatele locului de pescuit pe care tatăl lui Michael i l-a arătat acestuia, să se determine numărul de moduri de a parcurge distanța dintre ele. Două drumuri sunt considerate distincte dacă, scriind secvența rândurilor vizitate (în ordine crescătoare a coloanelor), ele diferă prin cel puțin o poziție.

Date de intrare

Prima linie va conține numerele L și K (separate de un spațiu), reprezentând numărul de rânduri ale regiunii și numărul K cu semnificația menționată mai sus. Pe fiecare din următoarele L linii, se găsesc K numere care pot fi 0 sau 1, nefiind separate prin spații. Pe linia L + 2 se află două numere X și C (separate de un spațiu), reprezentând coordonatele (X, C) ale locului unde pescuiesc. Casa bunicilor are coordonatele (1, 1).

Date de ieșire

Programul va afișa pe ecran singur număr natural care reprezintă valoarea cerută modulo 666013.

Restricții și precizări

2 ≤ L, K ≤ 100
1 ≤ X ≤ 100
2 ≤ C ≤ 10¹⁵
Pentru 20% din teste, C ≤ 1000

Exemplu

Intrare

Ieșire

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema optiuni:

#include <iostream>
#define DIM 102
#define MOD 666013
using namespace std;

char A[DIM][DIM];
int v[DIM], w[DIM];
int D[65][DIM][DIM], P[DIM][DIM], M[DIM][DIM], d[DIM][DIM];
int L, K, X, mic = 1, mare = 2;
long long C;

inline int get(int i, int j, int K) {
    if (j%K == 0)
        return A[i][K] - '0';
    else
        return A[i][ j%K ] - '0';
}

void dinamica(int i, int v[], int tip) {
    int aux = K;
    if (tip == mic)
        K = C;

    for (int k=0;k<=L+1;k++)
        v[k] = 0;
    w[0] = w[L+1] = 0;
    if (A[i][1] == '0') {
        return;
    }

    v[i] = 1;
    for (int j=2;j<=K;j++) {
        for (i=1;i<=L;i++) {
            if (get(i, j, aux) == 1)
                w[i] = (v[i-1] + v[i] + v[i+1]) % MOD;
            else
                w[i] = 0;
        }
        for (i=1;i<=L;i++)
            v[i] = w[i];
    }

}

void produs(int A[DIM][DIM], int B[DIM][DIM], int C[DIM][DIM]) {
    for (int i=1;i<=L;i++)
        for (int j=1;j<=L;j++) {
            C[i][j] = 0;
            for (int k=1;k<=L;k++) {
                C[i][j] += (A[i][k-1] + A[i][k] + A[i][k+1]) % MOD * 1LL * B[k][j] % MOD;
                if (C[i][j] >= MOD)
                    C[i][j] -= MOD;
            }
        }
}

void copiere(int A[DIM][DIM], int B[DIM][DIM]) {
    for (int i=1;i<=L;i++)
        for (int j=1; j<=L;j++)
            A[i][j] = B[i][j];
}

void af(char *msg, int a[DIM][DIM]) {
    cout<<msg<<"\n";
    for (int i=1;i<=L;i++) {
        for (int j=1;j<=L;j++)
            cout<<a[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"\n";
}

int main () {

    cin>>L>>K;
    for (int i=1; i<=L; i++)
        cin>>(A[i]+1);
    cin>>X>>C;
    if (C <= 3*K) {
        dinamica(1, v, mic);
        cout<<v[X];
        return 0;
    }

    for (int i=1;i<=L;i++) {
        dinamica(i, v, mare);
        for (int j=1;j<=L;j++)
            D[0][i][j] = v[j];
    }

    ///af("D[0]",D[0]);

    int log = 0;
    long long t = K;

    while (t < C) {
        log++;
        t *= 2;
    }

    for (int p = 1; p <= log; p++) {
        produs(D[p-1], D[p-1], D[p]);
    }
    ///af("D[1]", D[1]);
    long long dim = (C - K - C % K)/K;

    dinamica(1, v, mare);
    for (int j=1;j<=L;j++)
        P[1][j] = v[j];

    int bit = 0;
    while (dim != 0) {
        if (dim % 2 == 1) {
            produs(P, D[bit], M);
            copiere(P, M);
        }
        bit++;
        dim /= 2;
    }

    for (int i=1;i<=L;i++)
        d[i][0] = P[1][i];

    for (int j=1;j<=C%K;j++)
        for (int i=1;i<=L;i++)
            if (A[i][j] == '0')
                d[i][j] = 0;
            else
                d[i][j] = (d[i-1][j-1] + d[i][j-1] + d[i+1][j-1]) % MOD;

    cout<<d[X][C%K];

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2540 optiuni

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2540 optiuni de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2540 optiuni