codeforces757E. Bash Plays with Functions(狄…
2018-07-18 01:15:41来源:博客园 阅读 ()
http://codeforces.com/contest/757/problem/E
题意
Sol
非常骚的一道题
首先把给的式子化一下,设$u = d$,那么$v = n / d$
$$f_r(n) = \sum_{d \mid n} \frac{f_{r - 1}(d) + f_{r - 1}(\frac{n}{d})}{2}$$
$$= \sum_{d\mid n} f_{r - 1}(d)$$
很显然,这是$f_r(n)$与$1$的狄利克雷卷积
根据归纳法可以证明$f_r(n)$为积性函数
我们可以对每个质因子分别考虑他们的贡献
考虑$f_0(p^k) = [k =0]+1$,与$p$是无关的,因此我们只要枚举$r$和$k$就好
$f_r(p^k) = \sum_{i = 0}^k f_{r - 1}(p^i)$
前缀和优化dp
#include<cstdio> #include<cmath> #define LL long long using namespace std; const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int prime[MAXN], tot, vis[MAXN]; LL f[MAXN][22]; void GetPrime(int N) { for(int i = 2; i <= N; i++) { if(!vis[i]) prime[++tot] = i; for(int j = 1; j <= N && i * prime[j] <= N; j++) { vis[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } } void Pre(int N, int M) { f[0][0] = 1;//f[i][k] f_r(p^k) for(int i = 1; i <= M; i++) f[0][i] = 2; for(int r = 1; r <= N; r++) { LL sum = 0; for(int k = 0; k <= M; k++) { sum += f[r - 1][k]; (f[r][k] += sum ) %= mod; } } } main() { GetPrime(1e6 + 5); Pre(1e6 + 5, 21); int Q = read(); while(Q--) { int r = read(), n = read(); LL ans = 1; for(int i = 1; i <= tot && prime[i] <= sqrt(n); i++) { if(n % prime[i]) continue; int num = 0; while(!(n % prime[i])) num++, n /= prime[i]; ans = 1ll * ans * (f[r][num]) % mod; } if(n > 1) ans = (1ll * ans * f[r][1]) % mod; printf("%I64d\n", ans); } } /* */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 博弈论入门 Bash 、Nim 、Wythoff's Game结论及c++ 2019-01-23
- Bash游戏(51Nod - 1046) 2018-06-17
- linux程式设计-11.shellscript(bash)--(13)bash内建指令集_ 2008-02-23
- Linux教程(22)-在Bash中的操作 2008-02-23
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash