Submission #17673312
Source Code Expand
#include <bits/stdc++.h> typedef long long int64; typedef unsigned int uint; typedef unsigned long long uint64; typedef double db; typedef long double db64; const int N = 2e5, K = 300, MOD = 998244353, I2 = (MOD + 1) / 2; int n, k, a[N + 5], c[K + 5][K + 5]; int64 s[K + 5]; int main() { scanf("%d%d", &n, &k); for (int i = 0; i <= k; i++) { c[i][0] = 1; for (int j = 1; j <= i; j++) { c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD; } } for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); for (int x = 1, j = 0; j <= k; j++, x = (int64)x * a[i] % MOD) { s[j] += x; } } for (int i = 0; i <= k; i++) { s[i] %= MOD; } int pw = 2; for (int i = 1; i <= k; i++) { int64 ans = 0; for (int j = 0; j <= i; j++) { ans += (int64)s[j] * s[i - j] % MOD * c[i][j] % MOD; } ans -= (int64)pw * s[i] % MOD; pw = (pw + pw) % MOD; ans %= MOD; printf("%lld\n", (ans * I2 % MOD + MOD) % MOD); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Powers |
User | siyuan |
Language | C++ (GCC 9.2.1) |
Score | 600 |
Code Size | 980 Byte |
Status | AC |
Exec Time | 276 ms |
Memory | 4892 KiB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:15:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] 15 | scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~ ./Main.cpp:23:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] 23 | scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01, 00_sample_02, 00_sample_03 |
All | 00_sample_01, 00_sample_02, 00_sample_03, 10_small_01, 10_small_02, 10_small_03, 10_small_04, 10_small_05, 10_small_06, 10_small_07, 10_small_08, 10_small_09, 10_small_10, 20_random_01, 20_random_02, 20_random_03, 20_random_04, 20_random_05, 20_random_06, 20_random_07, 20_random_08, 20_random_09, 20_random_10, 30_max_01, 30_max_02, 30_max_03, 30_max_04, 30_max_05, 31_max_01, 31_max_02 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01 | AC | 7 ms | 3676 KiB |
00_sample_02 | AC | 2 ms | 3840 KiB |
00_sample_03 | AC | 2 ms | 3832 KiB |
10_small_01 | AC | 4 ms | 4048 KiB |
10_small_02 | AC | 2 ms | 3924 KiB |
10_small_03 | AC | 3 ms | 4008 KiB |
10_small_04 | AC | 3 ms | 4016 KiB |
10_small_05 | AC | 2 ms | 3796 KiB |
10_small_06 | AC | 3 ms | 4040 KiB |
10_small_07 | AC | 2 ms | 3820 KiB |
10_small_08 | AC | 2 ms | 3656 KiB |
10_small_09 | AC | 2 ms | 3684 KiB |
10_small_10 | AC | 5 ms | 3872 KiB |
20_random_01 | AC | 92 ms | 4208 KiB |
20_random_02 | AC | 104 ms | 4344 KiB |
20_random_03 | AC | 10 ms | 3900 KiB |
20_random_04 | AC | 112 ms | 4388 KiB |
20_random_05 | AC | 53 ms | 4396 KiB |
20_random_06 | AC | 174 ms | 4444 KiB |
20_random_07 | AC | 59 ms | 4220 KiB |
20_random_08 | AC | 162 ms | 4580 KiB |
20_random_09 | AC | 40 ms | 4460 KiB |
20_random_10 | AC | 71 ms | 4552 KiB |
30_max_01 | AC | 271 ms | 4716 KiB |
30_max_02 | AC | 274 ms | 4728 KiB |
30_max_03 | AC | 272 ms | 4892 KiB |
30_max_04 | AC | 276 ms | 4892 KiB |
30_max_05 | AC | 270 ms | 4748 KiB |
31_max_01 | AC | 275 ms | 4708 KiB |
31_max_02 | AC | 272 ms | 4768 KiB |