Advertisement
Josif_tepe

Untitled

Dec 9th, 2021
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int n;
  6. string a;
  7. int memo[200000][8];
  8. int f(int i,int remainder){
  9.     if(i == n && remainder == 0){
  10.         return 1;
  11.     }
  12.     if(i == n && remainder != 0){
  13.         return 0;
  14.     }
  15.     if(memo[i][remainder] != -1 ){
  16.         return memo[i][remainder];
  17.     }
  18.     int res = 0;
  19.     int mod = 1e9 +7;
  20.     res += f(i+1,remainder)+ f(i+1,((remainder*10 + (a[i]-'0'))%8));
  21.     res %= mod;
  22.     return memo[i][remainder] = res;
  23. }
  24. int main() {
  25.     cin >>n;
  26.     cin >>a;
  27.     for (int i = 0; i < n; i++) {
  28.         for (int j = 0; j < 8; j++) {
  29.             memo[i][j] = -1;
  30.         }
  31.     }
  32.     cout << f(0,0) -1;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement