提出 #36767147

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;}
const int N = 10000000;
mint nq2[N+10]={0}; // n_{q=2}, q-number n, nq2[i]=1+q^1+q^2+..+q^i, q=2, nq2[i]=2**i-1
mint facq2[N+10]={1}; // fac_{q=2}, q-factor n, = nq2[0]*nq[1]*...*nq2[i]
mint ifacq2[N+10]; // ifac[i] = 1/facq[i]

int main(){
  int n=read(); // 2e5
  int b=read(); // 1e7
  rep(i,1,N+1) nq2[i] = nq2[i-1]*2+1;
  rep(i,1,N+1) facq2[i] = facq2[i-1]*nq2[i];
  ifacq2[N] = facq2[N].inv();
  per(i,0,N) ifacq2[i]=ifacq2[i+1]*nq2[i+1];
  // G(s) = \lbrack \mathbf{B-1}\rbrack_ 2 ! \lbrack \mathbf{s}\rbrack_ 2 ! \sum_{r=0}^s \left( \frac{2^{\frac{r(r+1)}{2}} }{ \lbrack \mathbf{B-1-r}\rbrack_ 2 ! \lbrack \mathbf{r}\rbrack_ 2 !}\right)\left(\frac{1}{\lbrack \mathbf{s-r} \rbrack_ 2 !}\right)
  vector<mint> h0(n+1);
  rep(i,0,min(n+1,b)) h0[i] = mint(2).pow((long long)i*(i+1)/2) * ifacq2[b-1-i] * ifacq2[i];
  vector<mint> h1(n+1);
  rep(i,0,n+1) h1[i] = ifacq2[i];
  vector<mint> g=atcoder::convolution(h0,h1);
  rep(i,0,n+1) g[i] *= facq2[b-1]*facq2[i];

  // stirling 反演
  // F(n) = \sum_{t=0}^n (-1)^{n-t} {n \brack t} G(t).
  vector<vector<mint> > stirling1 = {{1}}; // 第一类stirling数 f_n = \prod_{i=0}^{n-1} (i+x), 注意会有n=1的时候
  rep(i,0,n-1) stirling1.push_back({i,1});
  // stirling f_{n-1}
  while(stirling1.size()>1){ // 分治
    // printf("stir len = %d\n",(int)stirling1.size());
    rep(i,0,stirling1.size()/2) stirling1[i] = atcoder::convolution(stirling1[i*2],stirling1[i*2+1]);
    if(stirling1.size()&1) stirling1[stirling1.size()/2] = stirling1.back();
    stirling1.erase(stirling1.begin()+(stirling1.size()+1)/2,stirling1.end());
  }
  // rep(i,0,stirling1[0].size()) printf("stirling1[%d][%d] = %d\n",n-1,i,stirling1[0][i].val());
  auto f=[&](int n){
    mint v = 0;
    rep(i,0,n+1) v+= mint(-1).pow((n-i)%2) * stirling1[0][i] * g[i];
    return v;
  };
  mint twob=mint(2).pow(b); // 2**b
  mint good_n_1 = 1;
  rep(i,0,n-1) good_n_1*=(twob-i);
  mint good_n = good_n_1*(twob-(n-1));
  good_n_1-=f(n-1);
  stirling1[0]=atcoder::convolution(stirling1[0],{n-1,1}); // stirling f_{n}
  // rep(i,0,stirling1[0].size()) printf("stirling1[%d][%d] = %d\n",n,i,stirling1[0][i].val());
  good_n -= f(n);
  // printf("good[n] = %d\n",good_n.val());
  // printf("good[n-1] = %d\n",good_n_1.val());
  // ans=f[n]-f[n-1]*(2**B-N+1)
  printf("%d\n",(good_n-good_n_1*(twob-n+1)).val());
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int read()’:
./Main.cpp:11:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   11 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

ジャッジ結果