Advertisement
Josif_tepe

Untitled

Mar 19th, 2024
672
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <cstring>
  6. using namespace std;
  7. typedef long long ll;
  8. const int maxn = 2e5 + 10;
  9. const ll MOD = 1e9 + 7;
  10. int n;
  11. string s;
  12. ll dp[maxn][9];
  13. ll rec(int at, int remainder) {
  14.     if(at == n and remainder == 0){
  15.         return 1;
  16.     }
  17.     if(at == n) {
  18.         return 0;
  19.     }
  20.     if(dp[at][remainder] != -1) {
  21.         return dp[at][remainder];
  22.     }
  23.     ll res = 0;
  24.     res += rec(at + 1, remainder);
  25.     res %= MOD;
  26.     int new_remainder = (remainder * 10 + (s[at] - '0')) % 8;
  27.     res += rec(at + 1, new_remainder);
  28.     res %= MOD;
  29.     return dp[at][remainder] = res;
  30. }
  31. int main() {
  32.     ios_base::sync_with_stdio(false);
  33.     cin >> n >> s;
  34.     memset(dp, -1, sizeof dp);
  35.     cout << rec(0, 0) - 1 << endl;
  36.     return 0;
  37. }
  38.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement