Description
设函数 g(N)表示 N 的约数个数. 现在给出一个数 M, 求出所有 M 的约数 x 的 g(x)的 K 次方和.
Input
第一行输入 N,K.N 表示 M 由前 N 小的素数组成. 接下来 N 行, 第 i+1 行有一个正整数 Pi, 表示第 Ai 小的素数 有 Pi 次. 等式:
Output
输出一个数, 表示答案. 只需输出最后答案除以 1000000007 的余数.
- Sample Input
- 2 3
- 1
- 3
- Sample Output
- 900
[样例说明]
M=2^1*3^3=54
M 的约数有 1,2,3,6,9,18,27,54. 约数个数分别为 1,2,2,4,3,6,4,8.
Answer=1^3+2^3+2^3+4^3+3^3+6^3+4^3+8^3=900
编号 N K Pi<=
- 50 3 10000
- 50 100 10000
- 50 20101125 10000
- 999 17651851 100000
- 5000 836954247 100000
- 4687 1073741823 100000
- 4321 123456789 100000
- 5216 368756432 100000
- 8080 2^31-1 100000
- 10086 3 2^63-1
- 64970 3 2^63-1
- 71321 3 2^63-1
- 350 5 2^31-1
- 250 6 2^31-1
- 110 7 2^31-1
- 99 8 2^31-1
- 80 9 2^31-1
- 70 10 2^31-1
- 60 11 2^31-1
- 50 12 2^31-1
解题思路:
拿到题感觉一脸不可做, 反正不是反演的样子.
先来考虑一下样例:
$2^1*3^3=54$
考虑如何将答案分类. 将贡献重新累加起来.
首先 $g(d)=\sum\limits_{i=1}^{n}{(1+c_i)}$()其中 $c_i$ 为第 $i$ 项的次数)
现在考虑如何将 $M$ 的所有因数表示出来:
以 54 为例
其中每个因数可以按照 2 的次数分类, 可以是 0~1 次共有 2 种选法.
对于每种选法, 对应的数中 3 的次数有 0~3 共 4 种选法.
而对应 3 的每一种选法其答案都是 $[(2 的次数 + 1)*(3 的次数 + 1)]^k$
那么这种结果可以看做两个多项式乘积的形式, 这两个多项式都是 (1+2+3+...) 的形式, 而由于那个指数上的 k 是可以带入括号的.
那么答案就变成了 $f(54)=(1^3+2^3)*(1^3+2^3+3^3+4^3)=9*100=900$
现在答案就可以解出来了, 答案就变成了:
$f(M)=\prod\limits_{i=1}^{n}\sum\limits_{j=1}^{p_i}{j^k}$
n 是可以枚举的, 对于前 45 分的点, 可以暴力快速幂求解.
剩下的怎么办.
后面的那个高次求和 $\sum\limits_{i=1}^{n}{i^k}$ 是非常公式化的, 怎么可能没有公式.
高次求和公式会形如:
$\sum\limits_{i=1}^{n}{i^k}=\sum\limits_{i=1}^{k+1}{a_i*n^i}$
所以可以这样求解(orz zwz):
$a_1x^1+a_2x^2+...+a_{k+1}x^{k+1}+(x+1)^k=a_1(x+1)+a_2(x+1)^2+...+a_{k+1}(x+1)^{k+1}$
二项式定理展开移项:
$\sum\limits_{i=1}^{k+1}{C_i^0x^0}+\sum\limits_{i=2}^{k+1}{C_i^1x^1}+...+\sum\limits_{i=k+1}^{k+1}{C_i^kx^k}=\sum\limits_{i=0}^{k}{C_k^ix^i}$
这个杨辉三角打出矩阵消元就可以解出系数了.
代码:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- typedef long long lnt;
- const lnt mod=(lnt)(1e9+7);
- lnt n,k;
- lnt maxs;
- lnt C[100][100];
- lnt F[200001];
- lnt p[200001];
- lnt a[1001];
- lnt b[100][100];
- lnt c[100];
- lnt ksm(lnt x,lnt y)
- {
- lnt ans=1;
- while(y)
- {
- if(y&1)ans=ans*x%mod;
- x=x*x%mod;
- y=y/2;
- }
- return ans;
- }
- lnt squ(lnt x)
- {
- return x%mod*x%mod;
- }
- int main()
- {
- scanf("%lld%lld",&n,&k);
- for(int i=1;i<=n;i++)
- scanf("%lld",&p[i]),
- maxs=std::max(p[i],maxs);
- if(maxs<=100000)
- {
- lnt ans=1;
- for(int i=1;i<=maxs+1;i++)F[i]=(F[i-1]+ksm(i,k))%mod;
- for(int i=1;i<=n;i++)ans=(ans*F[p[i]+1])%mod;
- printf("%lld\n",ans);
- return 0;
- }
- if(k==3)
- {
- lnt ans=1;
- lnt Inv=ksm(4,mod-2);
- for(int i=1;i<=n;i++)
- ans=ans*squ(p[i]%mod+1)%mod*squ(p[i]%mod+2)%mod*Inv%mod;
- printf("%lld\n",ans);
- return 0;
- }
- C[0][0]=1;
- for(int i=1;i<=k+1;i++)
- {
- C[i][0]=1;
- for(int j=1;j<=i;j++)
- C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
- }
- for(int i=1;i<=k+1;i++)
- {
- for(int j=i;j<=k+1;j++)
- {
- b[i][j]=C[j][i-1];
- }
- }
- for(int i=1;i<=k+1;i++)a[i]=C[k][i-1];
- for(int i=k+1;i>=1;i--)
- {
- a[i]=(a[i]*ksm(b[i][i],mod-2))%mod;
- for(int j=i-1;j;j--)
- {
- (a[j]-=b[j][i]*a[i]%mod)%=mod;
- }
- }
- lnt ans=1;
- for(int i=1;i<=n;i++)
- {
- lnt tmp=0;
- for(int j=1;j<=k+1;j++)
- tmp=(tmp+(a[j]*ksm(p[i]%mod+1,j))%mod)%mod;
- ans=(ans*tmp)%mod;
- }
- printf("%lld\n",(ans%mod+mod)%mod);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2948676.html