結果
問題 | No.1392 Don't be together |
ユーザー |
![]() |
提出日時 | 2021-02-13 15:44:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 253 ms / 2,000 ms |
コード長 | 3,863 bytes |
コンパイル時間 | 1,812 ms |
コンパイル使用メモリ | 174,292 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 18:37:29 |
合計ジャッジ時間 | 6,198 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>#include <numeric>using namespace std;// using mint = long double;// using mint = modint998244353;// using mint = modint1000000007;typedef long long ll;typedef pair<ll, ll> P;typedef pair<P, ll> T;typedef pair<ll, vector<ll> > Pd;const ll INF = 1e18;const ll fact_table = 32008;priority_queue <ll> pql;priority_queue <P> pqp;//big priority queue// priority_queue <ll, vector<ll>, greater<ll> > pqls;priority_queue <P, vector<P>, greater<P> > pqps;//small priority queue//top popll dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};ll dy[8] = {0, 1, 0, -1, -1, 1, 1, -1};//↓,→,↑,←/*#define endl "\n"#ifdef ENJAPMA#undef endl#endif*/#define p(x) cout<<x<<endl;#define el cout<<endl;#define pe(x) cout<<x<<" ";#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;#define pu(x) cout<<(x);#define pb push_back#define lb lower_bound#define ub upper_bound#define pc(x) cout << x << ",";#define rep(i, n) for (ll i = 0; i < (n); i ++)#define rep2(i, a, b) for (ll i = a; i <= (b); i++)#define rep3(i, a, b) for (ll i = a; i >= (b); i--)typedef vector<ll> vec;typedef vector<vector<ll>> mat;// vec v(n) -> 長さnのベクトルを宣言// mat dp(h, vec(w)) -> h * w の行列を宣言const ll mod = 998244353ll;// const ll mod = 1000000007ll;ll mypow(ll a, ll b, ll m = mod) {ll x = 1; while (b) {while (!(b & 1)) {(a *= a) %= m; b >>= 1;}(x *= a) %= m; b--;} return x;}vec rv(ll read) { vec res(read); for (int i = 0; i < read; i++) { cin >> res[i]; } return res;}void YES(bool cond) { if (cond) { p("YES");} else { p("NO");} return;}void Yes(bool cond) { if (cond) { p("Yes");} else { p("No");} return;}void line() { p("--------------------"); return;}ll fact[fact_table + 5], rfact[fact_table + 5];void c3_init() {fact[0] = rfact[0] = 1;for (ll i = 1; i <= fact_table; i++) {fact[i] = (fact[i - 1] * i) % mod;}rfact[fact_table] = mypow(fact[fact_table], mod - 2, mod);for (ll i = fact_table; i >= 1; i--) {rfact[i - 1] = rfact[i] * i;rfact[i - 1] %= mod;}return;}ll c3(ll n, ll r) {return (((fact[n] * rfact[r]) % mod ) * rfact[n - r]) % mod;}bool icpc = false;bool multicase = false;ll n, m;ll p[5005];ll x[5005];bool used[5005];ll dp[5005][3];ll dfs(ll color, ll i, ll par) {if (used[i]) {// 清算を行うreturn dp[par][0];}used[i] = true;if (par == -1) {dp[i][0] = 0;dp[i][1] = color;} else {dp[i][1] += dp[par][0];dp[i][0] += dp[par][1] * (color - 1) % mod;dp[i][0] += dp[par][0] * (color - 2) % mod;dp[i][0] %= mod;}return dfs(color, p[i], i);}bool solve() {cin >> n >> m;c3_init();for (int i = 1; i <= n; i++) {cin >> p[i];}for (int color = 1; color <= m; color ++) {ll res = 1ll;for (int i = 1; i <= n; i++) {used[i] = false;dp[i][0] = dp[i][1] = 0;}for (int i = 1; i <= n; i++) {if (!used[i]) {res *= dfs(color, i, -1);res %= mod;}}x[color] = res;}ll ans = 0ll;ll flag = 1ll;for (int color = m; color >= 1; color --) {ans += ((x[color] * flag) % mod) * c3(m, color) % mod;flag = (mod - flag);ans %= mod;}ans *= rfact[m];ans %= mod;p(ans);return true;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);if (icpc) {while (solve());return 0;}ll q, testcase = 1;if (multicase) {cin >> q;} else {q = 1;}while (q--) {// pu("Case ");pu("#");pu(testcase);pu(": ");solve();testcase++;}// solve();return 0;}