2020 ICPC Shanghai Site E. The Journey of Geor Autumn

問題ページ

dp[長さiの数列] = 何通り とDPをする。

1をi番目に置く

• [1,i) は自由においてok → P(n-1, i-1)
• (i,n] は dp[n-i] 通り

の累積和をもちつつ更新すれば

▶ソースコード(クリックで展開)

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#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> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
constexpr ll MOD = 998244353;  
  
ll modpow(ll x, ll y, ll m) {  
    ll a = 1, p = x;  
    while(y > 0) {  
        if(y%2 == 0) {p = (p*p) % m; y /= 2;}  
        else {a = (a*p) % m; y--;}  
    }  
    return a;  
}  
  
int main() {  
    ll n, k;  
    cin >> n >> k;  
  
    vector<ll> fac(n+1), inv(n+1);  
    fac[0] = 1;  
    FOR(i, 1, n+1) fac[i] = fac[i-1] * i % MOD;  
    inv[n] = modpow(fac[n], MOD-2, MOD);  
    for(ll i=n-1; i>=0; --i) inv[i] = inv[i+1] * (i+1) % MOD;  
  
    vector<ll> dp(n+1), sum(n+1);  
    dp[0] = sum[0] = 1;  
    FOR(i, 1, n+1) {  
        dp[i] = fac[i-1] * (sum[i-1] - (i-k-1>=0 ? sum[i-k-1] : 0)) % MOD;  
        dp[i] = (dp[i] + MOD) % MOD;  
        sum[i] = (sum[i-1] + dp[i] * inv[i] % MOD) % MOD;  
    }  
    cout << (dp[n] % MOD + MOD) % MOD << endl;  
  
    return 0;  
}