其实这题n可以多两个0吧

kczno1 2018-03-22 10:36:23 2018-03-22 14:56:18

就用这个打表做法
https://loj.ac/submission/78189
upd做法:
dp[i]表示还有i步没走的答案,s[i]表示dp[0]+dp[1]..dp[i],
则dp[0]=0,(移项后)dp[i]=s[i-1]/i+(i+1)/i。
答案就是dp[n-1]。
然后用s[i]消掉dp[i]
得s[i]=(i+1)/i*s[i-1]+(i+1)/i
求出s[n-2]就可以算答案了。
然后考虑每个(i+1)/i的贡献,化简可得 s[n]=(n+1) \sum_{i=1}^{n} 1/i
upd:
之前求逆元多了一个log,后来想起来求n个数的逆元可以O(n+log)
https://loj.ac/submission/78343

共 6 条回复

kczno1

竟然还有sqrt(p)log(p)的做法
不过好难读啊。

WDLGZH2017

膜拜神犇,表示出题人都没想到

kczno1

现在写了

WDLGZH2017

请简述你的做法(sorry,看不懂)

LittleRed

你的算法是怎么样的?我需要O(n)递推啊。