a53

c_n_t_s_c_i_f

a53
May 28th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.66 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define MOD 666013
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. int n,sum;
  8. cin>>n>>sum;
  9. if(sum>=n*9)
  10. {
  11. if(n*9==sum)
  12. {
  13. cout<<1<<'\n';
  14. return 0;
  15. }
  16. else
  17. {
  18. cout<<0<<'\n';
  19. return 0;
  20. }
  21. }
  22. vector<int> d(sum+1,0);
  23. d[0]=1;
  24. for(int i=1;i<=n;++i)
  25. {
  26. if(i==n)d[sum]=0;
  27. for(int j=sum;j>=0;--j)
  28. {
  29. auto&c=d[j];
  30. int l=max(static_cast<int>(0),j-9);
  31. for(int k=j-1;k>=l;--k)
  32. c+=d[k],c-=(c>=MOD)*MOD;
  33. }
  34. }
  35. cout<<d[sum];
  36. return 0;
  37. }
Add Comment
Please, Sign In to add comment