Submission #17633994

---

Source Code Expand

import java.io.*; import java.util.*;
public class Main {
    static int MOD=998244353;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int K=Integer.parseInt(st.nextToken());
        long[] a=new long[N];
        long[] p=new long[N]; //Only track p[.][i]
        long[] ps=new long[K+1];
        ps[0]=N;
        st=new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            a[i]=Integer.parseInt(st.nextToken());
            
        }
        Arrays.fill(p,1);
        for (int i = 1; i <=K; i++) {
            for (int j = 0; j < N; j++) {
                p[j]*=a[j]; p[j]%=MOD;
                ps[i]+=p[j]; ps[i]%=MOD;
            }
        }
        
        //System.out.println(Arrays.toString(pi));
        
        long ans; long cur=0;
        for (int X = 1; X <=K; X++) {//Evaluating answer for X=i
            ans=0; long binom=1;
            for (int i = 0; i <= (X-1)/2; i++) {
                cur=ps[i]*ps[X-i]; cur%=MOD;
                cur-=ps[X]; cur%=MOD;
                cur*=binom; cur%=MOD;
                ans+=cur; ans%=MOD;
                binom*=(X-i); binom%=MOD;
                binom*=inv(i+1,MOD); binom%=MOD;
            }
            if(X%2==0){
                cur=ps[X/2]*ps[X/2]; cur%=MOD;
                cur-=ps[X]; cur%=MOD;
                
                cur*=binom; cur%=MOD;
                cur*=inv(2,MOD); cur%=MOD;
                
                ans+=cur; ans%=MOD;
            }
            if(ans<0){
                ans+=MOD;
            }
            System.out.println(ans);
        }
    }
    public static long inv(long a, long b){//Computes modular inverse of a mod b
        //Assume b>a and gcd(a,b)=1, 
        if(a==1)return 1;
        long q=b/a;
        long r=b-q*a;
        long y=-inv(r,a);
        return ((b*y+1)/a)+b;
        
    }
}
  

Submission Info

Judge Result