fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. // #pragma GCC optimize("Ofast,unroll-loops,fast-math")
  4. // #pragma GCC target("avx2,sse4,bmi,popcnt")
  5. #define int long long
  6. #define REP(i,n) for(int i=0;i<(n);i++)
  7. #define REP1(i,n) for(int i=1;i<=(n);i++)
  8. #define RREP(i,n) for(int i=(n)-1;i>=0;i--)
  9. #define RREP1(i,n) for(int i=(n);i>=1;i--)
  10. #define f first
  11. #define s second
  12. #define pb push_back
  13. #define ALL(x) (x).begin(),(x).end()
  14. #define ALL1(x) (x).begin()+1,(x).end()
  15. #define SZ(x) (int)((x).size())
  16. #define SQ(x) (x)*(x)
  17. #define pii pair<int,int>
  18. #define pipii pair<int,pii>
  19. #define Graph vector<vector<int>>
  20. #define Graphw vector<vector<pii>>
  21. #define IOS() ios::sync_with_stdio(0),cin.tie(0)
  22. #define md(x) (((x)%(mod)+(mod))%(mod))
  23. #define MD(x,M) (((x)%(M)+(M))%(M))
  24. #define ld long double
  25. #define pdd pair<ld,ld>
  26. #define chmax(x,y) x=max(x,y)
  27. #define chmin(x,y) x=min(x,y)
  28. #define addmod(x,y) x=((x+(y))%mod)
  29. #define Vi vector<int>
  30. #ifdef LOCAL
  31. #define op(x) cout<<(#x)<<"="<<(x)<<", ";
  32. #define ope(x) cout<<(#x)<<"="<<(x)<<endl;
  33. #define oparr(x) cout<<(#x)<<":";for(auto &mken:(x)) cout<<mken<<" ";cout<<" size="<<(x).size()<<endl;
  34. #define entr cout<<endl;
  35. #else
  36. #define op(x) ;
  37. #define ope(x) ;
  38. #define oparr(x) ;
  39. #define entr ;
  40. #endif
  41. const int mod=30011;
  42. const int maxn=2e4+5;
  43. const int maxn2=2e5+5;
  44. const int maxb=20;
  45. const int inf=(1ll<<62); 
  46. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  47. int rd(int l,int r) {
  48.     return uniform_int_distribution<int>(l,r)(rng);
  49. }
  50. int pw(int x,int p) {
  51.     int r=1;
  52.     while(p>0) {
  53.         if(p&1) r=r*x%mod;
  54.         x=x*x%mod;
  55.         p>>=1;
  56.     }
  57.     return r;
  58. }
  59. int inv(int x) { 
  60.     return pw(x,mod-2);
  61. }
  62. Vi fac(maxn),infac(maxn);
  63. int C(int n,int k) {
  64.     return (fac[n]*infac[k]%mod)*infac[n-k]%mod;
  65. }
  66. bool isp(int n) {
  67.     for(int i=2;i*i<=n;i++) if(n%i==0) return 0;return 1;
  68. }
  69. int dp(int n,int k) {
  70.     if(k<0) return 0;
  71.     if(k==0) return 1;
  72.     int r=0;
  73.     int x=__lg(k + 1),y=k-(1<<x);
  74.     for(int i=0;i<=n;i+=2) {
  75.         addmod(r,(i==n?dp(i,y):pw(y+1,i)*pw(2,x*(n-i-1)))*C(n,i));
  76.     }
  77.     return r;
  78. }
  79. signed main() {
  80.     IOS();
  81.     fac[0]=1;
  82.     REP1(i,maxn-1) fac[i]=fac[i-1]*i%mod;
  83.     infac[maxn-1]=inv(fac[maxn-1]);
  84.     RREP(i,maxn-1) infac[i]=infac[i+1]*(i+1)%mod;
  85.     int n,k;
  86.     cin>>n>>k;
  87.     int r=dp(n,k);
  88.     int an=pw(k+1,n)-r;
  89.     an=(an+mod)%mod;
  90.     cout<<an<<'\n';
  91.     return 0;
  92. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10000 7
stdout
copy 
26593
https://ideone.com/38At3X
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!