結果

問題 No.2133 Take it easy!
ユーザー lddlinanlddlinan
提出日時 2023-03-31 18:45:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 37 ms / 2,000 ms
コード長 3,002 bytes
コンパイル時間 1,086 ms
コンパイル使用メモリ 90,080 KB
実行使用メモリ 4,792 KB
最終ジャッジ日時 2023-10-24 05:10:37
合計ジャッジ時間 2,848 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,372 KB
testcase_01 AC 2 ms
4,372 KB
testcase_02 AC 4 ms
4,372 KB
testcase_03 AC 36 ms
4,788 KB
testcase_04 AC 30 ms
4,524 KB
testcase_05 AC 1 ms
4,372 KB
testcase_06 AC 2 ms
4,372 KB
testcase_07 AC 30 ms
4,404 KB
testcase_08 AC 35 ms
4,788 KB
testcase_09 AC 35 ms
4,788 KB
testcase_10 AC 33 ms
4,688 KB
testcase_11 AC 28 ms
4,372 KB
testcase_12 AC 27 ms
4,372 KB
testcase_13 AC 36 ms
4,784 KB
testcase_14 AC 36 ms
4,788 KB
testcase_15 AC 33 ms
4,668 KB
testcase_16 AC 21 ms
4,372 KB
testcase_17 AC 26 ms
4,372 KB
testcase_18 AC 32 ms
4,632 KB
testcase_19 AC 26 ms
4,372 KB
testcase_20 AC 26 ms
4,372 KB
testcase_21 AC 33 ms
4,680 KB
testcase_22 AC 24 ms
4,372 KB
testcase_23 AC 37 ms
4,792 KB
testcase_24 AC 37 ms
4,792 KB
testcase_25 AC 36 ms
4,660 KB
testcase_26 AC 2 ms
4,372 KB
testcase_27 AC 2 ms
4,372 KB
testcase_28 AC 35 ms
4,788 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <map>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <algorithm>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <string>
using namespace std;

bool rcmp(int a, int b) { return a>b; }
typedef long long LL;
class mypcmp {
public:
    bool operator()(const int& a, const int& b) {
        return a<b;
    }
};


typedef struct { int s, e; } SNode;
SNode sg[1024*4];
bool mycmp(const SNode &a, const SNode &b) {
    if (a.s!=b.s) return a.s<b.s;
    return a.e<b.e;
}
int ft[200004];
int ift[200004];
#define MOD 998244353
int expit(LL b, int e) {
    LL r=1;
    while(e) {
        if (e&1){ r*=b; r%=MOD; }
        b*=b; b%=MOD;
        e>>=1;
    }
    return r;
}
int main() {
    int n, i,q , j, k, relax;
    int s1, e1, s2, e2, s, e, c;
    LL r, t, t2;
    scanf("%d %d", &n, &q);
    k=0;
    sg[k].s=1;  sg[k].e=n; if (n&1) sg[k].e++;
    k++;
    for (i=0; i<q; i++) { scanf("%d %d", &s, &e); sg[k].s=s; sg[k].e=e; k++; }
    ft[0]=ift[0]=1; 
    for (i=1; i<=n+1; i++) {
        t=ft[i-1]; t*=i; t%=MOD;
        ft[i]=t; ift[i]=expit(t, MOD-2);
    }
    while(1) {
        relax=0;
        for (i=0; i<k; i++) if ((sg[i].e-sg[i].s+1)&1) { printf("0\n"); return 0; }
        for (i=1; i<k; i++) {
            for (j=i-1; j>=0; j--) {
                s1=sg[j].s; e1=sg[j].e;
                s2=sg[i].s; e2=sg[i].e;
                if (s1>e2||e1<s2) continue;
                if (s1>s2&&e1<e2) continue;
                if (s2>s1&&e2<e1) continue;
                if (s1==s2&&e1==e2) { k--; sg[i]=sg[k]; i--; break; }
                relax=1;
                if (s1>s2) { t=s1; s1=s2; s2=t; t=e1; e1=e2; e2=t; }
                if (s1==s2) {
                    if (e1<e2) {
                        sg[j].e=e1;
                        sg[i].s=e1+1; sg[i].e=e2;
                    } else {
                        sg[j].e=e2;
                        sg[i].s=e2+1; sg[i].e=e1;
                    }
                } else if (e1==e2) {
                    sg[j].s=s1; sg[j].e=s2-1;
                    sg[i].s=s2; sg[i].e=e2;
                } else {
                    sg[j].s=s1; sg[j].e=s2-1;
                    sg[i].s=s2; sg[i].e=e1;
                    sg[k].s=e1+1; sg[k].e=e2; k++;
                }
            }
        }
        if (relax==0) break;
    }
    sort(sg, sg+k, mycmp);
    r=1;
    for (i=0; i<k; i++) {
        s1=sg[i].s; e1=sg[i].e;
        c=e1-s1+1;
        e2=s1;
        for (j=i+1; j<k; j++) {
            if (sg[j].s>e1) break;
            if (sg[j].e>e2)  { c-=(sg[j].e-sg[j].s+1); e2=sg[j].e; }
        }
        // C(c, c/2)-C(c, c/2-1);
        t=ft[c]; t*=ift[c/2]; t%=MOD; t*=ift[c/2]; t%=MOD;
        t2=ft[c]; t2*=ift[c/2-1]; t2%=MOD; t2*=ift[c/2+1]; t2%=MOD;
        t-=t2; if (t<0) t+=MOD;
        r*=t; r%=MOD;
    }
    r*=ft[n/2]; r%=MOD;
    r*=ft[(n+1)/2]; r%=MOD;
    printf("%lld\n", r);
    return 0;
}
0