結果

問題 No.2794 I Love EDPC-T
コンテスト
ユーザー Qq Ae
提出日時 2026-07-28 00:46:57
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 365 ms / 3,000 ms
+ 989µs
コード長 2,400 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,326 ms
コンパイル使用メモリ 364,652 KB
実行使用メモリ 17,668 KB
最終ジャッジ日時 2026-07-28 00:47:08
合計ジャッジ時間 10,679 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll pw(ll b, ll e){ ll r=1; b%=MOD; while(e){ if(e&1) r=r*b%MOD; b=b*b%MOD; e>>=1;} return r; }
void ntt(vector<ll>&a, bool inv){
    int n=a.size();
    for(int i=1,j=0;i<n;i++){ int bit=n>>1; for(;j&bit;bit>>=1) j^=bit; j^=bit; if(i<j) swap(a[i],a[j]); }
    for(int len=2;len<=n;len<<=1){
        ll w=pw(3,(MOD-1)/len); if(inv) w=pw(w,MOD-2);
        for(int i=0;i<n;i+=len){ ll wn=1;
            for(int j=0;j<len/2;j++){ ll u=a[i+j], v=a[i+j+len/2]*wn%MOD;
                a[i+j]=(u+v)%MOD; a[i+j+len/2]=(u-v+MOD)%MOD; wn=wn*w%MOD; } } }
    if(inv){ ll ni=pw(n,MOD-2); for(auto&x:a) x=x*ni%MOD; }
}
vector<ll> mul(const vector<ll>&a, const vector<ll>&b){
    if(a.empty()||b.empty()) return {};
    int rs=a.size()+b.size()-1;
    if((ll)a.size()*b.size()<=1024){ vector<ll> c(rs,0);
        for(size_t i=0;i<a.size();i++) if(a[i]) for(size_t j=0;j<b.size();j++) c[i+j]=(c[i+j]+a[i]*b[j])%MOD;
        return c; }
    int n=1; while(n<rs) n<<=1;
    vector<ll> fa(a.begin(),a.end()), fb(b.begin(),b.end()); fa.resize(n); fb.resize(n);
    ntt(fa,false); ntt(fb,false);
    for(int i=0;i<n;i++) fa[i]=fa[i]*fb[i]%MOD;
    ntt(fa,true); fa.resize(rs); return fa;
}
vector<ll> prodAll(vector<vector<ll>>&ps,int l,int r){
    if(r-l==1) return ps[l]; int m=(l+r)/2;
    return mul(prodAll(ps,l,m),prodAll(ps,m,r));
}
int main(){
    int N; string s; cin>>N>>s;
    vector<int> c; int cur=1;
    for(char ch: s){ if(ch=='>') cur++; else { c.push_back(cur); cur=1; } }
    c.push_back(cur);
    int k=c.size();
    if(k==1){ cout<<0<<"\n"; return 0; }              // 単調減少 → LIS=1
    vector<vector<ll>> ps;
    for(int r=1;r<k;r++){
        int hi = (r<k-1) ? c[r]-1 : c[r];
        if(hi<1){ cout<<0<<"\n"; return 0; }          // "<<" があると LIS≥3
        vector<ll> f(hi+1,1); f[0]=0; ps.push_back(move(f));
    }
    vector<ll> g = prodAll(ps,0,ps.size());
    vector<ll> fact(N+1), inv(N+1); fact[0]=1;
    for(int i=1;i<=N;i++) fact[i]=fact[i-1]*i%MOD;
    inv[N]=pw(fact[N],MOD-2); for(int i=N;i>0;i--) inv[i-1]=inv[i]*i%MOD;
    auto C=[&](int n,int r)->ll{ if(r<0||r>n) return 0; return fact[n]*inv[r]%MOD*inv[n-r]%MOD; };
    ll ans=0;
    for(size_t m=0;m<g.size();m++) if(g[m])
        ans=(ans+g[m]%MOD*((C(N,(int)m)-C(N,(int)m-1)+MOD)%MOD))%MOD;
    cout<<ans%MOD<<"\n";
}
0