fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. const long MOD = 1000000007;
  4.  
  5. using namespace std;
  6.  
  7. int main(){
  8.  
  9.   //freopen("input.txt","r",stdin);
  10.  
  11.   long n,m,k;
  12.  
  13.  
  14.   cin >> n >> m >> k;
  15.   long a[n+1];
  16.   long ans[n+1];
  17.  
  18.   memset(a,0,sizeof(a));
  19.   memset(ans,0,sizeof(ans));
  20.  
  21.   for (long i = 1; i<=k;++i){
  22.     long pos;
  23.     cin >> pos;
  24.     a[pos] = 1;
  25.   }
  26.  
  27.  
  28.   a[0] = 0;
  29.   ans[1] = 1;
  30.   for(long i = 2; i<=n;++i){
  31.     if (a[i] == 1) continue;
  32.     for (long j = i - m; j <i;++j){
  33.         if (j < 0) continue;
  34. 	if (a[j] == 1) continue;
  35.         if (j == 0){
  36. 	  ans[i] += 1;
  37. 	}
  38. 	else {
  39. 	  ans[i] += ans[j];
  40. 	}
  41. 	ans[i] %= MOD;
  42.     }
  43.     ans[i] %= MOD;
  44.   }
  45. /*
  46.   for(long i = 1; i<=n;++i){
  47.     cout << ans[i] << "\n";
  48.   }
  49. */
  50.  
  51.   cout << ans[n];
  52.   return 0;
  53. }
  54.  
Success #stdin #stdout 0s 4240KB
comments (?)
stdin
copy 
8 3 2
3 4
stdout
copy 
8
https://ideone.com/YXbGgM
language:
C++14 (gcc 8.3)
created:
5 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!