問題ページ
考えたこと
- 出目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;
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};
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;
}
if(C_<0 || C_>N_) return 0;
return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;
}
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;
}