TOJ 564
題敘
https://toj.tfcis.org/oj/pro/564/
給一個序列,如果求該敘列有多少種回文排列方式
想法
如果說序列中相同元素各數有一種以上是奇數,可以保證一定無解
因為要排成回文,我們可以只看一半,而另一半的答案會隨之確定
其他情況下,將所有相同數字的元素數量切半來看,排列好
最後將不同數字排列,就可以獲得答案
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include <bits/stdc++.h> #define int long long #define pii pair<int,int> using namespace std; const int N = 1e6+10; const int mod = 1e9+7; int n,arr[N],cnt[N],ans=1,odd=0,diff=0; int p(int x,int y){ int ret=1; y++; while(y<=x){ ret*=y; ret%=mod; y++; } return ret; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=0 ; i<n ; i++){ cin>>arr[i]; } sort(arr,arr+n); int j=0; for(int i=0 ; i<n ; i++){ if(i==0 || arr[i]==arr[i-1]) cnt[j]++; else cnt[++j]++; } for(int i=0,k ; i<=j ; i++){ if(cnt[i]%2) odd++; ans*=p(cnt[i],cnt[i]/2); ans%=mod; diff+=cnt[i]/2; } for(int i=1 ; i<=diff ; i++){ ans*=i; ans%=mod; } if(odd>1) cout<<0<<"\n"; else cout<<ans<<"\n"; }
|
複雜度
大約為 $O(不同數字數量)$