Submission #19713590


Source Code Expand

Copy
//*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//*/
 
#include <bits/stdc++.h>
 
// #include <atcoder/all>
 
using namespace std;
// using namespace atcoder;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
typedef long long ll;
// #define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
void YES(bool t=true) {cout<<(t?"YES":"NO")<<endl;}
void Yes(bool t=true) {cout<<(t?"Yes":"No")<<endl;}
void yes(bool t=true) {cout<<(t?"yes":"no")<<endl;}
void NO(bool t=true) {cout<<(t?"NO":"YES")<<endl;}
void No(bool t=true) {cout<<(t?"No":"Yes")<<endl;}
void no(bool t=true) {cout<<(t?"no":"yes")<<endl;}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
int popcount(ll t) { return __builtin_popcountll(t); }
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
// vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
struct Setup_io {
    Setup_io() {
        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cout << fixed << setprecision(25);
    }
} setup_io;
// const ll MOD = 1000000007;
const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'

const int MAXN = 555555;

vl fact(MAXN);
vl rfact(MAXN);

ll mod_pow(ll x, ll p, ll M = MOD) {
  if (p < 0) {
    x = mod_pow(x, M - 2, M);
    p = -p;
  }
  ll a = 1;
  while (p) {
    if (p % 2)
      a = a*x%M;
    x = x*x%M;
    p /= 2;
  }
  return a;
}

ll mod_inverse(ll a, ll M = MOD) {
  return mod_pow(a, M - 2, M);
}

void set_fact(ll n, ll M = MOD) {
  fact[0] = 1;
  for (ll i = 1; i <= n; i++) {
    fact[i] = i * fact[i - 1] % M;
  }
  rfact[n] = mod_inverse(fact[n], M);
  for (ll i = n - 1; i >= 0; i--) {
      rfact[i] = (i + 1) * rfact[i + 1] % M;
  }
}

//http://drken1215.hatenablog.com/entry/2018/06/08/210000
//n���傫��fact���v�Z�ł��Ȃ��Ƃ��̂ق��̌v�Z���@�ɂ‚��ď����Ă���
ll nCr(ll n, ll r, ll M = MOD) {
  if (r > n) return 0;
  assert(fact[2] == 2);
  ll ret = fact[n];
  if (rfact[r] == 0) {
    rfact[r] = mod_inverse(fact[r], M);
  }
  ret = (ret*rfact[r]) % M;
  if (rfact[n - r] == 0) {
    rfact[n - r] = mod_inverse(fact[n - r], M);
  }
  ret = (ret*rfact[n - r]) % M;
  return ret;
}

ll nHr(ll n, ll r) {
  return nCr(n+r-1, r);
}

ll solve(int n, int k, int idx) {
    int left = idx, right = n - 1 - left;
    vector<vll> dp(k, vll(left + 1, vl(right + 1)));
    vll free(left + 1, vl(right + 1));
    auto free2 = free;
    free[left][right] = 1;
    rep (_, left) {
        rep (i, left + 1) rep (j, right + 1) free2[i][j] = 0;

        rep (i, left + 1) rep (j, right + 1) {
            if (free[i][j] == 0) continue;
            ll rem = k - (left - i) - (right - j);
            ll suc = rem * mod_inverse(k) % MOD;
            if (suc != 0) {
                (free2[i - 1][j] += free[i][j] * suc % MOD) %= MOD;
            }
            (free2[i][j] += free[i][j] * (1 - suc) % MOD) %= MOD;
        }
        swap(free, free2);
    }
    rep (i, left + 1) rep (j, right + 1) {
        if (free[i][j] == 0) continue;
        assert(j == right);
        dp[0][i][right] = free[i][j];
    }
    
    ll ans = 0;
    rep (i, k) {
        // DEBUG(i);
        rep (i, left + 1) rep (j, right + 1) {
            free[i][j] = free2[i][j] = 0;
        }

        // DEBUG("dp");
        // rep (l, left + 1) {
        //     rep (r, right + 1) {
        //         cout << dp[i][l][r] << " ";
        //     }
        //     cout << endl;
        // }

        rep (l, left + 1) rep (r, right + 1) {
            if (dp[i][l][r] == 0) continue;
            ll rem = k - (left - l) - (right - r);
            ll suc = rem * mod_inverse(k - i) % MOD;
            (ans += suc * dp[i][l][r]) %= MOD;

            if (i == k - 1) continue;
            (free[l][r] += dp[i][l][r] * (1 - suc + MOD) % MOD) %= MOD;
        }
        if (i == k - 1) continue;

        // DEBUG_MAT(free);

        for (int u = idx + 1; u < n; u++) {
            rep (i, left + 1) rep (j, right + 1) {
                free2[i][j] = 0;
            }
            int rr = n - u - 1;
            rep (l, left + 1) rep (r, right + 1) {
                if (free[l][r] == 0) continue;
                if (rr >= r) {
                    (free2[l][r] += free[l][r]) %= MOD;
                }
                else {
                    ll rem = k - (left - l) - (right - r);
                    ll suc = rem * mod_inverse(k - i) % MOD;
                    if (rem != 0) {
                        (free2[l][r - 1] += free[l][r] * suc) %= MOD;
                    }
                    (free2[l][r] += free[l][r] * (1 - suc)) %= MOD;
                }
            }
            swap(free, free2);
        }
        // DEBUG_MAT(free);

        for (int u = 0; u < idx; u++) {
            rep (i, left + 1) rep (j, right + 1) {
                free2[i][j] = 0;
            }
            int rr = idx - u - 1;
            rep (l, left + 1) rep (r, right + 1) {
                if (free[l][r] == 0) continue;
                if (rr >= l) {
                    (free2[l][r] += free[l][r]) %= MOD;
                }
                else {
                    ll rem = k - (left - l) - (right - r);
                    ll suc = rem * mod_inverse(k - i - 1) % MOD;
                    if (rem != 0) {
                        (free2[l - 1][r] += free[l][r] * suc) %= MOD;
                    }
                    (free2[l][r] += free[l][r] * (1 - suc)) %= MOD;
                }
            }
            swap(free, free2);
        }

        // DEBUG_MAT(free);
        rep (l, left + 1) rep (r, right + 1) {
            if (free[l][r] == 0) continue;
            dp[i + 1][l][r] = free[l][r];
        }
    }
    return (ans + MOD) % MOD;
}

signed main() {
    int n, k;
    cin >> n >> k;
    ll sum = 0;
    rep (i, n) {
        ll ans = solve(n, k, i);
        cout << ans << endl;
        sum += ans;
    }
    // cout << sum % MOD << endl;
}

Submission Info

Submission Time
Task D - Shopping
User fuppy0716
Language C++ (GCC 9.2.1)
Score 1300
Code Size 7819 Byte
Status AC
Exec Time 442 ms
Memory 12252 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 28
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt AC 23 ms 11764 KB
001.txt AC 13 ms 11684 KB
002.txt AC 17 ms 12180 KB
003.txt AC 36 ms 12212 KB
004.txt AC 107 ms 12228 KB
005.txt AC 236 ms 12124 KB
006.txt AC 309 ms 12192 KB
007.txt AC 385 ms 12216 KB
008.txt AC 419 ms 12180 KB
009.txt AC 438 ms 12252 KB
010.txt AC 442 ms 12232 KB
011.txt AC 442 ms 12180 KB
012.txt AC 10 ms 11796 KB
013.txt AC 14 ms 11684 KB
014.txt AC 13 ms 11764 KB
015.txt AC 11 ms 11784 KB
016.txt AC 233 ms 12200 KB
017.txt AC 14 ms 11788 KB
018.txt AC 23 ms 11796 KB
019.txt AC 16 ms 11752 KB
020.txt AC 104 ms 12232 KB
021.txt AC 273 ms 12180 KB
022.txt AC 61 ms 12168 KB
023.txt AC 224 ms 12088 KB
024.txt AC 122 ms 12088 KB
example0.txt AC 9 ms 11788 KB
example1.txt AC 9 ms 11764 KB
example2.txt AC 73 ms 12036 KB