Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int int64_t
  3. #define F first
  4. #define S second
  5.  
  6. using namespace std;
  7. const int N = 1e5+5;
  8. const int INF = 1e18+7;
  9. const int MOD = 1e9+7;
  10.  
  11. map<pair<int,int>,int> dp;
  12. int n,k;
  13.  
  14. int rec(int pos, int sum=0)
  15. {
  16. if(dp[{pos,sum}]!=-1) return dp[{pos,sum}];
  17. int t=0;
  18. if(sum==n) t++;
  19. if(pos==k){
  20. return dp[{pos,sum}]=t;
  21. }
  22. for(int i=0;i<=9;i++) t+=rec(pos+1,sum+i);
  23. if(pos!=0){
  24. for(int i=0;i<=9;i++) t+=rec(pos+1,sum-i);
  25. }
  26. return dp[{pos,sum}]=t;
  27. }
  28.  
  29. int32_t main()
  30. {
  31. ios_base::sync_with_stdio(false);
  32. cin.tie(0); cout.tie(0);
  33. // freopen("input.txt","r",stdin);
  34. // freopen("output.txt","w",stdout);
  35. for(int i=0;i<10;i++){
  36. for(int j=-100;j<100;j++){
  37. dp[{i,j}]=-1;
  38. }
  39. }
  40. cin>>n>>k;
  41. int ans = rec(0,0);
  42. if(n==0) ans--;
  43. cout<<ans<<endl;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement