結果
問題 | No.3062 Rotate and Maximize |
ユーザー |
|
提出日時 | 2025-03-14 23:10:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 4,598 bytes |
コンパイル時間 | 2,618 ms |
コンパイル使用メモリ | 214,572 KB |
実行使用メモリ | 15,616 KB |
最終ジャッジ日時 | 2025-03-14 23:10:10 |
合計ジャッジ時間 | 5,191 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long mod = 998244353; //入力が必ず-mod<a<modの時. struct mint{ long long v = 0; mint(){} mint(int a){v = a<0?a+mod:a;} mint(long long a){v = a<0?a+mod:a;} mint(unsigned long long a){v = a;} long long val(){return v;} void modu(){v %= mod;} mint repeat2mint(const long long a,long long b){ mint ret = 1,p = a; while(b){ if(b&1) ret *= p; p *= p; b >>= 1; } return ret; }; mint &operator=(const mint &b) = default; mint operator-() const {return mint(0)-(*this);} mint operator+(const mint b){return mint(v)+=b;} mint operator-(const mint b){return mint(v)-=b;} mint operator*(const mint b){return mint(v)*=b;} mint operator/(const mint b){return mint(v)/=b;} mint operator+=(const mint b){ v += b.v; if(v >= mod) v -= mod; return *this; } mint operator-=(const mint b){ v -= b.v; if(v < 0) v += mod; return *this; } mint operator*=(const mint b){v = v*b.v%mod; return *this;} mint operator/=(mint b){ if(b == 0) assert(false); int left = mod-2; while(left){if(left&1) *this *= b; b *= b; left >>= 1;} return *this; } mint operator++(int){*this += 1; return *this;} mint operator--(int){*this -= 1; return *this;} bool operator==(const mint b){return v == b.v;} bool operator!=(const mint b){return v != b.v;} bool operator>(const mint b){return v > b.v;} bool operator>=(const mint b){return v >= b.v;} bool operator<(const mint b){return v < b.v;} bool operator<=(const mint b){return v <= b.v;} mint pow(const long long x){return repeat2mint(v,x);} mint inv(){return mint(1)/v;} }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> A(N); for(auto &a : A) cin >> a,a--; vector<int> start; for(int i=0; i<N; i++) if(A.at(i) == N-1) start.push_back(i); if(start.size() == 0){cout << "0\n"; return 0;} vector<pair<int,vector<int>>> B; for(auto s : start){ vector<int> now = {N-1}; for(int i=(s+1)%N; ; i=(i+1)%N){ if(A.at(i) == N-1) break; now.push_back(A.at(i)); } B.emplace_back(pair{s,now}); } sort(B.begin(),B.end(),[&](auto &a,auto &b){return a.second.size()<b.second.size();}); /* for(int i=B.size()-1; i<B.size(); i++){ vector<int> now1 = B.at(i).second; for(int k=i-1; k>=0; k--){ vector<int> now2 = B.at(k).second; while(now1.size() > now2.size()) now1.pop_back(); if(now1 != now2){cout << "0\n"; return 0;} } } */ { auto [p,ign] = B.back(); rotate(A.begin(),A.begin()+p,A.end()); for(auto &[s,ign] : B) s = (s-p+N)%N; start.clear(); for(int i=0; i<N; i++) if(A.at(i) == N-1) start.push_back(i); } vector<vector<int>> check(N); for(auto s : start) for(int i=0; i<N; i++){ int pos = (s+i)%N; if(A.at(pos) == N-1) continue; check.at(pos).push_back(i); } vector<vector<int>> sepa(N); for(int i=0; i<N; i++) sepa.at(A.at(i)).push_back(i); mint answer = 1; int hold = 0; vector<bool> already(N); for(int i=0; i<N-1; i++){ hold++; if(sepa.at(i).size() == 0) continue; vector<int> count(N); for(auto g : sepa.at(i)) for(auto c : check.at(g)) count.at(c)++; int kouho = 0; vector<int> all; for(int k=0; k<N; k++){ if(count.at(k) == sepa.at(i).size() && !already.at(k)){ kouho++; if(kouho == 1) already.at(k) = true; } if(count.at(k) > 0 && !already.at(k)) all.push_back(k); } answer *= kouho; hold--; for(auto &p : all) answer *= hold,hold--,already.at(p) = true; if(hold < 0){cout << "0\n"; return 0;} } while(hold > 0) answer *= hold,hold--; answer *= N; cout << answer.v << "\n"; return 0; vector<int> AA(N); iota(AA.begin(),AA.end(),0); int answer2 = 0; do{ if(AA.at(0) != N-1) continue; vector<int> now(N); for(int i=0; i<N; i++) if(A.at(i) == N-1){ for(int k=0; k<N; k++){ int pos = (i+k)%N; now.at(pos) = max(now.at(pos),AA.at(k)); } } if(now == A) answer2++; }while(next_permutation(AA.begin(),AA.end())); cout << answer2*N << endl; }