ferinの競プロ帳

競プロについてのメモ

ARC102 E - Stop. Otherwise...

問題ページ

考えたこと

  • 出目i,jを使わずにK面サイコロをN個降る組み合わせ数がわかればよさそう
  • dp[i][j] = (i面サイコロでj個振るときの出目の組み合わせ数) とする
  • これは実質パスカルの三角形なので dp[i][j] = dp[i-1][j] + dp[i][j-1] としてO(N^2)で求まる
  • i=5 が存在してはいけないときを考える
  • 出目がなんでもいいことを*と書く
  • 答えを求める式を包除っぽく書ける
  • ans = (*,*,*,*,…の組み合わせ数) - (1,4,*,*,…) - (2,3,*,*,…) + (1,4,2,3,*.*,…) となる
  • ans = dp[K][N] - dp[K][N-2] - dp[K][N-2] + dp[K][N-4]
  • 包除の係数はコンビネーションで書けるので各iについてO(N)くらいで求まる
  • O(KN)で求まる
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long int;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 998244353;

ll combi(ll N_, ll C_, ll mo=MOD) {
  const int NUM_=1e5+10;
  static ll fact[NUM_+1]={},factr[NUM_+1]={},inv[NUM_+1]={};
  auto binpow = [&](ll x, ll e) -> ll{
    ll a = 1, p = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % mo; e /= 2;}
      else {a = (a*p) % mo; e--;}
    }
    return a;
  };
  if (fact[0]==0) {
    fact[0] = factr[0] = inv[0] = 1;
    FOR(i, 1, NUM_+1) fact[i] = fact[i-1] * i % MOD;
    factr[NUM_] = binpow(fact[NUM_], mo-2);
    for(int i=NUM_-1; i>=0; --i) factr[i] = factr[i+1] * (i+1) % MOD;
    // fact[i] = fact[i-1] * i;
    // inv[i] = binpow(i, MOD-2);
    // factr[i] = factr[i-1] * inv[i];
  }
  if(C_<0 || C_>N_) return 0;
  // 前計算 O(max(N,K)) クエリ O(1)
  return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;
  // 前計算 O(max(N,K)log(mod)) クエリ O(K)
  // ll ret = 1;
  // for(;C_>0;N_--,C_--) (ret *= N_%MOD) %= MOD, (ret *= inv[C_]) %= MOD;
  // return ret;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, k;
  cin >> k >> n;

  auto dp = make_v<ll>(k+1,n+1);
  fill_v(dp, 0);
  dp[0][0] = 1;
  FOR(i, 1, k+1) REP(j, n+1) {
    if(j == 0) dp[i][j] = dp[i-1][j];
    else dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
  }

  FOR(i, 2, k+2) {
    int ans = 0;
    int now = n;
    REP(j, i/2+1) {
      if(now < 0) break;
      if(j%2==0) (ans += dp[k][now] * combi(i/2, j) % MOD) %= MOD;
      else (ans += (MOD - dp[k][now]) * combi(i/2, j) % MOD) %= MOD;
      now -= 2;
    }
    cout << ans << endl;
  }
  for(int i=k; i>=2; --i) {
    int ans = 0;
    int now = n;
    REP(j, i/2+1) {
      if(now < 0) break;
      if(j%2==0) (ans += dp[k][now] * combi(i/2, j) % MOD) %= MOD;
      else (ans += (MOD - dp[k][now]) * combi(i/2, j) % MOD) %= MOD;
      now -= 2;
    }
    cout << ans << endl;
  }

  return 0;
}