結果
問題 | No.1392 Don't be together |
ユーザー |
![]() |
提出日時 | 2021-02-12 21:47:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 217 ms / 2,000 ms |
コード長 | 21,660 bytes |
コンパイル時間 | 2,554 ms |
コンパイル使用メモリ | 219,008 KB |
最終ジャッジ日時 | 2025-01-18 18:19:10 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
コンパイルメッセージ
In destructor ‘Permutation::~Permutation()’, inlined from ‘int main()’ at main.cpp:1039:1: main.cpp:815:17: warning: ‘P.Permutation::dat’ may be used uninitialized [-Wmaybe-uninitialized] 815 | delete [] dat; | ^~~ main.cpp: In function ‘int main()’: main.cpp:1017:15: note: ‘P.Permutation::dat’ was declared here 1017 | Permutation P(N); | ^
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;#define MD (998244353U)void*wmem;char memarr[96000000];template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );(*arr)=(T*)(*mem);(*mem)=((*arr)+x);}template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){walloc1d(arr, x2-x1, mem);(*arr) -= x1;}struct Modint{unsigned val;Modint(){val=0;}Modint(int a){val = ord(a);}Modint(unsigned a){val = ord(a);}Modint(long long a){val = ord(a);}Modint(unsigned long long a){val = ord(a);}inline unsigned ord(unsigned a){return a%MD;}inline unsigned ord(int a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned ord(unsigned long long a){return a%MD;}inline unsigned ord(long long a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned get(){return val;}inline Modint &operator+=(Modint a){val += a.val;if(val >= MD){val -= MD;}return *this;}inline Modint &operator-=(Modint a){if(val < a.val){val = val + MD - a.val;}else{val -= a.val;}return *this;}inline Modint &operator*=(Modint a){val = ((unsigned long long)val*a.val)%MD;return *this;}inline Modint &operator/=(Modint a){return *this *= a.inverse();}inline Modint operator+(Modint a){return Modint(*this)+=a;}inline Modint operator-(Modint a){return Modint(*this)-=a;}inline Modint operator*(Modint a){return Modint(*this)*=a;}inline Modint operator/(Modint a){return Modint(*this)/=a;}inline Modint operator+(int a){return Modint(*this)+=Modint(a);}inline Modint operator-(int a){return Modint(*this)-=Modint(a);}inline Modint operator*(int a){return Modint(*this)*=Modint(a);}inline Modint operator/(int a){return Modint(*this)/=Modint(a);}inline Modint operator+(long long a){return Modint(*this)+=Modint(a);}inline Modint operator-(long long a){return Modint(*this)-=Modint(a);}inline Modint operator*(long long a){return Modint(*this)*=Modint(a);}inline Modint operator/(long long a){return Modint(*this)/=Modint(a);}inline Modint operator-(void){Modint res;if(val){res.val=MD-val;}else{res.val=0;}return res;}inline operator bool(void){return val!=0;}inline operator int(void){return get();}inline operator long long(void){return get();}inline Modint inverse(){int a = val;int b = MD;int u = 1;int v = 0;int t;Modint res;while(b){t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}if(u < 0){u += MD;}res.val = u;return res;}inline Modint pw(unsigned long long b){Modint a(*this);Modint res;res.val = 1;while(b){if(b&1){res *= a;}b >>= 1;a *= a;}return res;}inline bool operator==(int a){return ord(a)==val;}inline bool operator!=(int a){return ord(a)!=val;}};inline Modint operator+(int a, Modint b){return Modint(a)+=b;}inline Modint operator-(int a, Modint b){return Modint(a)-=b;}inline Modint operator*(int a, Modint b){return Modint(a)*=b;}inline Modint operator/(int a, Modint b){return Modint(a)/=b;}inline Modint operator+(long long a, Modint b){return Modint(a)+=b;}inline Modint operator-(long long a, Modint b){return Modint(a)-=b;}inline Modint operator*(long long a, Modint b){return Modint(a)*=b;}inline Modint operator/(long long a, Modint b){return Modint(a)/=b;}inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar_unlocked('-');}while(s--){my_putchar_unlocked(f[s]+'0');}}inline void wt_L(Modint x){int i;i = (int)x;wt_L(i);}template<class S, class T> inline S chmax(S &a, T b){if(a<b){a=b;}return a;}template<class T> struct Comb{int mem_fact;T*factri;T*ifactri;int mem_dfact;T*dfactri;int mem_pw2;int mem_pw3;int mem_pw10;int mem_rep1;T*pw2c;T*pw3c;T*pw10c;T*rep1c;int mem_ipw2;int mem_ipw3;int mem_ipw10;T*ipw2c;T*ipw3c;T*ipw10c;Comb(){mem_fact = 0;mem_dfact = 0;mem_pw2 = mem_pw3 = mem_pw10 = mem_rep1 = 0;mem_ipw2 = mem_ipw3 = mem_ipw10 = 0;}inline void expand_fact(int k){int i;if(k <= mem_fact){return;}chmax(k, 2 * mem_fact);if(mem_fact == 0){factri = (T*)malloc(k * sizeof(T));ifactri = (T*)malloc(k * sizeof(T));factri[0] = 1;for(i=(1);i<(k);i++){factri[i] = i * factri[i-1];}ifactri[k-1] = 1 / factri[k-1];for(i=(k-1)-1;i>=(0);i--){ifactri[i] = (i+1) * ifactri[i+1];}}else{factri = (T*)realloc(factri, k * sizeof(T));ifactri = (T*)realloc(ifactri, k * sizeof(T));for(i=(mem_fact);i<(k);i++){factri[i] = i * factri[i-1];}ifactri[k-1] = 1 / factri[k-1];for(i=(k-1)-1;i>=(mem_fact);i--){ifactri[i] = (i+1) * ifactri[i+1];}}mem_fact = k;}inline T fac(int k){if(mem_fact < k+1){expand_fact(k+1);}return factri[k];}inline T ifac(int k){if(mem_fact < k+1){expand_fact(k+1);}return ifactri[k];}inline T C(int a, int b){if(b < 0 || b > a){return 0;}if(mem_fact < a+1){expand_fact(a+1);}return factri[a] * ifactri[b] * ifactri[a-b];}inline T P(int a, int b){if(b < 0 || b > a){return 0;}if(mem_fact < a+1){expand_fact(a+1);}return factri[a] * ifactri[a-b];}inline T H(int a, int b){if(a==0 && b==0){return 1;}if(a <= 0 || b < 0){return 0;}if(mem_fact < a+b){expand_fact(a+b);}return C(a+b-1, b);}inline T Multinomial(int sz, int a[]){int i;int s = 0;T res;for(i=(0);i<(sz);i++){s += a[i];}if(mem_fact < s+1){expand_fact(s+1);}res = factri[s];for(i=(0);i<(sz);i++){res *= ifactri[a[i]];}return 1;}inline T Multinomial(int a){return 1;}inline T Multinomial(int a, int b){if(mem_fact < a+b+1){expand_fact(a+b+1);}return factri[a+b] * ifactri[a] * ifactri[b];}inline T Multinomial(int a, int b, int c){if(mem_fact < a+b+c+1){expand_fact(a+b+c+1);}return factri[a+b+c] * ifactri[a] * ifactri[b] * ifactri[c];}inline T Multinomial(int a, int b, int c, int d){if(mem_fact < a+b+c+d+1){expand_fact(a+b+c+d+1);}return factri[a+b+c+d] * ifactri[a] * ifactri[b] * ifactri[c] * ifactri[d];}inline T Catalan(int n){if(n < 0){return 0;}if(mem_fact < 2*n+1){expand_fact(2*n+1);}return factri[2*n] * ifactri[n] * ifactri[n+1];}inline T C_s(long long a, long long b){long long i;T res;if(b < 0 || b > a){return 0;}if(b > a - b){b = a - b;}res = 1;for(i=(0);i<(b);i++){res *= a - i;res /= i + 1;}return res;}inline T P_s(long long a, long long b){long long i;T res;if(b < 0 || b > a){return 0;}res = 1;for(i=(0);i<(b);i++){res *= a - i;}return res;}inline T per_s(long long n, long long k){T d;int m;if(n < 0 || k < 0){return 0;}if(n == k && k == 0){return 1;}if(n == 0 || k == 0){return 0;}if(k==1){return 1;}if(k==2){d = n / 2;return d;}if(k==3){d = (n-1) / 6;m = (n-1) % 6;if(m==0){return 3 * d * d + d;}if(m==1){return 3 * d * d + 2 * d;}if(m==2){return 3 * d * d + 3 * d + 1;}if(m==3){return 3 * d * d + 4 * d + 1;}if(m==4){return 3 * d * d + 5 * d + 2;}if(m==5){return 3 * d * d + 6 * d + 3;}}assert(0 && "per_s should be k <= 3");return -1;}inline void expand_dfact(int k){int i;if(k <= mem_dfact){return;}chmax(k, 3);chmax(k, 2 * mem_dfact);if(mem_dfact==0){dfactri = (T*)malloc(k * sizeof(T));dfactri[0] = dfactri[1] = 1;for(i=(2);i<(k);i++){dfactri[i] = i * dfactri[i-2];}}else{dfactri = (T*)realloc(dfactri, k * sizeof(T));for(i=(mem_dfact);i<(k);i++){dfactri[i] = i * dfactri[i-2];}}mem_dfact = k;}inline void expand_pw2(int k){int i;if(k <= mem_pw2){return;}chmax(k, 2 * mem_pw2);if(mem_pw2==0){pw2c = (T*)malloc(k * sizeof(T));pw2c[0] = 1;for(i=(1);i<(k);i++){pw2c[i] = 2 * pw2c[i-1];}}else{pw2c = (T*)realloc(pw2c, k * sizeof(T));for(i=(mem_pw2);i<(k);i++){pw2c[i] = 2 * pw2c[i-1];}}mem_pw2 = k;}inline void expand_ipw2(int k){int i;if(k <= mem_ipw2){return;}chmax(k, 2);chmax(k, 2 * mem_ipw2);if(mem_ipw2==0){ipw2c = (T*)malloc(k * sizeof(T));ipw2c[0] = 1;ipw2c[1] = ipw2c[0] / 2;for(i=(1);i<(k);i++){ipw2c[i] = ipw2c[1] * ipw2c[i-1];}}else{ipw2c = (T*)realloc(ipw2c, k * sizeof(T));for(i=(mem_ipw2);i<(k);i++){ipw2c[i] = ipw2c[1] * ipw2c[i-1];}}mem_ipw2 = k;}inline void expand_pw3(int k){int i;if(k <= mem_pw3){return;}chmax(k, 2 * mem_pw3);if(mem_pw3==0){pw3c = (T*)malloc(k * sizeof(T));pw3c[0] = 1;for(i=(1);i<(k);i++){pw3c[i] = 3 * pw3c[i-1];}}else{pw3c = (T*)realloc(pw3c, k * sizeof(T));for(i=(mem_pw3);i<(k);i++){pw3c[i] = 3 * pw3c[i-1];}}mem_pw3 = k;}inline void expand_ipw3(int k){int i;if(k <= mem_ipw3){return;}chmax(k, 2);chmax(k, 2 * mem_ipw3);if(mem_ipw3==0){ipw3c = (T*)malloc(k * sizeof(T));ipw3c[0] = 1;ipw3c[1] = ipw3c[0] / 3;for(i=(1);i<(k);i++){ipw3c[i] = ipw3c[1] * ipw3c[i-1];}}else{ipw3c = (T*)realloc(ipw3c, k * sizeof(T));for(i=(mem_ipw3);i<(k);i++){ipw3c[i] = ipw3c[1] * ipw3c[i-1];}}mem_ipw3 = k;}inline void expand_pw10(int k){int i;if(k <= mem_pw10){return;}chmax(k, 2 * mem_pw10);if(mem_pw10==0){pw10c = (T*)malloc(k * sizeof(T));pw10c[0] = 1;for(i=(1);i<(k);i++){pw10c[i] = 10 * pw10c[i-1];}}else{pw10c = (T*)realloc(pw10c, k * sizeof(T));for(i=(mem_pw10);i<(k);i++){pw10c[i] = 10 * pw10c[i-1];}}mem_pw10 = k;}inline void expand_ipw10(int k){int i;if(k <= mem_ipw10){return;}chmax(k, 2);chmax(k, 2 * mem_ipw10);if(mem_ipw10==0){ipw10c = (T*)malloc(k * sizeof(T));ipw10c[0] = 1;ipw10c[1] = ipw10c[0] / 10;for(i=(1);i<(k);i++){ipw10c[i] = ipw10c[1] * ipw10c[i-1];}}else{ipw10c = (T*)realloc(ipw10c, k * sizeof(T));for(i=(mem_ipw10);i<(k);i++){ipw10c[i] = ipw10c[1] * ipw10c[i-1];}}mem_ipw10 = k;}inline void expand_rep1(int k){int i;if(k <= mem_rep1){return;}chmax(k, 2 * mem_rep1);if(mem_rep1==0){rep1c = (T*)malloc(k * sizeof(T));rep1c[0] = 0;for(i=(1);i<(k);i++){rep1c[i] = 10 * rep1c[i-1] + 1;}}else{rep1c = (T*)realloc(rep1c, k * sizeof(T));for(i=(mem_rep1);i<(k);i++){rep1c[i] = 10 * rep1c[i-1] + 1;}}mem_rep1 = k;}inline T dfac(int k){if(k >= 0){if(mem_dfact < k+1){expand_dfact(k+1);}return dfactri[k];}if(k==-1){return 1;}k = - k - 2;if(k % 4 == 1){return 1 / (-dfac(k));}return 1 / dfac(k);}inline T pw2(int k){if(k >= 0){if(mem_pw2 < k+1){expand_pw2(k+1);}return pw2c[k];}else{k = -k;if(mem_ipw2 < k+1){expand_ipw2(k+1);}return ipw2c[k];}}inline T pw3(int k){if(k >= 0){if(mem_pw3 < k+1){expand_pw3(k+1);}return pw3c[k];}else{k = -k;if(mem_ipw3 < k+1){expand_ipw3(k+1);}return ipw3c[k];}}inline T pw10(int k){if(k >= 0){if(mem_pw10 < k+1){expand_pw10(k+1);}return pw10c[k];}else{k = -k;if(mem_ipw10 < k+1){expand_ipw10(k+1);}return ipw10c[k];}}inline T repunit(int k){if(mem_rep1 < k+1){expand_rep1(k+1);}return rep1c[k];}};template<> inline Modint Comb<Modint>::C_s(long long a, long long b){long long i;Modint res;Modint d;if(b < 0 || b > a){return 0;}if(b > a - b){b = a - b;}res = d = 1;for(i=(0);i<(b);i++){res *= a - i;d *= i + 1;}return res / d;}template<class T> struct fenwick{int size;int memory;T*data;void malloc(int mem);void malloc(int mem, int fg);void walloc(int mem, void **workMemory = &wmem);void walloc(int mem, int fg, void **workMemory = &wmem);void free(void);void init(int N);void add(int k, T val);T get(int k);T range(int a, int b);int kth(T k);};struct Permutation{int n;int mem;int*dat;Permutation(){n = mem = 0;}Permutation(const int nn){n = mem = nn;if(mem > 0){dat = new int[mem];}}Permutation(const Permutation &a){int i;mem = n = a.n;dat = new int[mem];for(i=(0);i<(mem);i++){dat[i] = a.dat[i];}}~Permutation(){if(mem){delete [] dat;}}void changeSize(const int nn){n = nn;if(mem < n){if(mem){delete [] dat;}mem = n;dat = new int[mem];}}Permutation& operator=(const Permutation &a){int i;changeSize(a.n);n = a.n;for(i=(0);i<(n);i++){dat[i] = a.dat[i];}return *this;}Permutation& operator=(const int a){int i;for(i=(0);i<(n);i++){dat[i] = i;}return *this;}Permutation& operator*=(const Permutation &a){int i;int*m;void*mv = wmem;if(n==0 || n!=a.n){changeSize(0);return *this;}walloc1d(&m, n, &mv);for(i=(0);i<(n);i++){m[i] = dat[a.dat[i]];}for(i=(0);i<(n);i++){dat[i] = m[i];}return *this;}Permutation operator*(const Permutation &a){return Permutation(*this) *= a;}bool operator==(const Permutation &a){int i;if(n != a.n){return false;}for(i=(0);i<(n);i++){if(dat[i] != a.dat[i]){return false;}}return true;}template<class T> void apply(T A[]){int i;T*B;void*mv = wmem;walloc1d(&B, n, &mv);for(i=(0);i<(n);i++){B[dat[i]] = A[i];}for(i=(0);i<(n);i++){A[i] = B[i];}}template<class T> void apply(T A[], T B[]){int i;for(i=(0);i<(n);i++){B[dat[i]] = A[i];}}int cycle_len(int res[] = NULL){int i;int j;int k;int sz = 0;int*vis;void*mv = wmem;if(res==NULL){walloc1d(&res, n, &mv);}walloc1d(&vis, n, &mv);for(i=(0);i<(n);i++){vis[i] = 0;}for(i=(0);i<(n);i++){if(!vis[i]){k = 0;j = i;while(vis[j]==0){vis[j] = 1;j = dat[j];k++;}res[sz++] = k;}}return sz;}void cycle_len_EachElement(int res[]){int i;int j;int k;int sz = 0;int*vis;void*mv = wmem;walloc1d(&vis, n, &mv);for(i=(0);i<(n);i++){vis[i] = 0;}for(i=(0);i<(n);i++){if(!vis[i]){k = 0;j = i;while(vis[j]==0){vis[j] = 1;j = dat[j];k++;}j = i;while(vis[j]==1){res[j] = k;vis[j] = 2;j = dat[j];}}}}template<class T> inline T getIndex(void *mem = wmem){int i;fenwick<int> t;T res;T*fac;walloc1d(&fac,n,&mem);fac[0] = 1;for(i=(1);i<(n);i++){fac[i] = i * fac[i-1];}t.walloc(n,&mem);t.init(n);for(i=(0);i<(n);i++){t.add(i,1);}res = 0;for(i=(0);i<(n);i++){t.add(dat[i], -1);res += fac[n-1-i] * t.get(dat[i]-1);}return res;}inline int& operator[](const int a){return dat[a];}};template<class S> inline Permutation pow_L(Permutation a, S b){Permutation res;res.changeSize(a.n);res = 1;while(b){if(b&1){res *= a;}b >>= 1;a *= a;}return res;}int sz;int len[5000];Modint dp[2][5001];Modint solve(int N, int M){int i;Modint res = 1;if(M <= 0){return 0;}dp[1][1] = M;for(i=(2);i<(N+1);i++){dp[0][i] = dp[0][i-1] * (M-2) + dp[1][i-1] * (M-1);dp[1][i] = dp[0][i-1];}for(i=(0);i<(sz);i++){res *= dp[0][len[i]];}return res;}int main(){int i;wmem = memarr;int N;rd(N);int M;rd(M);Permutation P(N);Comb<Modint> c;Modint res = 0;{int cTE1_r3A;for(cTE1_r3A=(0);cTE1_r3A<(N);cTE1_r3A++){rd(P[cTE1_r3A]);P[cTE1_r3A] += (-1);}}sz = P.cycle_len(len);for(i=(0);i<(M);i++){if(i%2==0){res += solve(N,M-i) * c.C(M,i);}else{res -= solve(N,M-i) * c.C(M,i);}}res *= c.ifac(M);wt_L(res);wt_L('\n');return 0;}template<class T> void fenwick<T>::malloc(int mem){memory = mem;data = (T*)std::malloc(sizeof(T)*mem);}template<class T> void fenwick<T>::malloc(int mem, int fg){memory = mem;data = (T*)std::malloc(sizeof(T)*mem);if(fg){init(mem);}}template<class T> void fenwick<T>::walloc(int mem, void **workMemory /* = &wmem*/){memory = mem;walloc1d(&data, mem, workMemory);}template<class T> void fenwick<T>::walloc(int mem, int fg, void **workMemory /* = &wmem*/){memory = mem;walloc1d(&data, mem, workMemory);if(fg){init(mem);}}template<class T> void fenwick<T>::free(void){memory = 0;free(data);}template<class T> void fenwick<T>::init(int N){size = N;memset(data,0,sizeof(T)*N);}template<class T> void fenwick<T>::add(int k, T val){while(k < size){data[k] += val;k |= k+1;}}template<class T> T fenwick<T>::get(int k){T res = 0;while(k>=0){res += data[k];k = (k&(k+1))-1;}return res;}template<class T> T fenwick<T>::range(int a, int b){if(b==-1){b=size-1;}return get(b) - get(a-1);}template<class T> int fenwick<T>::kth(T k){int i=0;int j=size;int c;T v;while(i<j){c = (i+j)/2;v = get(c);if(v <= k){i=c+1;}else{j=c;}}return i==size?-1:i;}// cLay version 20210103-1 [bug fixed 2]// --- original code ---// #define MD 998244353// int sz, len[5000];// Modint dp[2][5001];//// Modint solve(int N, int M){// Modint res = 1;// if(M <= 0) return 0;// dp[1][1] = M;// rep(i,2,N+1){// dp[0][i] = dp[0][i-1] * (M-2) + dp[1][i-1] * (M-1);// dp[1][i] = dp[0][i-1];// }// rep(i,sz) res *= dp[0][len[i]];// return res;// }//// {// int @N, @M;// Permutation P(N);// Comb<Modint> c;// Modint res = 0;// rd((P--)(N));// sz = P.cycle_len(len);//// rep(i,M){// if(i%2==0) res += solve(N,M-i) * c.C(M,i);// else res -= solve(N,M-i) * c.C(M,i);// }// res *= c.ifac(M);// wt(res);// }