結果

問題 No.1492 01文字列と転倒
コンテスト
ユーザー southsidesamurai65-prog
提出日時 2026-08-24 20:24:00
言語 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  
実行時間 763 ms / 4,000 ms
+ 41µs
コード長 1,173 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,442 ms
コンパイル使用メモリ 155,388 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2026-08-24 20:24:12
合計ジャッジ時間 11,244 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<cstring>
typedef long long ll;
using namespace std;
ll dp[2][105][5005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //一定是0好串1 或 好串+好串，区间DP
    //但是需要O(n^6)枚举两侧长度和逆序对数啊？
    //不要用区间dp计数！dp[n][h][k]，n长，0比1多h，逆序对k
    int n;ll m;cin>>n>>m;
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=1;i<=2*n;i++){
        for(int k=0;k<=n*(n-1)/2;k++){
            dp[1][0][k]=dp[0][1][k]; //一样多肯定是补了1
            for(int h=1;h<=min(n,i);h++){
                int one=(i-h)/2;
                dp[1][h][k]=0;
                if(h+1<=n) dp[1][h][k]=(dp[1][h][k]+dp[0][h+1][k])%m; //补1
                if(k>=one) dp[1][h][k]=((dp[1][h][k]+dp[0][h-1][k-one])%m+m)%m; //补0
            }
        }
        for(int k=0;k<=n*(n-1)/2;k++){
            for(int h=0;h<=min(n,i);h++){
                dp[0][h][k]=dp[1][h][k];
            }
        }
    }
    for(int k=0;k<=n*(n-1)/2;k++){
        cout<<dp[1][0][k]<<endl;
    }
    for(int k=n*(n-1)/2+1;k<=n*n;k++){
        cout<<0<<endl;
    }


    return 0;
}
0