結果
問題 | No.1392 Don't be together |
ユーザー |
![]() |
提出日時 | 2021-02-13 18:04:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 3,004 bytes |
コンパイル時間 | 1,073 ms |
コンパイル使用メモリ | 107,928 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 21:16:52 |
合計ジャッジ時間 | 3,877 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<vector>#include<cmath>#include<algorithm>#include<map>#include<queue>#include<deque>#include<iomanip>#include<tuple>#include<cassert>#include<set>#include<complex>#include<numeric>#include<functional>#include<unordered_map>#include<unordered_set>using namespace std;typedef long long int LL;typedef pair<int,int> P;typedef pair<LL,int> LP;const int INF=1<<30;const LL MAX=998244353;void array_show(int *array,int array_n,char middle=' '){for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));}void array_show(LL *array,int array_n,char middle=' '){for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));}void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){if(vec_n==-1)vec_n=vec_s.size();for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));}void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){if(vec_n==-1)vec_n=vec_s.size();for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));}long long int pow_mod(long long int a,long long int n,long long int p=1e9+7){//a^n mod plong long int b=1,t=1;for(;b<=n;b<<=1);for(b>>=1;b>0;b>>=1){t*=t;if(t>=p)t%=p;if(n&b)t*=a;if(t>=p)t%=p;}return t;}long long int gcd(long long int a,long long int b){if(a<b)gcd(b,a);if(b==0)return a;return gcd(b,a%b);}long long int divide(long long int a,long long int b,long long int p=1e9+7){// a/b mod p// prime:p is primeif(a>=p)a%=p;if(a<0)a+=p;if(b>=p)b%=p;if(b<0)b+=p;a*=pow_mod(b,p-2,p);return a%p;}namespace sol{int n;bool used[5555];vector<LL> va;LL calc(int m){vector<LL> v1(n+10);v1[1]=m;v1[2]=m*(m-1);LL a=m*(m-1);for(int i=3;i<=n;i++){a=a*(m-1)%MAX;v1[i]=a-v1[i-1];if(v1[i]<0)v1[i]+=MAX;v1[i]%=MAX;}a=1;for(auto num:va){a=a*v1[num]%MAX;}return a;}void solve(){int m;int i,j,k;LL a,b,c;cin>>n>>m;vector<int> vp(n);for(i=0;i<n;i++){cin>>vp[i];vp[i]--;}for(i=0;i<n;i++){if(used[i])continue;used[i]=true;a=vp[i];for(j=1;a!=i;j++){used[a]=true;a=vp[a];}va.push_back(j);}a=0,b=1;for(i=0;i<m;i++){c=b*calc(m-i)%MAX;if(i%2==0)a+=c;else a-=c;if(a<0)a+=MAX;a%=MAX;b*=m-i;b=divide(b,i+1,MAX);}for(i=1;i<=m;i++){a=divide(a,i,MAX);}cout<<a<<endl;}}int main(){sol::solve();}