提出 #17680444


ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define M 998244353
#define N 200000
typedef long long int LL;
LL fact[301],invfact[301],sum[301],sum2[301];
int ap[N][301],p2[301];
LL mult(LL a, LL b){
	return a*b%M;
}
LL add(LL a, LL b){
	return (a+b+M)%M;
}
LL c(LL n, LL k){
	return mult(fact[n],mult(invfact[k],invfact[n-k]));
}
LL p(LL b, LL x){
	if(x==0) return 1LL;
	LL sub=p(b,x/2);
	sub=mult(sub,sub);
	if(x&1) sub=mult(sub,b);
	return sub;
}
int main(){
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++) scanf("%d",a+i);
	for(int i=0;i<n;i++) ap[i][0]=1;
	for(int i=0;i<n;i++) for(int j=1;j<=k;j++) ap[i][j]=mult(ap[i][j-1],a[i]);
	fact[0]=invfact[0]=1;
	for(int i=1;i<301;i++) fact[i]=mult(fact[i-1],i),invfact[i]=p(fact[i],M-2);
	p2[0]=1;
	for(int i=1;i<301;i++) p2[i]=mult(2,p2[i-1]);
	for(int i=0;i<n;i++) for(int j=0;j<=k;j++) sum[j]=add(sum[j],ap[i][j]);
	LL tinv=p(2,M-2);
	for(int X=1;X<=k;X++){
		LL ans=0;
		for(int x=0;x<=X;x++){
			ans=add(ans,mult(c(X,x),mult(sum[X-x],sum[x])));
		}
		ans=add(ans,-mult(p2[X],sum[X]));
		ans=mult(ans,tinv);
		cout<<ans<<"\n";
	}
}

提出情報

提出日時
問題 D - Powers
ユーザ alhasan
言語 C++ (GCC 9.2.1)
得点 600
コード長 1139 Byte
結果 AC
実行時間 543 ms
メモリ 239548 KiB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:28:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   28 |  for(int i=0;i<n;i++) scanf("%d",a+i);
      |                       ~~~~~^~~~~~~~~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 3
AC × 30
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
00_sample_01 AC 8 ms 3612 KiB
00_sample_02 AC 2 ms 3492 KiB
00_sample_03 AC 2 ms 3596 KiB
10_small_01 AC 5 ms 3688 KiB
10_small_02 AC 3 ms 3660 KiB
10_small_03 AC 3 ms 3832 KiB
10_small_04 AC 3 ms 3800 KiB
10_small_05 AC 2 ms 3780 KiB
10_small_06 AC 2 ms 3712 KiB
10_small_07 AC 2 ms 3472 KiB
10_small_08 AC 3 ms 3804 KiB
10_small_09 AC 3 ms 3792 KiB
10_small_10 AC 4 ms 3892 KiB
20_random_01 AC 185 ms 90220 KiB
20_random_02 AC 214 ms 103460 KiB
20_random_03 AC 41 ms 41044 KiB
20_random_04 AC 232 ms 122120 KiB
20_random_05 AC 194 ms 189548 KiB
20_random_06 AC 350 ms 163868 KiB
20_random_07 AC 156 ms 118588 KiB
20_random_08 AC 341 ms 184928 KiB
20_random_09 AC 187 ms 225872 KiB
20_random_10 AC 254 ms 236928 KiB
30_max_01 AC 541 ms 239396 KiB
30_max_02 AC 543 ms 239400 KiB
30_max_03 AC 540 ms 239548 KiB
30_max_04 AC 538 ms 239388 KiB
30_max_05 AC 528 ms 239416 KiB
31_max_01 AC 543 ms 239420 KiB
31_max_02 AC 541 ms 239536 KiB