Cod sursa(job #1237311)

Utilizator apopeid15Apopei Daniel apopeid15 Data 3 octombrie 2014 19:40:47
Problema Diviz Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <cstring>
 
#define mod 30103
 
using namespace std;
 
ifstream fin ("diviz.in");
ofstream fout ("diviz.out");
 
int dp[2][201][101],n,K,A,B,ans,ok;
int dif[10][201][101];
string s;
 
void add (int ad, int &to)
{
    to += ad;
    if (to >= mod)
        to -= mod;
    if (to < 0)
        to += mod;
}
 
int main()
{
    fin>>K>>A>>B;
 
    fin>>s;
    n = s.length ();
 
    dp[0][0][0] = 1;
 
    for (int i=1; i<=n; ++i)
    {
        memset (dp[i&1],0,sizeof(dp[i&1]));
        int nr = s[i-1]-'0';
 
        for (int j=0; j<i; ++j)
        {
            for (int k=0; k<K; ++k)
            {
                int upd = dp[(i-1)&1][j][k] - dif[nr][j][k];
 
                add (dp[(i-1)&1][j][k],dp[i&1][j][k]);
                add (upd,dp[i&1][j+1][(k*10+nr)%K]);
 
                dif[nr][j][k] = dp[(i-1)&1][j][k];
            }
        }
 
        if (nr == 0 && !ok)
            add (-1,dp[i&1][1][0]), ok = 1;
    }
 
    for (int j=A; j<=B; ++j)
        add (dp[n&1][j][0],ans);
 
    fout<<ans;
}