Submission #145716

#	Time	Username	Problem	Language	Result	Execution time	Memory
145716		AlexPascu007	Mate (COCI18_mate)	C++98	100 / 100	554 ms	53700 KiB

mate

#include <cstdio>
#include <cstring>
#include <vector>
#define mod 1000000007
#define DIM 2002
using namespace std;
char p,u,s[DIM];
long long n,i,j,k,t,l,c[DIM][DIM],r[DIM][26],d[DIM][26][26],sol[DIM][26][26];
vector<long long> poz[26];
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]=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);
    while (t--) {
        scanf("%lld %c %c",&l,&p,&u);
        printf("%lld\n",sol[l][p-'a'][u-'a']);
    }
    return 0;
}

Compilation message (stderr)

mate.cpp: In function 'int main()':
mate.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (t=0;t<poz[j].size();t++) {
                      ~^~~~~~~~~~~~~~
mate.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",s+1);
     ~~~~~^~~~~~~~~~
mate.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&t);
     ~~~~~^~~~~~~~~~~
mate.cpp:58: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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100