結果

問題 No.2990 Interval XOR
ユーザー ygussanyygussany
提出日時 2024-12-15 23:27:35
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 3,603 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 34,432 KB
実行使用メモリ 29,056 KB
最終ジャッジ日時 2024-12-15 23:28:25
合計ジャッジ時間 48,130 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,496 KB
testcase_01 AC 2 ms
8,448 KB
testcase_02 AC 2 ms
10,496 KB
testcase_03 AC 2 ms
7,424 KB
testcase_04 AC 2 ms
10,496 KB
testcase_05 AC 2 ms
7,296 KB
testcase_06 AC 2 ms
10,496 KB
testcase_07 AC 2 ms
12,288 KB
testcase_08 AC 1 ms
10,496 KB
testcase_09 AC 2 ms
8,320 KB
testcase_10 AC 2 ms
10,496 KB
testcase_11 AC 2 ms
12,288 KB
testcase_12 AC 3 ms
10,496 KB
testcase_13 AC 8 ms
12,288 KB
testcase_14 AC 2 ms
10,496 KB
testcase_15 AC 15 ms
29,056 KB
testcase_16 AC 3 ms
10,496 KB
testcase_17 AC 8 ms
28,928 KB
testcase_18 AC 21 ms
10,496 KB
testcase_19 AC 3 ms
17,060 KB
testcase_20 AC 15 ms
17,068 KB
testcase_21 AC 4 ms
10,496 KB
testcase_22 AC 13 ms
10,496 KB
testcase_23 AC 3 ms
29,056 KB
testcase_24 AC 14 ms
10,496 KB
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int Mod = 998244353;
const int bit[21] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576};
const int bit_inv[21] = {1, 499122177, 748683265, 873463809, 935854081, 967049217, 982646785, 990445569, 994344961, 996294657, 997269505, 997756929, 998000641, 998122497, 998183425, 998213889, 998229121, 998236737, 998240545, 998242449};

// Fast Hardmard Transformation (XOR convolution)
void FHT(int d, int a[], int b[])
{
	if (d == 0) {
		b[0] = a[0];
		return;
	}
	
	int i, j;
	static int c[1048576];
	FHT(d - 1, a, b);
	FHT(d - 1, &(a[bit[d-1]]), &(b[bit[d-1]]));
	for (i = 0; i < bit[d]; i++) c[i] = b[i];
	for (i = 0, j = bit[d-1]; i < bit[d-1]; i++, j++) {
		b[i] = c[i] + c[j];
		if (b[i] >= Mod) b[i] -= Mod;
		b[j] = c[i] - c[j];
		if (b[j] < 0) b[j] += Mod;
	}
}

void naive(int N, int M, int L[], int R[], int ans[])
{
	int i, j;
	static int tmp[1048576], a[1048576], b[1048576];
	for (i = 0; i < L[1]; i++) ans[i] = 0;
	for (; i <= R[1]; i++) ans[i] = 1;
	for (; i < bit[N]; i++) ans[i] = 0;
	for (j = 2; j <= M; j++) {
		for (i = 0; i < L[j]; i++) tmp[i] = 0;
		for (; i <= R[j]; i++) tmp[i] = 1;
		for (; i < bit[N]; i++) tmp[i] = 0;
		FHT(N, ans, a);
		FHT(N, tmp, b);
		for (i = 0; i < bit[N]; i++) tmp[i] = (long long)a[i] * b[i] % Mod;
		FHT(N, tmp, ans);
		for (i = 0; i < bit[N]; i++) ans[i] = (long long)ans[i] * bit_inv[N] % Mod;
	}
}

void naive_faster(int N, int M, int L[], int R[], int ans[])
{
	int i, j;
	static int tmp[1048576], a[1048576], b[1048576];
	for (i = 0; i < L[1]; i++) ans[i] = 0;
	for (; i <= R[1]; i++) ans[i] = 1;
	for (; i < bit[N]; i++) ans[i] = 0;
	FHT(N, ans, a);
	for (j = 2; j <= M; j++) {
		for (i = 0; i < L[j]; i++) tmp[i] = 0;
		for (; i <= R[j]; i++) tmp[i] = 1;
		for (; i < bit[N]; i++) tmp[i] = 0;
		FHT(N, tmp, b);
		for (i = 0; i < bit[N]; i++) a[i] = (long long)a[i] * b[i] % Mod;
	}
	FHT(N, a, ans);
	for (i = 0; i < bit[N]; i++) ans[i] = (long long)ans[i] * bit_inv[N] % Mod;
}


#define MT_N 624
#define MT_M 397
#define MT_MATRIX_A 0x9908b0dfUL
#define MT_UPPER_MASK 0x80000000UL
#define MT_LOWER_MASK 0x7fffffffUL

static unsigned int mt[MT_N];
static int mti = MT_N + 1;

void init_genrand(unsigned int s)
{
    mt[0] = s & 0xffffffffUL;
    for (mti = 1; mti < MT_N; mti++) {
        mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); 
        mt[mti] &= 0xffffffffUL;
    }
}

unsigned int genrand()
{
    unsigned int y;
    static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A};

    if (mti >= MT_N) {
        int kk;
        if (mti == MT_N + 1) init_genrand(5489UL);
		
        for (kk = 0; kk < MT_N - MT_M; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        for (; kk < MT_N - 1; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK);
        mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL];

        mti = 0;
    }
  
    y = mt[mti++];

    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}

int main()
{
	int i, N, M, L[200001], R[200001];
	scanf("%d %d", &N ,&M);
	for (i = 1; i <= M; i++) scanf("%d %d", &(L[i]), &(R[i]));
	
	static int ans[1048576];
	naive_faster(N, M, L, R, ans);
	for (i = 0; i < bit[N]; i++) printf("%d\n", ans[i]);
	fflush(stdout);
	return 0;
}
0