fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #pragma GCC target("avx2")
  7. #pragma GCC optimize("O3")
  8. #pragma GCC optimize("unroll-loops")
  9. typedef long long ll;
  10. typedef vector <ll> vll;
  11. typedef set <ll> sll;
  12. typedef vector <vector<ll>> vvll;
  13. typedef set<pair<ll,ll>> spll;
  14. typedef vector <bool> vbl;
  15. typedef vector <pair<ll,ll>> vpll;
  16. typedef map <ll,ll> mll;
  17.  
  18. #define yen cout<<"YES"<<"\n"
  19. #define ye cout<<"YES"
  20. #define non cout<<"NO"<<"\n"
  21. #define no cout<<"NO"
  22. #define pb push_back
  23. #define bk break
  24. #define co continue
  25. #define ff first
  26. #define ss second
  27. #define f(i, a, b) for (long long i = (a); i <= (b); i++)
  28. #define fr(i, a, b) for (long long i = (b); i >= (a); i--)
  29.  
  30. ll LMA=LLONG_MAX;
  31. ll LMI=LLONG_MIN;
  32.  
  33. void pr(vector <ll> &v)
  34. {
  35.     ll sz=v.size();
  36.     sz-=2;
  37.     for (ll i=1;i<=sz;i++)
  38.     {
  39.         cout<<v[i]<<" ";
  40.     }
  41.     cout<<"\n";
  42. }
  43.  
  44. void pr0(vector <ll> &v)
  45. {
  46.     for (auto elem:v)
  47.     {
  48.         cout<<elem<<" ";
  49.     }
  50.     cout<<"\n";
  51. }
  52.  
  53. template<typename T>
  54. using ordered_set = tree<
  55.     T,
  56.     null_type,
  57.     less<T>,
  58.     rb_tree_tag,
  59.     tree_order_statistics_node_update>;
  60.  
  61. const ll MAXN=500;
  62. const ll MOD=998244353;
  63. ll factorial[MAXN + 1];
  64. ll inverse_factorial[MAXN + 1];
  65.  
  66. // Function to compute power of a number with modular arithmetic
  67. ll power(ll x, ll y)
  68. {
  69.     ll res=1;
  70.     x=x%MOD;
  71.     while (y>0)
  72.     {
  73.         if ((y&1)!=0)
  74.         {
  75.             res=(res*x)%MOD;
  76.         }
  77.         y=y>>1;
  78.         x=(x*x)%MOD;
  79.     }
  80.     return res;
  81. }
  82.  
  83. void compute_factorials()
  84. {
  85.     factorial[0]=1;
  86.     for (ll i=1;i<= MAXN;++i)
  87.     {
  88.         factorial[i]=(factorial[i-1]*i)%MOD;
  89.     }
  90. }
  91.  
  92. void compute_inverse_factorials()
  93. {
  94.     inverse_factorial[MAXN]=power(factorial[MAXN],MOD-2);
  95.     for (ll i=(MAXN - 1);i>=0;--i)
  96.     {
  97.         inverse_factorial[i]=(inverse_factorial[i+1]*(i+1))%MOD;
  98.     }
  99. }
  100.  
  101. ll binomial_coefficient(ll n, ll k)
  102. {
  103.     if (k>n)
  104.     {
  105.         return 0;
  106.     }
  107.     return (((factorial[n]*inverse_factorial[k])%MOD)*inverse_factorial[n-k])%MOD;
  108. }
  109.  
  110. int main()
  111. {
  112.     ios_base::sync_with_stdio(false);
  113.     cin.tie(0);
  114.  
  115.     ll t=1;
  116.     cin>>t;
  117.  
  118.     compute_factorials();
  119.     compute_inverse_factorials();
  120.  
  121.     while (t--)
  122.     {
  123.         ll n;
  124.         cin>>n;
  125.         ll answer=0;
  126.         for (ll m=1;m<=(n-1);m++)
  127.         {
  128.             for (ll i=0;i<=(m+1);i++)
  129.             {
  130.                 ll temp=power(2*m-i,n);
  131.                 temp=(temp*binomial_coefficient(m+1,i))%MOD;
  132.                 if ((i%2)==1)
  133.                 {
  134.                     temp=(-temp+MOD)%MOD;
  135.                 }
  136.                 answer=(answer+temp)%MOD;
  137.             }
  138.         }
  139.         cout<<answer<<"\n";
  140.     }
  141.  
  142.     return 0;
  143. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
2
3
stdout
copy 
2
12
https://ideone.com/rzP3jW
language:
C++14 (clang 8.0)
created:
203 days ago
visibility:
secret

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!