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. int M[N + N];
  14.  
  15. inline int add(int x, int y) {
  16. 	return x + y >= mod ? x + y - mod : x + y;
  17. }
  18.  
  19. int main() {
  20.  
  21. 	scanf("%d %d", &n, &m);
  22.  
  23. 	assert(n <= 1000000);
  24.  
  25. 	for(int i = 1; i <= m; i++) {
  26. 		int x;
  27. 		scanf("%d", &x);
  28. 		a[x]++;
  29. 	}
  30.  
  31. 	for(int i = 1; i <= n; i++)
  32. 		sum[i] = sum[i - 1] + a[i];
  33.  
  34. 	dp[n + 1] = 1;
  35.  
  36. 	int ans = 0;
  37.  
  38. 	sumDp[n + 1] = dp[n + 1];
  39.  
  40. 	M[sum[n] - n + N] = add(M[sum[n] - n + N], 1);
  41.  
  42. 	for(int i = n; i >= 1; i--) {
  43.  
  44. 		if(!a[i - 1]) {
  45. 			dp[i] = M[sum[i - 1] - i + 1 + N];
  46. 		}
  47.  
  48. 		if(a[i])
  49. 			ans = 0;
  50. 		ans = add(ans, dp[i]);
  51.  
  52. 		if(a[i])
  53. 			sumDp[i] = dp[i];
  54. 		else
  55. 			sumDp[i] = add(sumDp[i + 1], dp[i]);
  56.  
  57. 		if(!a[i])
  58. 			M[sum[i - 1] - (i - 1) + N] = add(M[sum[i - 1] - (i - 1) + N], sumDp[i + 1]);
  59. 	}
  60.  
  61. 	printf("%d\n", ans);
  62.  
  63.     return 0;
  64.  
  65. }
  66.  
  67.  
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/L9o6dz
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!