TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4686
  • Problem
  • P4686乘积之和
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 4s,265536
    Description

    给出由N个正整数组成的数组A,有Q次查询,每个查询包含一个整数K,从数组A中任选K个(K <= N)把他们乘在一起得到一个乘积。求所有不同的方案得到的乘积之和,由于结果巨大,输出Mod 100003的结果即可。例如:1 2 3,从中任选1个共3种方法,{1} {2} {3},和为6。从中任选2个共3种方法,{1 2} {1 3} {2 3},和为2 + 3 + 6 = 11。

    Input Format
    第一行:包括2个数N,Q,中间用空格分隔。(1 <= N, Q <= 50000)
    第2 至 N + 1行:每行1个数A[i],对应数组A的元素。(1 <= A[i] <= 10^9)
    第N + 2 至 N + Q + 1行:每行1个数K。(1 <= K <= N)
    Output Format
    输出共Q行,每行1个数,对应每个查询的结果。
    Sample Input 1

    3 2
    1
    2
    3
    1
    2

    Sample Output 1

    6
    11

    Sample Input 2

    10 5
    4
    30
    1
    24
    72
    70
    16
    7
    81
    9
    9
    7
    5
    3
    4

    Sample Output 2

    31387
    47424
    66689
    82760
    65264


    Source  51nod 1348