結果

問題 No.2899 Taffy Permutation
コンテスト
ユーザー sea_water
提出日時 2026-10-07 14:01:51
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,579 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,811 ms
コンパイル使用メモリ 356,472 KB
実行使用メモリ 19,272 KB
最終ジャッジ日時 2026-10-07 14:02:10
合計ジャッジ時間 6,532 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
long long q[2005],qq[2005],qp[2005],vp[2005],ans,sum;
int c[2005][2005];
int dp[2005],n,m,ss,tt,vx;
string s;
struct xxs{
    int sum,op;
}a[2005];
int main(){
  //  freopen("aspect.in","r",stdin);
  //  freopen("aspect.out","w",stdout);
    cin>>n;
    cin>>s;
    s=' '+s;
    for(int i=1;i<=n;i++){
        if(s[i]!=s[i-1]){
            m++;
            a[m].sum=1;
            a[m].op=s[i]-'0';
        }
        else a[m].sum++;
    }
    q[1]=1;
    for(int i=2;i<=n;i++){
        q[i]=q[i-1]*1ll*i%mod;
    }
    for(int i=0;i<=n;i++) c[i][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            c[i][j]%=mod;
        }
    }
    if(a[m].op==0){
        dp[a[m].sum+1]=q[a[m].sum];
        ss=a[m].sum;
        vx=a[m].sum;
        m--;
    }
   // dp[a[m-1].sum+1]=1;
    for(int i=m;i>=1;i-=2){
        if(i==1){
            ans=c[n][a[i].sum]*1ll*q[a[i].sum]%mod;
            for(int i=1;i<=n;i++){
                if(dp[i]){
                    sum+=dp[i];
                    sum%=mod;
                }
            }
            if(sum!=0)ans=(ans*sum)%mod;
            cout<<ans;
            return 0;
        }
        vx+=a[i].sum;
        vx+=a[i-1].sum;
        for(int j=a[i-1].sum+1;j<=ss+a[i-1].sum+1;j++){
            qp[j]=c[j-1][a[i-1].sum-1]*1ll*q[a[i-1].sum]%mod*c[vx-j+1][a[i].sum]%mod*q[a[i].sum]%mod;
      //     cout<<qp[j]<<' ';
        }
     //      cout<<qp[ss+a[i-1].sum+1]<<' '<<c[ss+a[i-1].sum][a[i-1].sum]<<' ';
     //   cout<<'\n';
        for(int j=2;j<=ss+1;j++){
            if(dp[j]){
                vp[j+a[i-1].sum]+=dp[j];
                cout<<dp[j]<<' '<<j+a[i-1].sum<<' ';
                vp[j+a[i-1].sum]%=mod;
            }
        }
        cout<<'\n';
        if(i==m){
            vp[a[m-1].sum+1]=1;
        }
        for(int j=1;j<=a[i-1].sum;j++) dp[j]=0;
        //vp[vx+1]=0;
       // cout<<vp[3];
        for(int j=ss+a[i-1].sum+1;j>=a[i-1].sum+1;j--){
            cout<<vp[j]<<' ';
            vp[j]+=vp[j+1];
            vp[j]%=mod;
        }
        cout<<'\n';
        for(int j=a[i-1].sum+1;j<=ss+a[i-1].sum+1;j++){
        //    cout<<vp[j]<<' ';
            dp[j]=vp[j]*1ll*qp[j]%mod;
        }
        for(int j=1;j<=ss+a[i-1].sum+1;j++){
            vp[j]=qp[j]=0;
        }
        ss+=a[i-1].sum;
       // cout<<dp[2]<<'\n';
    }
    for(int i=1;i<=n+1;i++){
        if(dp[i]){
            ans+=dp[i];
            ans%=mod;
        }
    }
    cout<<ans;
    return 0;
}
0