fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fr(i, n, d, x) for(ll i = d; i < n; i += x)
  4. #define frr(i, n, d, x) for(ll i = d; i <= n; i += x)
  5. #define frd(i, n, d, x) for(ll i = d; i > n; i -= x)
  6. #define frrd(i, n, d, x) for(ll i = d; i >= n; i -= x)
  7. #define pb push_back
  8. #define elif else if
  9. using namespace std;
  10.  
  11. int main(){
  12.     cin.tie(0);
  13.     cout.tie(0);
  14.     ios_base::sync_with_stdio(0);
  15.     ll n, m, ans = 0, dp[100001][10];
  16.     dp[0][0] = 0;
  17.     fr(i, 10, 1, 1)
  18.         dp[0][i] = 1;
  19.     cin >> n >> m;
  20.     fr(i, n - 1, 0, 1){
  21.         fr(j, 10, 0, 1){
  22.             dp[i][j] %= m;
  23.             if(j == 0){
  24.                 fr(k, 10, 1, 1){
  25.                     dp[i + 1][k] += dp[i][j];
  26.                 }
  27.             }
  28.             elif(j >= 1 && j <= 4){
  29.                 fr(k, 10, 0, j){
  30.                     dp[i + 1][k] += dp[i][j];
  31.                 }
  32.             }
  33.             elif(j >= 5 && j <= 9){
  34.                 dp[i + 1][0] += dp[i][j];
  35.                 dp[i + 1][j] += dp[i][j];
  36.             }
  37.         }
  38.  
  39.     }
  40.     fr(i, 10, 0, 1){
  41.         ans += dp[n - 1][i];
  42.         ans %= m;
  43.     }
  44.     cout << ans % m;
  45. }
  46.  
Success #stdin #stdout 0s 4368KB
comments (?)
stdin
copy 
2
20
stdout
copy 
12
https://ideone.com/RTmBu8
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!