Submission #19713586


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);
            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 0
Code Size 7813 Byte
Status WA
Exec Time 443 ms
Memory 12224 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
AC × 3
AC × 21
WA × 7
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 16 ms 11744 KB
001.txt AC 12 ms 11744 KB
002.txt AC 27 ms 12168 KB
003.txt AC 38 ms 12068 KB
004.txt AC 109 ms 12072 KB
005.txt AC 235 ms 12224 KB
006.txt AC 309 ms 12220 KB
007.txt WA 387 ms 12132 KB
008.txt WA 423 ms 12064 KB
009.txt WA 436 ms 12084 KB
010.txt WA 443 ms 12136 KB
011.txt AC 443 ms 12144 KB
012.txt AC 10 ms 11756 KB
013.txt AC 12 ms 11680 KB
014.txt AC 13 ms 11656 KB
015.txt AC 14 ms 11724 KB
016.txt AC 236 ms 12032 KB
017.txt AC 11 ms 11772 KB
018.txt AC 18 ms 11756 KB
019.txt AC 14 ms 11804 KB
020.txt WA 100 ms 12188 KB
021.txt AC 276 ms 12044 KB
022.txt AC 65 ms 12072 KB
023.txt WA 224 ms 12068 KB
024.txt WA 124 ms 12048 KB
example0.txt AC 11 ms 11748 KB
example1.txt AC 12 ms 11772 KB
example2.txt AC 69 ms 12040 KB