fork download
copy 
  1. /*DM NA*/
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define ld long double
  6. #define task "name"
  7. #define ii pair<ll, ll>
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define em emplace
  12. #define all(x) (x).begin(), (x).end()
  13. #define sall(x) sort(all(x))
  14. #define rall(x) reverse(all(x))
  15. #define testcase \
  16.     int tc;      \
  17.     cin >> tc;   \
  18.     while (tc--) \
  19.         solve();
  20. ll inline gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }
  21. ll inline lcm(ll a, ll b) { return (a / gcd(a, b) * b); }
  22. ///============================================================================
  23. #define BIT(i, mask) ((mask >> (i - 1)) & 1)
  24. #define DAOBIT(i, mask) ((mask ^ (1 << i - 1)))
  25. #define OFFBIT(i, mask) ((mask & ~(1 << (i - 1))))
  26. #define ONBIT(i, mask) ((mask | (1 << (i - 1))))
  27. ///============================================================================
  28. const ll mod = 998244353;
  29. const ll inf = (ll)1e18 + 10;
  30. const ll nmax = 1e6+5;
  31. ///============================================================================
  32. using namespace std;
  33. ///============================================================================
  34. ll nhan(ll a, ll b, ll M)
  35. {
  36.     if (b == 0)
  37.         return 0;
  38.     ll t = nhan(a, b / 2, M) % M;
  39.     if (b & 1)
  40.         return ((t + t) % M + a % M) % M;
  41.     else
  42.         return (t + t) % M;
  43. }
  44. ll mu(ll a, ll b, ll M)
  45. {
  46.     if (b == 0)
  47.         return 1LL;
  48.     ll half = mu(a, b / 2LL, M) % M;
  49.     half = nhan(half, half, M);
  50.     if (b & 1)
  51.         return nhan(half, a, M);
  52.     else
  53.         return half;
  54. }
  55. struct matrix {
  56.     ll a[12][12];
  57.     ll hang, cot;
  58. };
  59. matrix nhan(matrix a, matrix b)
  60. {
  61.     matrix ans;
  62.     ans.hang = a.hang;
  63.     ans.cot = b.cot;
  64.     for (int i = 1; i <= ans.hang; i++)
  65.         for (int j = 1; j <= ans.cot; j++)
  66.         {
  67.             ans.a[i][j] = 0;
  68.             for (int k = 1; k <= a.cot; k++)
  69.                 ans.a[i][j] = (ans.a[i][j] + (a.a[i][k] % mod) * (b.a[k][j] % mod) % mod + mod) % mod;
  70.             ///ans.a[i][j] = (ans.a[i][j] + nhan(a.a[i][k], b.a[k][j], mod)) % mod;
  71.         }
  72.     return ans;
  73. }
  74. matrix mu(matrix a, ll b)
  75. {
  76.     if (b == 1) return a;
  77.     matrix ans = mu(a, b / 2LL);
  78.     ans = nhan(ans, ans);
  79.     if (b & 1) return nhan(ans, a);
  80.     else return ans;
  81. }
  82. ll n, m;
  83. map<ll, bool> a;
  84. ll dp[nmax], mx;
  85. matrix b, c;
  86. ///============================================================================
  87. int main()
  88. {
  89.     ios::sync_with_stdio(0);
  90.     cin.tie(0);
  91.     cout.tie(0);
  92.     cin >> n >> m;
  93.     for(int i = 1; i <= m; i++)
  94.     {
  95.         ll x;
  96.         cin >> x;
  97.         a[x] = 1;
  98.     }
  99.     if(n <= 200000)
  100.     {
  101.         dp[0] = 1;
  102.         for(int i = 2; i <= n; i++)
  103.         {
  104.             if(a[i])
  105.                 dp[i] = 0;
  106.             else{
  107.                 dp[i] = (dp[i - 2] + dp[i - 3] * (i >= 3)) % mod;
  108.             }
  109.             ///cout << i << ' ' << dp[i] << '\n';
  110.         }
  111.         cout << dp[n];
  112.         return 0;
  113.     }
  114.     if(m == 0)
  115.     {
  116.         b.hang = 3, b.cot = 3;
  117.         b.a[1][2] = b.a[1][3] = 1;
  118.         b.a[2][1] = b.a[3][2] = 1;
  119.         matrix ans = mu(b, n);
  120.         matrix c;
  121.         c.hang = 3, c.cot = 1;
  122.         c.a[1][1] = c.a[3][1] = 1;
  123.         matrix res = nhan(c, ans);
  124.         /*for(int i = 1; i <= 3; i++)
  125.         {
  126.             for(int j = 1; j <= 3; j++)
  127.             {
  128.                 cout << ans.a[i][j] << ' ';
  129.             }
  130.             cout << '\n';
  131.         }*/
  132.         cout << res.a[1][1];
  133.  
  134.     }
  135.  
  136. }
  137.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/Xe31nE
language:
C++14 (gcc 8.3)
created:
15 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!