Advertisement
Josif_tepe

Untitled

Dec 8th, 2021
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.68 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int dp[200005][8];
  5. int main()
  6. {
  7.     int n;
  8.     cin >> n;
  9.     string s;
  10.     cin >> s;
  11.     for(int i = 0; i <= n; i++) {
  12.         for(int j = 0; j < 8; j++) {
  13.             dp[i][j] = 0;
  14.         }
  15.     }
  16.     dp[0][0] = 1;
  17.     int MOD = 1e9 + 7;
  18.     for(int i = 0; i < n; i++) {
  19.         for(int remainder = 0; remainder < 8; remainder++) {
  20.             dp[i + 1][remainder] += dp[i][remainder];
  21.             dp[i + 1][remainder] %= MOD;
  22.             dp[i + 1][(remainder * 10 + (s[i] - '0')) % 8] += dp[i][remainder];
  23.             dp[i + 1][(remainder * 10 + (s[i] - '0')) % 8] %= MOD;
  24.         }
  25.     }
  26.     cout << dp[n][0]  - 1<< endl;
  27. }
  28.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement