Cod sursa(job #2362236)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 3 martie 2019 00:50:01
Problema Matrix Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>

using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

const int VAL=1005;
const int CAR=35;

int MOD[3], NR[3];
int N, M, i, j, ANS;
int PUT[3][65], cnt;
int dp[3][VAL][VAL];
int lin[3][VAL][VAL];
int col[3][VAL][VAL];
string S[VAL], T[VAL];

int main()
{
    fin >> M >> N;
    MOD[1]=30103;
    MOD[2]=37891;
    PUT[1][0]=PUT[2][0]=1;
    for (i=1; i<CAR; i++)
    {
        for (j=1; j<=2; j++)
        {
            PUT[j][i]=PUT[j][i-1]*26;
            PUT[j][i]%=MOD[j];
        }
    }
    for (i=1; i<=M; i++)
    {
        fin >> T[i];
        T[i]='*'+T[i];
    }
    for (i=1; i<=N; i++)
    {
        fin >> S[i];
        S[i]='*'+S[i];
        for (j=1; j<=N; j++)
        {
            for (cnt=1; cnt<=2; cnt++)
            {
                NR[cnt]+=PUT[cnt][T[i][j]-'a'];
                if (NR[cnt]>=MOD[cnt])
                    NR[cnt]-=MOD[cnt];
            }
        }
    }
    for (i=1; i<=M; i++)
    {
        for (j=1; j<=M; j++)
        {
            for (cnt=1; cnt<=2; cnt++)
            {
                lin[cnt][i][j]=lin[cnt][i][j-1]+PUT[cnt][S[i][j]-'a'];
                if (j>N)
                    lin[cnt][i][j]-=PUT[cnt][S[i][j-N]-'a'];
                lin[cnt][i][j]%=MOD[cnt];
                if (lin[cnt][i][j]<0)
                    lin[cnt][i][j]+=MOD[cnt];

                col[cnt][i][j]=col[cnt][i-1][j]+PUT[cnt][S[i][j]-'a'];
                if (i>N)
                    col[cnt][i][j]-=PUT[cnt][S[i-N][j]-'a'];
                if (col[cnt][i][j]<0)
                    col[cnt][i][j]+=MOD[cnt];
            }
        }
    }
    for (i=1; i<=N; i++)
    {
        for (cnt=1; cnt<=2; cnt++)
        {
            dp[cnt][N][N]+=lin[cnt][i][N];
            if (dp[cnt][N][N]>=MOD[cnt])
                dp[cnt][N][N]-=MOD[cnt];
        }
    }
    if (dp[1][N][N]==NR[1] && dp[2][N][N]==NR[2])
        ANS++;
    for (i=N; i<=M; i++)
    {
        for (j=N; j<=M; j++)
        {
            if (i==N && j==N)
                continue;
            for (cnt=1; cnt<=2; cnt++)
            {
                if (j==N)
                    dp[cnt][i][j]=dp[cnt][i-1][j]+lin[cnt][i][j]-lin[cnt][i-N][j];
                else
                    dp[cnt][i][j]=dp[cnt][i][j-1]+col[cnt][i][j]-col[cnt][i][j-N];
                dp[cnt][i][j]%=MOD[cnt];
                if (dp[cnt][i][j]<0)
                    dp[cnt][i][j]+=MOD[cnt];
            }
            if (dp[1][N][N]==NR[1] && dp[2][N][N]==NR[2])
                ANS++;
        }
    }
    fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}