Clarke and math

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5628

Description

Clarke is a patient with multiple personality disorder. One day, he turned into a mathematician, did a research on interesting things.

Suddenly he found a interesting formula. Given f(i),1≤i≤n, calculate

g(i)=∑i1∣i∑i2∣i1∑i3∣i2⋯∑ik∣ik−1f(ik) mod 1000000007(1≤i≤n)

Input

The first line contains an integer T(1≤T≤5), the number of test cases.

For each test case, the first line contains two integers n,k(1≤n,k≤100000).

The second line contains n integers, the ith integer denotes f(i),0≤f(i)<109+7.

Output

For each test case, print a line contained n integers, the ith integer represents g(i).

Sample Input

2

6 2

2 3 3 3 3 3

23 3

2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

Sample Output

2 7 7 15 7 23

2 9 9 24 9 39 9 50 24 39 9 102 9 39 39 90 9 102 9 102 39 39 9

Hint

题意

题解：

dp

dp[i][j]表示第i位置，选择了j个不同的因子之后，能够获得的权值是多少

ans[i]=sigma C(k,j)*dp[i][j]

为什么呢？

我们考虑传递了k次的sigma，实际上就是在枚举因子，在这个数据范围内，最多枚举20个不同的因子，而且因子显然是不断递减的（当然，这句话没什么用

然后脑补脑补，这个就是对的了……

官方题解确实看不懂……

弱智选手并不会xx卷积……

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+7;

const int mod = 1e9+7;

long long fac[maxn];

long long qpow(long long a,long long b)

{

    long long ans=1;a%=mod;

    for(long long i=b;i;i>>=1,a=a*a%mod)

        if(i&1)ans=ans*a%mod;

    return ans;

}

long long C(long long n,long long m)

{

    if(m>n||m<0)return 0;

    long long s1=fac[n],s2=fac[n-m]*fac[m]%mod;

    return s1*qpow(s2,mod-2)%mod;

}

int a[maxn];

int dp[maxn][22];

int K=20;

int main()

{

    fac[0]=1;

    for(int i=1;i<maxn;i++)

        fac[i]=fac[i-1]*i%mod;

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m;

        memset(dp,0,sizeof(dp));

        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]);

        for(int i=1;i<=n;i++)

            dp[i][0]=a[i];

        for(int i=1;i<=n;i++)

            for(int j=i+i;j<=n;j+=i)

                for(int k=0;k<K;k++)

                    dp[j][k+1]=(dp[j][k+1]+dp[i][k])%mod;

        for(int i=1;i<=n;i++)

        {

            int ans = 0;

            for(int j=0;j<=K;j++)

                ans=(ans+1ll*C(m,j)*dp[i][j])%mod;

            if(i==n)printf("%d",ans);else printf("%d ",ans);

        }

        printf("\n");

    }

}

巴特西

HDU 5628 Clarke and math dp+数学