Cod sursa(job #2977649)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 12 februarie 2023 01:42:54
Problema Diviz Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <fstream>

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

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

const int MOD=30103;
const int NMAX=2e2+5;
const int MAXR=100;

int dp[2][NMAX][MAXR];

int v[NMAX];
int pozdigit[NMAX][10];

string s;

void reset(int key,int n,int k)
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=0;j<k;j++)
            dp[key][i][j]=0;
}

int main()
{
    int n,k,a,b,i,j,r,c;
    long long kon=0;
    bool key=true;
    fin>>k>>a>>b;
    fin>>s;
    s=' '+s;
    n=s.size();
    for(i=0;i<=9;i++)
        pozdigit[n+1][i]=n;
    for(i=n;i>=1;i--)
    {
        for(j=0;j<=9;j++)
        {
            if(i!=n)
            {
                if(s[i]-'0'==j)
                    pozdigit[i][j]=i;
                else
                    pozdigit[i][j]=pozdigit[i+1][j];
            }
            else
            {
                if(s[i]-'0'==j)
                    pozdigit[i][j]=n;
                else
                    pozdigit[i][j]=0;
            }
        }
    }
    for(i=1;i<=9;i++)
        dp[key][pozdigit[1][i]][i%k]=1;
    for(i=1;i<=b;i++)
    {
        for(j=i;j<=n;j++)
        {
            for(r=0;r<k;r++)
            {
                if(!dp[key][j][r])
                    continue;
                else
                {
                    for(c=0;c<=9;c++)
                    {
                        if(pozdigit[j+1][c]==0)
                            continue;
                        else
                        {
                            int aux=(r*10+c)%k;
                            dp[!key][pozdigit[j+1][c]][aux]=(dp[!key][pozdigit[j+1][c]][aux]+dp[key][j][r])%MOD;
                        }
                    }
                }
            }
            if(i>=a)
                kon=(kon+dp[key][j][0])%MOD;
        }
        reset(key,n,k);
        key=!key;
    }
    fout<<kon;
    return 0;
}