結果
問題 | No.1855 Intersected Lines |
ユーザー |
![]() |
提出日時 | 2022-02-25 23:19:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 1,209 bytes |
コンパイル時間 | 4,848 ms |
コンパイル使用メモリ | 265,080 KB |
最終ジャッジ日時 | 2025-01-28 02:36:13 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for(int i=0;i<(n);i++)#define Inf 1000000001int main(){int n,x;cin>>n>>x;vector<char> c;vector<long long> v;rep(i,x){char C;long long V;cin>>C>>V;if(c.size()==0 || c.back()!=C){c.push_back(C);v.push_back(V);}else{v.back() += V;}}mint ans = 0;rep(i,2){char cc;if(i==0)cc = 'B';else cc = 'R';long long sum = 0LL;rep(j,c.size()){if(c[j]==cc)sum += v[j];}if(sum <= 3)continue;mint t = sum;t *= sum-1;t *= sum-2;t *= sum-3;t /= 24;t /= sum-1;t /= sum-3;ans += t;}map<string,mint> mp;mp[""] = 1;rep(i,c.size()){map<string,mint> nmp = mp;for(auto a:mp){string ss = a.first;if(ss.size()>0 && ss.back()==c[i])continue;ss += c[i];if(ss.size()>=5)continue;nmp[ss] += a.second * v[i];}swap(mp,nmp);}{mint tt = mp["RBRB"] + mp["BRBR"];int R = 0,B = 0;rep(i,c.size()){if(c[i]=='R')R += v[i];else B += v[i];}tt /= R-1;tt /= B-1;ans += tt;}cout<<ans.val()<<endl;return 0;}