【hdu 5628】Clarke and math (Dirichlet卷积)
and HDU 卷积 Math
2023-09-11 14:19:24 时间
题意
Given f(i),1≤i≤n, calculate
\(\displaystyle g(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_k \mid i_{k-1}} f(i_k) \text{ mod } 1000000007 \quad (1 \le i \le n)\)
题解
Dirichlet convolution -wiki
别人的题解
恒等函数1(n)=1。
那么\(\sum_{i_k \mid i_{k-1}} f(i_k)\) 就是\(f(i_k)\)与\(1(\frac {i_{k-1}} {i_k})\) 的狄利克雷卷积
然后再和$ 1(\frac {i_{k-2}} {i_{k-1}})$卷积。。。
再用的狄利克雷卷积满足交换律,所以就是 \(g(i)=\sum_{j|i}f(j)1^k\)
代码
const int N=201000;
int n,k;
ll tmp[N],x[N],f[N],ans[N];
void dirichlet(ll *ans, ll *x){
mem(tmp,0);
rep(i,1,sqrt(n)+1){
tmp[i*i]+=ans[i]*x[i]%mod;
rep(j,i+1,n/i+1){
tmp[i*j]+=ans[i]*x[j]%mod;
tmp[i*j]+=ans[j]*x[i]%mod;
}
}
rep(i,1,n+1)
ans[i]=tmp[i]%mod;
}
void qpow(){
for(;k;k>>=1,dirichlet(x, x))
if(k&1) dirichlet(ans, x);
}
int main() {
int t;
sf(t);
while(t--){
sf(n);sf(k);
rep(i,1,n+1){
sfl(f[i]);
ans[i]=0;
x[i]=1;
}
ans[1]=1;
qpow();
dirichlet(ans, f);
rep(i,1,n+1)printf("%lld%c",ans[i],i==n?'\n':' ');
}
return 0;
}
相关文章
- [AWS DA] API Gateway and Lambda Stage variable
- [Angular2 Form] Create and Submit an Angular 2 Form using ngForm
- [Unit testing RxJS] Testing Observables with Subscribe and assert Parttern
- [Typescript Kaop-ts] Use AOP in Vue Components with TypeScript and Kaop-ts
- coroutine in Python Tornado and NodeJs
- 「翻译」Photoshop CC 2015 is copying Sketch and it's a good thing
- Settype COM_TA_MANUFAC - mapping between ERP Equipment and CRM Individual Object
- 【hdu 6438】Buy and Resell
- 【23.33%】【hdu 5945】Fxx and game
- 【hdu 1848】Fibonacci again and again
- 【hdu 2108】Shape of HDU
- 【hdu 1068】Girls and Boys
- Unity 3D 2022.1 AND UnityHub 3.2 Patch
- MySQL错误:You are using safe update mode and you tried to update a table without a WHERE that uses a K
- 迁移学习(COAL)《Generalized Domain Adaptation with Covariate and Label Shift CO-ALignment》
- HDU 5066 Harry And Physical Teacher(物理题)
- HDU 1312:Red and Black
- hdu 5057 Argestes and Sequence
- Mybatis对象关联数据库表【一对多关联AND一对一关联】
- 【快乐离散数学】谓词与量词 | 嵌套量词 | 狄摩根定律 | Predicates and Quantifiers | Nested Quantifiers