結果
問題 | No.1481 Rotation ABC |
ユーザー |
![]() |
提出日時 | 2021-04-16 21:53:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,120 bytes |
コンパイル時間 | 3,613 ms |
コンパイル使用メモリ | 175,992 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-03 01:34:15 |
合計ジャッジ時間 | 4,367 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream>#include <string>#include <cmath>#include<algorithm>#include<stack>#include<queue>#include<map>#include<set>#include<iomanip>#include<bitset>#define _USE_MATH_DEFINES#include <math.h>#include <functional>#include<complex>#include<cassert>#include<random>using namespace std;#include<atcoder/all>using namespace atcoder;#define rep(i,x) for(ll i=0;i<x;i++)#define repn(i,x) for(ll i=1;i<=x;i++)typedef long long ll;typedef pair<ll, ll> P;const ll INF = 1e17;const ll MAX = 4000001;const long double eps = 1E-14;ll max(ll a, ll b) {if (a > b) { return a; }return b;}ll min(ll a, ll b) {if (a > b) { return b; }return a;}ll gcd(ll a, ll b) {if (b == 0) { return a; }if (a < b) { return gcd(b, a); }return gcd(b, a % b);}ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}struct edge {ll id;ll fr;ll to;ll d;};using mint = modint;typedef vector<ll> vll;typedef vector <vector<ll>> vvll;typedef vector<vector<vector<ll>>> vvvll;typedef vector<mint> vmint;typedef vector<vector<mint>> vvmint;typedef vector<vector<vector<mint>>> vvvmint;vmint f, finv, inv;void cominit(ll N) {ll MOD = modint::mod();//デフォルトが998244353に注意f.assign(N + 1, 1);finv.assign(N + 1, 1);inv.assign(N + 1, 1);inv[1] = 1;repn(i, N) {f[i] = f[i - 1] * i;if (i > 1)inv[i] = -inv[MOD % i] * (MOD / i);finv[i] = finv[i - 1] * inv[i];}}mint com(ll a, ll b) {if (a < 0 || b < 0 || a < b) { return 0; }return f[a] * finv[b] * finv[a - b];}/////////////////////////////////////bool ch(string S, string T) {ll t = 0;rep(i, S.size()) {if (S[i] == T[t]) { t++; }if (t == T.size()) { return true; }}return false;}int main() {ll N;cin >> N;string S;cin >> S;set<char> st;rep(i, N)st.insert(S[i]);if (st.size() < 3) { cout << 1 << endl; return 0; }if (!ch(S, "ABC") && !ch(S, "BCA") && !ch(S, "CAB")) { cout << 1 << endl; return 0; }cominit(N + 1);vll c(3);rep(i, N)c[S[i] - 'A']++;mint ans = com(N, c[0]) * com(c[1] + c[2], c[1]);ans -= N;cout << ans.val() << endl;}