ķ子集和查询 [英] K subset sum queries

问题描述

由于N个整数列表的，我们问Q查询。每个查询表示为一个整​​数K，为此我们需要返回恰好有k个元素的所有可能的子列表的产品的总和。

Given a list A of N integers and we are asked Q queries. Each query is denoted by an integer K, for which we need to return the sum of product of all possible sublists having exactly K elements.

我们需要打印的答案模100003。

We need to print the answers modulo 100003.

例：设N = 3和阵列是{1,2,3}，让有2个查询

Example : Let N = 3 and array be {1,2,3} and let there are 2 queries.

查询1：K = 1，则答案是6如对于K = 1的子列表可能是{1}，{2}，{3}这样的回答是1 + 2 + 3 = 6

Query 1 : K=1 then answer is 6 as For K=1 possible sublists are {1},{2},{3} so answer is 1+2+3=6.

问题2：K = 2，然后回答是11作为对K = 2个可能的子列表是{1,2}，{2,3}，{3,1}，以便回答为（1×2）+（2× 3）+（3×1）= 2 + 6 + 3 = 11

Query 2 : K=2 then answer is 11 as For K=2 possible sublists are {1,2},{2,3},{3,1} so answer is (1×2)+(2×3)+(3×1)=2+6+3=11.

我的尝试：

#define MOD 100003
unsigned long long ans=0;
unsigned long long mulmod(unsigned long long a,unsigned long long b,unsigned long long c){
unsigned long long x = 0,y=a%c;
while(b > 0){
    if(b%2 == 1){
        x = (x+y)%c;
    }
    y = (y*2)%c;
    b /= 2;
}
return x%c;
}

void KSubset(unsigned long long *a,unsigned long long n,unsigned long long *s,unsigned long long sindex,unsigned long long index,unsigned long long k){

if (index>n)
    return;
if (k==0){
    unsigned long long productt = 1;
    for(int i=0;i<sindex;i++){
        productt=mulmod(productt,s[i],MOD);
    }
    ans=(ans%MOD + productt%MOD)%MOD;
    return ;
    }
s[sindex]=a[index];
KSubset(a,n,s,sindex+1,index+1,k-1);
KSubset(a,n,s,sindex,index+1,k);
}

但由于查询可以高达N和N可以高达3 * 10 ^ 4.So是有这个问题的更好的方法吗？

But as queries can be upto N and N can be upto 3*10^4.So is there any better approach for this problem?

推荐答案

由于{3,1}不是一个子表，我会假设你的意思是子集。所有的计算都做MOD 100003;是没有问题的，因为这里的一切是代数。如果展开因素多项式

Since {3, 1} is not a sublist, I'm going to assume that you meant subset. All calculations are to be done mod 100003; there is no problem, since everything here is algebraic. If you expand the factored polynomial

(1 + 1 x) (1 + 2 x) (1 + 3 x)

其中每个因素对应的输入值，那么你得到

where each factor corresponds to an input value, then you get

1 + 6 x + 11 x^2 + 6 x^3,

和答案的查询q是第X ^ Q系数。天真的算法是相当于扩大广义箔法，这需要指数时间。更好的算法，与二次运行时间，是积累的因素一个接一个，与像

and the answer to a query q is the coefficient of x^q. The naive algorithm is to equivalent to expanding a generalized FOIL method, which takes exponential time. A better algorithm, with quadratic running time, is to accumulate the factors one by one, with a loop like

for (int i = degree; i > -1; i--) coefficient[i + 1] += coefficient[i] * x;

其中， X 是下一个值。

这篇关于ķ子集和查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！