結果

問題 No.2994 べき内積
ユーザー 👑 ygussanyygussany
提出日時 2024-12-19 01:29:10
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 2,950 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 38,884 KB
実行使用メモリ 19,208 KB
最終ジャッジ日時 2024-12-19 01:29:20
合計ジャッジ時間 9,860 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 4 ms
16,504 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 65 ms
8,064 KB
testcase_07 AC 278 ms
16,936 KB
testcase_08 AC 6 ms
18,340 KB
testcase_09 AC 221 ms
16,428 KB
testcase_10 AC 226 ms
16,784 KB
testcase_11 AC 61 ms
8,356 KB
testcase_12 AC 57 ms
6,820 KB
testcase_13 AC 228 ms
16,704 KB
testcase_14 AC 297 ms
18,692 KB
testcase_15 AC 89 ms
8,220 KB
testcase_16 AC 198 ms
16,188 KB
testcase_17 AC 76 ms
6,816 KB
testcase_18 AC 233 ms
18,692 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 1,066 ms
19,020 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast,unroll-loops")
#include <stdio.h>

const int p = 1009;

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

long long pow_mod(int n, long long k)
{
	long long N, ans = 1;
	for (N = n; k > 0; k >>= 1, N = N * N % p) if (k & 1) ans = ans * N % p;
	return ans;
}

#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, M, N, K[400001], A[2001];
	scanf("%d %d", &M, &N);
	for (i = 0; i <= M; i++) scanf("%d", &(K[i]));
	for (i = 0; i <= N; i++) scanf("%d", &(A[i]));
	// for (i = 0, K[0] = p - 1; i <= N; i++) A[i] = genrand() % p;
	// A[0] = 2;
	
	int j, k;
	long long B[1009][2001];
	if (A[0] == 0) {
		for (i = 1, B[0][0] = 1; i <= N; i++) B[0][i] = 0;
		for (i = 0; i <= N; i++) B[1][i] = A[i];
		for (k = 2; k < p; k++) {
			for (i = 0; i <= N; i++) for (j = 0, B[k][i] = 0; j <= i; j++) B[k][i] += B[k-1][j] * A[i-j];
			for (i = 0; i <= N; i++) B[k][i] %= p;
		}
		for (i = M, k = 0; i >= 0 && k < p; i--) k = k * p + K[i];
		if (k < p) for (i = 0; i <= N; i++) printf("%lld ", B[k][i]);
		else for (i = 0; i <= N; i++) printf("0 ");
	} else {
		for (i = M, k = 0; i >= 1; i--) k = (k * p + K[i]) % (p - 1);
		k = pow_mod(A[0], k);
		for (i = 0; i <= N; i++) B[0][i] = 0;
		B[0][0] = k;
		B[0][p] = A[1] * k % p * div_mod(1, k, p) * K[1] % p;
		for (k = 1; k <= K[0]; k++) {
			for (i = 0; i <= N; i++) for (j = 0, B[k][i] = 0; j <= i; j++) B[k][i] += B[k-1][j] * A[i-j];
			for (i = 0; i <= N; i++) B[k][i] %= p;
		}
		for (i = 0; i <= N; i++) printf("%lld ", B[K[0]][i]);
	}
	printf("\n");
	fflush(stdout);
	return 0;
}
0