fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair < int, int > ii;
  7.  
  8. const int N = 1e6 + 5;
  9. const int mod = 1e9 + 7;
  10.  
  11. int n, m;
  12. int a[N], sum[N], dp[N], sumDp[N];
  13.  
  14. inline int add(int x, int y) {
  15. 	return x + y >= mod ? x + y - mod : x + y;
  16. }
  17.  
  18. int main() {
  19.  
  20. 	scanf("%d %d", &n, &m);
  21.  
  22. 	for(int i = 1; i <= m; i++) {
  23. 		int x;
  24. 		scanf("%d", &x);
  25. 		a[x]++;
  26. 	}
  27.  
  28. 	for(int i = 1; i <= n; i++)
  29. 		sum[i] = sum[i - 1] + a[i];
  30.  
  31. 	dp[n + 1] = 1;
  32.  
  33. 	int ans = 0;
  34.  
  35. 	sumDp[n + 2] = 1;
  36. 	sumDp[n + 1] = 1;
  37.  
  38. 	for(int i = n; i >= 1; i--) {
  39. 		if(!a[i-1])
  40. 		for(int j = i; j <= n; j++) {
  41. 			if(j - i + 1 == sum[j] - sum[i - 1] and !a[j + 1]) {
  42. 				dp[i] = add(dp[i], sumDp[j + 2]);
  43. 			}
  44. 		}
  45. 		if(a[i])
  46. 			ans = 0;
  47. 		ans = add(ans, dp[i]);
  48.  
  49. 		if(a[i])
  50. 			sumDp[i] = dp[i];
  51. 		else
  52. 			sumDp[i] = add(sumDp[i + 1], dp[i]);
  53. 	}
  54.  
  55. 	printf("%d\n", ans);
  56.  
  57.     return 0;
  58.  
  59. }
  60.  
  61.  
Success #stdin #stdout 0s 4304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/7pZh4R
language:
C++14 (clang 8.0)
created:
6 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!