結果

問題 No.1855 Intersected Lines
コンテスト
ユーザー 蜜蜂
提出日時 2022-01-09 22:31:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 2,562 bytes
コンパイル時間 3,845 ms
コンパイル使用メモリ 233,124 KB
実行使用メモリ 9,612 KB
最終ジャッジ日時 2024-07-01 21:19:08
合計ジャッジ時間 7,752 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:100:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  100 |     auto [ch,va]=s[i];
      |          ^
main.cpp:105:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  105 |         auto [c,v]=s[j];
      |              ^
main.cpp:123:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  123 |     auto [ch,va]=s[i];
      |          ^
main.cpp:128:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  128 |         auto [c,v]=s[j];
      |              ^

ソースコード

diff # 

//g++ 6.cpp -std=c++14 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;

#define fi first
#define se second
#define pb push_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

using mint = modint998244353;
constexpr ll mod = 998244353;

// xC4
mint c4(ll x){
  mint res=1;
  rep(i,0,4){
    res*=x-i;
    res/=i+1;
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n;
  int x;
  cin>>n>>x;

  mint ans=0;

  ll r=0,b=0;

  vector<pair<char,ll>> s(x);
  rep(i,0,x){
    char c;
    ll v;
    cin>>c>>v;
    s[i]={c,v};

    if(c=='R')r+=v;
    if(c=='B')b+=v;
  }

  if(r%2==1||b%2==1){
    cout<<0<<endl;
    return 0;
  }

  /*
  (r-1)!! * (b-1)!! 通り

  赤同士の寄与
  2つ選ぶ rC4 通り
  他の決め方 (r-5)!! * (b-1)!! 通り

  期待値への寄与 rC4 * (r-5)!!/(r-1)!! = rC4 * 1/(r-1)(r-3)
  */

  mint rr=0,bb=0,rb=0;

  rr=c4(r),bb=c4(b);
  rr/=(r-1)*(r-3);bb/=(b-1)*(b-3);

  if(r==0||b==0){
    cout<<(rr+bb).val()<<endl;
    return 0;
  }

  /*
  ある赤線と青線を決め打った時 (r-3)!! * (b-3)!! 通り

  この2本がある確率 (r-3)!! / (r-1)!! * (b-3)!! / (b-1)!! = 1/(r-1)(b-1)
  */

  // sum1 pq sum2 p-q
  mint sum1=0,sum2=0;
  rep(i,0,x){
    auto [ch,va]=s[i];

    if(ch=='R'){
      mint p=0;
      rep(j,i,x){
        auto [c,v]=s[j];
        if(c=='R'){
          mint q=b-p;
          sum1+=p*q*v;
          sum2+=(p-q)*v;
        }
        else{
          p+=v;
        }
      }
      break;
    }
  }
  //rb+=sum1;

  mint rv=r;

  rep(i,0,x){
    auto [ch,va]=s[i];

    if(ch=='R'){
      mint p=0;
      rep(j,i,x){
        auto [c,v]=s[j];
        if(c=='R'){
          mint q=b-p;
          rb+=(sum1+sum2*p-p*p*rv)*v;
          sum1-=p*q*v;
          sum2-=(p-q)*v;
          rv-=v;
          //cout<<rb.val()<<" "<<p.val()<<endl;
        }
        else{
          p+=v;
        }
      }
      break;
    }
  }
  //rb/=2;
  rb/=(r-1)*(b-1);

  cout<<(rr+bb+rb).val()<<endl;
}
0