結果

問題 No.2133 Take it easy!
コンテスト
ユーザー lddlinan
提出日時 2023-03-31 18:45:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 3,002 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 90,508 KB
最終ジャッジ日時 2025-02-11 19:40:26
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:49:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:53:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |     for (i=0; i<q; i++) { scanf("%d %d", &s, &e); sg[k].s=s; sg[k].e=e; k++; }
      |                           ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

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