結果
問題 | No.1481 Rotation ABC |
ユーザー |
![]() |
提出日時 | 2021-04-16 20:54:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 2,594 bytes |
コンパイル時間 | 3,291 ms |
コンパイル使用メモリ | 182,276 KB |
最終ジャッジ日時 | 2025-01-20 19:08:21 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#include <list>#include <atcoder/all>#define popcount __builtin_popcountusing namespace std;using namespace atcoder;typedef long long ll;typedef pair<int, int> P;using mint=modint998244353;mint f[2000010], invf[2000010];void fac(int n){f[0]=1;for(ll i=1; i<=n; i++) f[i]=f[i-1]*i;invf[n]=f[n].inv();for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1);}mint comb(int x, int y){if(!(0<=y && y<=x)) return 0;return f[x]*invf[y]*invf[x-y];}int main(){int n; cin>>n;string s; cin>>s;// set<string> st;// queue<string> que;// que.push(s);// st.insert(s);// while(!que.empty()){// auto t=que.front(); que.pop();// for(int i=0; i<n; i++){// if(t[i]!='A') continue;// for(int j=0; j<n; j++){// if(t[j]!='B') continue;// for(int k=0; k<n; k++){// if(t[k]!='C') continue;// if(!((i<j && j<k) || (j<k && k<i) || (k<i && i<j))) continue;// string u=t;// u[i]='B', u[j]='C', u[k]='A';// if(st.find(u)==st.end()){// st.insert(u);// que.push(u);// }// }// }// }// }// cout<<st.size()<<endl;fac(n);int ca=0, cb=0, cc=0;for(int i=0; i<n; i++){if(s[i]=='A') ca++;else if(s[i]=='B') cb++;else cc++;}mint ans=f[n]*invf[ca]*invf[cb]*invf[cc];ans-=mint(n);bool ok=0;int z=0;for(int i=0; i<n; i++){if(z==0 && s[i]=='A') z++;if(z==1 && s[i]=='B') z++;if(z==2 && s[i]=='C') z++;}if(z==3) ok=1;z=0;for(int i=0; i<n; i++){if(z==0 && s[i]=='B') z++;if(z==1 && s[i]=='C') z++;if(z==2 && s[i]=='A') z++;}if(z==3) ok=1;z=0;for(int i=0; i<n; i++){if(z==0 && s[i]=='C') z++;if(z==1 && s[i]=='A') z++;if(z==2 && s[i]=='B') z++;}if(z==3) ok=1;if(ok) cout<<ans.val()<<endl;else cout<<1<<endl;return 0;}