daily pastebin goal
68%
SHARE
TWEET

Untitled

a guest Apr 17th, 2018 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. long long a,n;
  7. int x,d,s;
  8. long long m;
  9. char bla[50];
  10. pair <long long,long long> dp[50][2][20010][2];
  11.  
  12. pair<long long,long long> rek(int pos,bool granica,int mod,bool jesam){
  13.         if(dp[pos][granica][mod][jesam].first!=-1) return dp[pos][granica][mod][jesam];
  14.         if(pos==s){
  15.             if(mod==a%d) return make_pair(1,0);
  16.             else return make_pair(0,0);
  17.         }
  18.         dp[pos][granica][mod][jesam].first=0;
  19.         dp[pos][granica][mod][jesam].second=0;
  20.         for(int zn=0;zn<10;++zn){
  21.                 if(x!=0 || zn!=0){
  22.                     bool g=0;
  23.                     if(granica==0 && zn>bla[pos]-'0') continue;
  24.                     if(granica==1 || zn<bla[pos]-'0') g=1;
  25.                     dp[pos][granica][mod][jesam].first+=rek(pos+1,g,(10*mod+zn)%d,1).first;
  26.                     dp[pos][granica][mod][jesam].second+=rek(pos+1,g,(10*mod+zn)%d,1).second;
  27.                     if(zn==x) dp[pos][granica][mod][jesam].second+=rek(pos+1,g,(10*mod+zn)%d,1).first;
  28.                 }
  29.                 else{
  30.                     bool g=0;
  31.                     if(granica==0 && zn>bla[pos]-'0') continue;
  32.                     if(granica==1 || zn<bla[pos]-'0') g=1;
  33.                     dp[pos][granica][mod][jesam].first+=rek(pos+1,g,(10*mod+zn)%d,jesam).first;
  34.                     dp[pos][granica][mod][jesam].second+=rek(pos+1,g,(10*mod+zn)%d,jesam).second;
  35.                     if(jesam) dp[pos][granica][mod][jesam].second+=rek(pos+1,g,(10*mod+zn)%d,jesam).first;
  36.                 }
  37.         }
  38.         return dp[pos][granica][mod][jesam];
  39. }
  40.  
  41. int main(void){
  42.     memset(dp,-1,sizeof(dp));
  43.     scanf("%lld%d%lld%d",&a,&d,&n,&x);
  44.     m=n*d+a;
  45.     sprintf(bla,"%lld",m);
  46.     s=strlen(bla);
  47.     long long rj=rek(0,0,0,0).second;
  48.     memset(dp,-1,sizeof(dp));
  49.     sprintf(bla,"%lld",a-1);
  50.     s=strlen(bla);
  51.     rj-=rek(0,0,0,0).second;
  52.     printf("%lld\n",rj);
  53. return 0;
  54. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top