[BZOJ 3601]一个人的数论
转载请注明出处：http://danihao123.is-programmer.com/
本来想做JZPKIL的……但卡常太恶心了
上来先颓式子：
fd(n)=n∑i=1[(i,n)=1]id=n∑i=1id∑k|n,k|iμ(k)=∑k|nμ(k)nk∑i=1(ik)d=∑k|nμ(k)kdhd(nd)=((μ⋅idk)∗hd)
其中hd表示指数为d时的等幂求和函数。然后我们可能会想，如果这个函数是积性函数，那么我们可以对质因数分解的每一种质因数都求一遍答案，而由于μ的存在（对于质数的幂pk的因数，只有1和p的莫比乌斯函数值不为0），所以需要处理的情况只有两种。
不过很可惜，hd显然不是积性函数，所以最后的整个卷积也不是积性函数。但是我们注意到hd事一个d+1次多项式，所以我们可以把多项式每一项都当成单独的函数，然后每个单独函数卷出来都是一个积性函数。至于求多项式每一项的系数，用伯努利数即可。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | /************************************************************** Problem: 3601 User: danihao123 Language: C++ Result: Accepted Time:220 ms Memory:948 kb****************************************************************/ #include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <utility>typedef long long ll;ll ha = 1000000007LL;ll pow_mod(ll a, ll b) { ll ans = 1LL, res = a; while(b) { if(1LL & b) ans = (ans * res) % ha; res = (res * res) % ha; b >>= 1; } return ans;}ll inv(ll x) { return pow_mod(x, ha - 2LL);} const int maxn = 105;ll C[maxn][maxn];void process_C() { C[0][0] = 1LL; for(int i = 1; i < maxn; i ++) { C[i][0] = C[i][i] = 1LL; for(int j = 1; j < i; j ++) { C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ha; } }}ll B[maxn];void process_B() { B[0] = 1LL; for(int i = 1; i <= 101; i ++) { B[i] = 1LL; for(int j = 0; j < i; j ++) { ll d = (((C[i][j] * B[j]) % ha) * inv(i - j + 1)) % ha; B[i] = (B[i] - d + ha) % ha; } }} const int maxw = 1005;typedef std::pair<ll, ll> pii;pii P[maxw]; ll dv[maxw][3];int d, w;void process_dv() { for(int i = 1; i <= w; i ++) { ll p = P[i].first, t = P[i].second; p %= ha; dv[i][0] = pow_mod(p, t); dv[i][1] = pow_mod(p, t - 1LL); dv[i][2] = pow_mod(p, d); }}ll calc(ll k, int z) { ll ans = k; for(int i = 1; i <= w; i ++) { ll p = P[i].first, t = P[i].second; p %= ha; ll f1 = pow_mod(dv[i][0], z), f2 = pow_mod(dv[i][1], z); ll v1 = (f1 - (dv[i][2] * f2) % ha + ha) % ha; ans = (ans * v1) % ha; }#ifdef LOCAL printf("Case (%lld, %d) : %lld\n", k, z, ans);#endif return ans;} int main() { process_C(); process_B(); scanf("%d%d", &d, &w); for(int i = 1; i <= w; i ++) { scanf("%lld%lld", &P[i].first, &P[i].second); } process_dv(); ll ans = 0LL; for(int i = 0; i <= d; i ++) { ll g = calc((((C[d + 1][i] * B[i]) % ha) * inv(d + 1)) % ha, d + 1 - i); ans = (ans + g) % ha; } printf("%lld\n", ans); return 0;} |
评论 (0)
