fork download
copy 
  1. //https://c...content-available-to-author-only...s.fi/problemset/task/1746
  2. /*
  3. dp[i][j] là số lượng mảng thỏa mãn với số cuối là j
  4. */
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. const long long MaxN = 1e5+5,MaxM=105,MOD=1e9+7;
  8. long long n,m,a[MaxN],dp[MaxN][MaxM];
  9.  
  10. void add(long long &a,long long b)
  11. {
  12.     a+=b;
  13.     if(a>=MOD) a-=MOD;
  14. }
  15.  
  16. void input()
  17. {
  18.     cin >> n >> m;
  19.     for(long long i=1;i<=n;i++)
  20.         cin >> a[i];
  21. }
  22.  
  23. void solve()
  24. {
  25.     for(long long i=1;i<=n;i++)
  26.     {
  27.         for(long long j=1;j<=m;j++)
  28.             dp[i][j]=0;
  29.     }
  30.  
  31.     if(a[1]==0)
  32.     {
  33.         for(long long j=1;j<=m;j++)
  34.             dp[1][j]=1;
  35.     }
  36.     else
  37.     {
  38.         dp[1][a[1]]=1;
  39.     }
  40.  
  41.     for(long long i=2;i<=n;i++)
  42.     {
  43.         if(a[i]==0)
  44.         {
  45.             for(long long j=1;j<=m;j++)
  46.             {
  47.                 add(dp[i][j],dp[i-1][j]);
  48.  
  49.                 if(j>1)
  50.                     add(dp[i][j],dp[i-1][j-1]);
  51.  
  52.                 if(j<m)
  53.                     add(dp[i][j],dp[i-1][j+1]);
  54.             }
  55.         }
  56.         else
  57.         {
  58.             long long j=a[i];
  59.  
  60.             add(dp[i][j],dp[i-1][j]);
  61.  
  62.             if(j>1)
  63.                 add(dp[i][j],dp[i-1][j-1]);
  64.  
  65.             if(j<m)
  66.                 add(dp[i][j],dp[i-1][j+1]);
  67.         }
  68.     }
  69.  
  70.     long long res=0;
  71.  
  72.     if(a[n]==0)
  73.     {
  74.         for(long long j=1;j<=m;j++)
  75.             add(res,dp[n][j]);
  76.     }
  77.     else
  78.     {
  79.         res=dp[n][a[n]];
  80.     }
  81.  
  82.     cout << res;
  83. }
  84.  
  85. int main()
  86. {
  87.     ios_base::sync_with_stdio(0);
  88.     cin.tie(0);
  89.  
  90.     input();
  91.     solve();
  92. }
  93.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GX4mJO
language:
C++14 (gcc 8.3)
created:
11 hours 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!