fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4.  
  5. typedef long long  lli ;
  6. typedef long double ld;
  7. typedef vector<lli > vi;
  8. typedef pair<lli ,lli > ii;
  9.  
  10. #define endl '\n'
  11. #define fore(i,a,b) for(lli  i = a; i <  b; i++)
  12. #define sz(s) lli (s.size())
  13. #define all(s) begin(s), end(s)
  14. #define f first
  15. #define s second
  16. #define pb push_back
  17. #define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  18. #define perr(x) cerr<<#x<<" "<<x<<endl
  19. typedef vector<vector<long long> > Matrix;
  20.  
  21. Matrix b(2, vi(2,1));
  22. Matrix a(1,vi(2));
  23.  
  24. long long MOD = 1e9 + 7;
  25. Matrix ones(int n) {
  26. Matrix r(n,vector<long long>(n));
  27. 	for(int i = 0; i < n; ++i) r[i][i] = 1;
  28. 	return r;
  29. }
  30. Matrix operator*(Matrix &a, Matrix &b) {
  31. 	int n=(int)(a.size()),m=(int)(b[0].size()),z=(int)(a[0].size());
  32. 	Matrix r(n,vector<long long>(m));
  33. 	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) for(int k = 0; k < z; ++k)
  34. 		r[i][j]+=a[i][k]*b[k][j],r[i][j]%=MOD;
  35. 	return r;
  36. }
  37. Matrix be(Matrix b, long long e) {
  38. 	Matrix r=ones((int)(b.size()));
  39. 	while(e){if(e&1LL)r=r*b;b=b*b;e/=2;}
  40. 	return r;
  41. }
  42.  
  43. ii compute_fib(int x, int cur, int prev){
  44.  
  45.     a[0][0] = cur;
  46.     a[0][1] = prev;
  47.  
  48.     if(x == 0) return {cur, prev};
  49.  
  50.     Matrix P = be(b, x);
  51.     Matrix res = a*P;
  52.     return {res[0][0], res[0][1]};
  53. }
  54.  
  55. int main() {_
  56.     b[1][1] = 0;
  57.  
  58.     int n, m;
  59.     cin >> n >> m;
  60.  
  61.     vector<int> a(m);
  62.     fore(i,0,m) cin >> a[i];
  63.     sort(all(a));
  64.  
  65.     bool poss = true;
  66.     fore(i,0,m-1){
  67.         if(a[i] + 1 == a[i+1]){ poss = false;break;}
  68.     }
  69.     if(!poss){cout << 0 << endl;return 0;}
  70.  
  71.     vector<int> c = {0};
  72.     fore(i,0,m) {if(a[i] < n  and a[i] > 0)c.pb(a[i]);}
  73.     c.pb(n+1);
  74.  
  75.     vector<int> b;
  76.     fore(i,1,sz(c)) b.pb(c[i] - c[i-1] - 1);
  77.  
  78.     int cur = 1;   
  79.     int prev = 0;
  80.  
  81.     fore(i,0,sz(b)){
  82.         auto nxt = compute_fib(b[i], cur, prev);
  83.         cur = nxt.f;
  84.         prev = nxt.s;
  85.         if(i +1 != sz(b)){        
  86.             prev = cur;            
  87.             cur = 0;               
  88.         }
  89.     }
  90.     cout << cur << endl;
  91. }
Success #stdin #stdout 2.77s 409608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
255718280
https://ideone.com/ZzHlZv
language:
C++14 (gcc 8.3)
created:
5 days 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!