首页 > 其他 > 详细

模拟赛 复活石 (狄利克雷卷积+快速幂 // 组合数学)

时间:2019-12-17 22:17:46      阅读:102      评论:0      收藏:0      [点我收藏+]

技术分享图片

题解

法一:
卷积忘完了,考场上根本没想到。。
可以发现要求的就是\(f*I^k\),这里的\(*\)是狄利克雷卷积。
然后狄利克雷卷积支持结合律。
所以快速幂就完事了。
时间复杂度\(O(n\log n\log k)\)

法二:
考虑\(f(x)\)对于\(g(i)\)的贡献,一定是\(f(x)*y\)的形式,\(y\)为一个与\(i/x\)有关的系数。

\(a_j=\frac{i_j-1}{i_j}(j\in[1,k]),i_0=i,i_k=x\)。那么\(y\)就是合法的\(a\)序列数量,\(a\)实质就是\(x\)乘上\(k\)个数最后变成了\(i\)

容易发现就相当于把\(i/x\)的质因子分在\(k\)个盒子里。每个质因子独立可以分开算。假设当前质因子有\(m\)个,方案就是\(C(m+k-1,k-1)\)

可以通过dfs/线性筛求出\(y\)。最后把\(f,y\)卷积一下就算出了答案。

CODE

法一代码:

#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
    char ch; while(!isdigit(ch=getchar()));
    for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
}
const int mod = 1e9 + 7;
const int MAXN = 100005;
int n, k, f[MAXN], g[MAXN], tmp[MAXN];
void mul(int *a, int *b) {
    for(int i = 1; i <= n; ++i) tmp[i] = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; j += i)
            tmp[j] = (tmp[j] + 1ll * a[i] * b[j/i]) % mod;
    for(int i = 1; i <= n; ++i) a[i] = tmp[i];
}
int main () {
    int T; read(T);
    while(T--) {
        read(n), read(k);
        for(int i = 1; i <= n; ++i) read(f[i]), g[i] = 1;
        while(k) {
            if(k&1) mul(f, g);
            mul(g, g); k>>=1;
        }
        for(int i = 1; i <= n; ++i) printf("%d%c", f[i], " \n"[i==n]);
    }
}

模拟赛 复活石 (狄利克雷卷积+快速幂 // 组合数学)

原文:https://www.cnblogs.com/Orz-IE/p/12056874.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!