結果
問題 | No.1392 Don't be together |
ユーザー |
|
提出日時 | 2021-02-12 23:38:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 210 ms / 2,000 ms |
コード長 | 4,389 bytes |
コンパイル時間 | 2,092 ms |
コンパイル使用メモリ | 199,060 KB |
最終ジャッジ日時 | 2025-01-18 19:54:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#line 2 "/home/defineprogram/Desktop/Library/template/template.cpp"#include <bits/stdc++.h>using namespace std;#define ll long long#define rep(i, n) for (int i = 0; i < n; i++)#define REP(i, n) for (int i = 1; i < n; i++)#define rev(i, n) for (int i = n - 1; i >= 0; i--)#define REV(i, n) for (int i = n - 1; i > 0; i--)#define all(v) v.begin(), v.end()#define PL pair<ll, ll>#define PI pair<int,int>#define len(s) (int)s.size()template <class T, class U>inline bool chmin(T &a, U b) {if (a > b) {a = b;return true;}return false;}template <class T, class U>inline bool chmax(T &a, U b) {if (a < b) {a = b;return true;}return false;}constexpr ll inf = 3e18;#line 3 "/home/defineprogram/Desktop/Library/math/extgcd.cpp"ll extGCD(ll a, ll b, ll &x, ll &y) {if (!b) {x = 1;y = 0;return a;}ll d = extGCD(b, a % b, y, x);y -= a / b * x;return d;}ll modinv(ll a, ll m) {ll x, y;extGCD(a, m, x, y);return (x % m + m) % m;}#line 4 "/home/defineprogram/Desktop/Library/math/modint.cpp"template <int MOD>struct mint {int32_t n;mint() : n(0) {}mint(ll x) : n(x >= 0 ? x % MOD : (MOD - (-x) % MOD) % MOD) {}mint &operator+=(const mint &p) {if ((n += p.n) >= MOD) n -= MOD;return *this;}mint &operator-=(const mint &p) {if ((n += MOD - p.n) >= MOD) n -= MOD;return *this;}mint &operator*=(const mint &p) {n = 1ll * n * p.n % MOD;return *this;}mint &operator/=(const mint &p) {*this *= p.inverse();return *this;}mint operator-() const { return mint(-n); }mint operator+(const mint &p) const { return mint(*this) += p; }mint operator-(const mint &p) const { return mint(*this) -= p; }mint operator*(const mint &p) const { return mint(*this) *= p; }mint operator/(const mint &p) const { return mint(*this) /= p; }bool operator==(const mint &p) const { return n == p.n; }bool operator!=(const mint &p) const { return n != p.n; }friend ostream &operator<<(ostream &os, const mint &p) {return os << p.n;}friend istream &operator>>(istream &is, mint &p) {int x;is >> x;p = mint(x);return is;}mint pow(int64_t x) const {mint res(1), mul(n);while (x > 0) {if (x & 1) res *= mul;mul *= mul;x >>= 1;}return res;}mint inverse() const {return mint(modinv(n,MOD));}};/*@brief mod int@docs docs/modint.md*/#line 3 "main.cpp"constexpr int mod=998244353;using modint=mint<mod>;#line 3 "/home/defineprogram/Desktop/Library/math/Combination.cpp"template <int MOD>struct Combination {using modint = mint<MOD>;vector<modint> perm, inv;Combination(int x = 1e6) {perm.resize(x);inv.resize(x);perm[0] = modint(1);REP(i, x + 1)perm[i] = perm[i - 1] * i;inv[x] = perm[x].pow(MOD - 2);for (int i = x - 1; i >= 0; i--) {inv[i] = inv[i + 1] * (i + 1);}}modint nCk(int x, int y) {if (x < y) return modint(0);return perm[x] * inv[x - y] * inv[y];}};/*@brief Combination (nCk)@docs docs/Combination.md*/#line 7 "main.cpp"Combination<mod> C;int N,M;int P[5005];bool used[5005];int main() {cin.tie(0); ios::sync_with_stdio(false);cin>>N>>M;rep(i,N){cin>>P[i];P[i]--;}modint ans=0;for(int i=2;i<=M;i++){modint tapi=1;memset(used,false,sizeof(used));rep(j,N)if(!used[j]){int cur=j;int cnt=0;do{used[cur]=true;cnt++;cur=P[cur];}while(cur!=j);modint dp[2],dp2[2];dp[0]=i;rep(k,cnt-2){swap(dp,dp2);dp[0]=dp[1]=0;dp[0]+=dp2[1];dp[1]+=dp2[0]*(i-1);dp[1]+=dp2[1]*(i-2);}modint res=dp[0]*(i-1)+dp[1]*(i-2);tapi*=res;}if((M-i)%2==0)ans+=C.nCk(M,i)*tapi;else ans-=C.nCk(M,i)*tapi;}REP(i,M+1)ans/=i;cout<<ans<<"\n";}