fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxV = 125005, MOD = 1e9 + 7;
  5. long long n, dp[MaxV + 5];
  6.  
  7. void add(long long &a, long long b)
  8. {
  9.     a += b;
  10.     if(a >= MOD) a -= MOD;
  11. }
  12.  
  13. void input()
  14. {
  15.     cin >> n;
  16. }
  17.  
  18. void solve1()
  19. {
  20.     long long sum = 0;
  21.     for(long long i = 1; i <= n; i++)
  22.     {
  23.         sum += i;
  24.     }
  25.  
  26.     if(sum % 2 != 0)
  27.     {
  28.         cout << 0;
  29.         return;
  30.     }
  31.  
  32.     long long target = sum / 2;
  33.  
  34.     memset(dp, 0, sizeof(dp));
  35.     dp[0] = 1;
  36.  
  37.     for(long long i = 1; i <= n; i++)
  38.     {
  39.         for(long long j = target; j >= i; j--)
  40.         {
  41.             add(dp[j], dp[j - i]);
  42.         }
  43.     }
  44.  
  45.     cout << dp[target] * ((MOD + 1) / 2) % MOD;
  46. }
  47.  
  48. void solve2()
  49. {
  50.     long long sum = 0;
  51.     for(long long i = 1; i <= n; i++)
  52.     {
  53.         sum += i;
  54.     }
  55.  
  56.     if(sum % 2 != 0)
  57.     {
  58.         cout << 0;
  59.         return;
  60.     }
  61.  
  62.     long long target = sum / 2;
  63.  
  64.     memset(dp, 0, sizeof(dp));
  65.     dp[0] = 1;
  66.  
  67.     for(long long i = 1; i <= n; i++)
  68.     {
  69.         for(long long j = 0; j <= target; j++)
  70.         {
  71.             if(j >= i)
  72.             {
  73.                 add(dp[j], dp[j - i]);
  74.             }
  75.         }
  76.     }
  77.  
  78.     cout << dp[target] * ((MOD + 1) / 2) % MOD;
  79. }
  80.  
  81. int main()
  82. {
  83.     ios_base::sync_with_stdio(0);
  84.     cin.tie(0);
  85.  
  86.     input();
  87.     solve1();
  88. }
  89.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
500000004
https://ideone.com/p3VZN0
language:
C++14 (gcc 8.3)
created:
15 hours 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!