{"id":39,"date":"2022-09-23T18:15:26","date_gmt":"2022-09-23T10:15:26","guid":{"rendered":"http:\/\/43.129.93.179\/?p=39"},"modified":"2023-03-07T01:22:56","modified_gmt":"2023-03-06T17:22:56","slug":"solution-for-icpc-online1-problem-f","status":"publish","type":"post","link":"http:\/\/yuri3.cn\/?p=39","title":{"rendered":"Solution For ICPC Online#1 Problem F"},"content":{"rendered":"

\u9898\u610f\uff1a\u7ed9\u5b9an,k<\/span>,\u6c42\u89e3\u957f\u5ea6\u4e3ak<\/span>\u7684\u6570\u5217a<\/span>,\u6ee1\u8db3a_{i} \\mid a_{i+1}<\/span>,\u5176\u4e2dn,k\\leq 10^9<\/span>\u3002
\n
\n\u9996\u5148\u6709\u4e2a\u660e\u663e\u7684dp\u65b9\u7a0b,\u5176\u4e2ddp(n,k)<\/span>\u8868\u793a\u8003\u8651\u5230\u7b2ck<\/span>\u4e2a\u6570\u672b\u5c3e\u7684\u6570\u4e3an<\/span>\u7684\u5408\u6cd5\u6570\u5217\u7684\u65b9\u6848\u6570\uff1a<\/p>\n

dp(n,k)=\\sum_{d\\mid n}dp(d,k-1)<\/span><\/p>\n

\u8003\u8651\u5199\u6210\u8fea\u5229\u514b\u96f7\u5377\u79ef\u5f62\u5f0f\uff1a<\/p>\n

dp(n,k)=dp(n,k-1)*I<\/span><\/p>\n

\u5f53k<\/span>\u7b49\u4e8e1<\/span>\u65f6\uff0c\u8fb9\u754c\u53d6\u503c\u5747\u4e3a1<\/span>\uff0c\u56e0\u6b64\u672c\u9898\u5b9e\u9645\u4e0a\u8981\u6c42\u7684\u4e1c\u897f\u5176\u5b9e\u662f\uff1a<\/p>\n

\\sum_{i=1}^{n}I^k(i)<\/span><\/p>\n

\u5176\u4e2dI<\/span>\u4e3a\u7f6e1<\/span>\u51fd\u6570\uff0c\u5e42\u6b21\u4ee3\u8868\u8fea\u5229\u514b\u96f7\u5377\u79ef\uff0c\u5176\u5b9e\u5c31\u662fI<\/span>\u51fd\u6570\u8fea\u5229\u514b\u96f7\u5377\u79efk<\/span>\u6b21\u3002
\n\u7531\u4e8eI<\/span>\u4e3a\u79ef\u6027\u51fd\u6570\uff0cI^k<\/span>\u4ea6\u4e3a\u79ef\u6027\u51fd\u6570\u3002\u6839\u636e\u7ecf\u5178\u65b9\u6cd5\uff0c\u53ea\u9700\u8981\u77e5\u9053I^k(p^t)<\/span>\u7684\u53d6\u503c\u5373\u53ef\u5957\u7528min_25\u7b5b\u6c42\u89e3\u672c\u9898\u3002
\n\u8003\u8651\u8d1d\u5c14\u7ea7\u6570\uff0cI_p(x)=\\frac{1}{1-x}<\/span>\uff0c\u6545I^k_p(x)=(1-x)^{-k}<\/span>\uff0cp^t<\/span>\u7684\u53d6\u503c\u5176\u5b9e\u662f\u8d1d\u5c14\u7ea7\u6570[x^t]<\/span>\u7684\u53d6\u503c\uff0c\u6839\u636e\u5e7f\u4e49\u4e8c\u9879\u5f0f\u5b9a\u7406\uff0c\u4e3a\\binom{k+t-1}{t}<\/span>\u3002<\/p>\n

\u6bd4\u8d5b\u7684\u65f6\u5019\u6211\u6ca1\u8003\u8651\u8d1d\u5c14\u7ea7\u6570\uff0c\u624b\u63a8\u4e00\u4e0b\u4e5f\u5e76\u4e0d\u96be\uff0c\u672c\u8d28\u4e0a\u662f\u4e2ak<\/span>\u6b21\u524d\u7f00\u548c\u3002<\/p>\n

\nCode<\/summary>\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing i64 = long long;\ntemplate <int mod>\nstruct mint {\n    int x;\n    mint() : x(0) {}\n    mint(i64 y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}\n    mint &operator+=(const mint &p) {\n        if ((x += p.x) >= mod) x -= mod;\n        return *this;\n    }\n    mint &operator-=(const mint &p) {\n        if ((x += mod - p.x) >= mod) x -= mod;\n        return *this;\n    }\n    mint &operator*=(const mint &p) {\n        x = (int)(1ll * x * p.x % mod);\n        return *this;\n    }\n    mint &operator\/=(const mint &p) {\n        *this *= p.inverse();\n        return *this;\n    }\n    mint operator-() const { return mint(-x); }\n    mint operator+(const mint &p) const { return mint(*this) += p; }\n    mint operator-(const mint &p) const { return mint(*this) -= p; }\n    mint operator*(const mint &p) const { return mint(*this) *= p; }\n    mint operator\/(const mint &p) const { return mint(*this) \/= p; }\n    bool operator==(const mint &p) const { return x == p.x; }\n    bool operator!=(const mint &p) const { return x != p.x; }\n    mint inverse() const {\n        int a = x, b = mod, u = 1, v = 0, t;\n        while (b > 0) {\n            t = a \/ b;\n            swap(a -= t * b, b);\n            swap(u -= t * v, v);\n        }\n        return mint(u);\n    }\n    friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }\n    friend istream &operator>>(istream &is, mint &a) {\n        i64 t;\n        is >> t;\n        a = mint<mod>(t);\n        return is;\n    }\n    int get() const { return x; }\n    static constexpr int get_mod() { return mod; }\n};\ni64 n, k;\nvector<int> prime_en(int N) {\n    vector<int> sieve(N \/ 3 + 1, 1);\n    for (int p = 5, d = 4, i = 1, sqn = sqrt(N); p <= sqn;\n         p += d = 6 - d, i++) {\n        if (!sieve[i]) continue;\n        for (int q = p * p \/ 3, r = d * p \/ 3 + (d * p % 3 == 2), s = 2 * p,\n                 qe = sieve.size();\n             q < qe; q += r = s - r)\n            sieve[q] = 0;\n    }\n    vector<int> ret{2, 3};\n    for (int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++) {\n        if (sieve[i]) ret.push_back(p);\n    }\n    while (!ret.empty() && ret.back() > N) ret.pop_back();\n    return ret;\n}\nconstexpr int mod = 1e9 + 7;\nusing Z = mint< mod >;\nconstexpr int N = 60;\nvector<Z> inv(N + 1);\nZ f(i64 p, i64 t) {\n    \/*\n        C(k+t-1,t)\n    *\/\n    Z res = 1;\n    for (i64 base = k + t - 1, now = 1; now <= t; now++, base--) {\n        res *= Z(base);\n    }\n    for (int i = 1; i <= t; i++) res *= inv[i];\n    return res;\n}\ntemplate < typename T, T (*f)(i64, i64) >\nstruct mf {\n    i64 M, sq, s;\n    vector< int> p;\n    int ps;\n    vector<T> buf;\n    T ans;\n    mf(i64 m) : M(m) {\n        sq = sqrt(M);\n        while (sq * sq > M) sq--;\n        while ((sq + 1) * (sq + 1) <= M) sq++;\n        if (M != 0) {\n            i64 hls = md(M, sq);\n            if (hls != 1 && md(M, hls - 1) == sq) hls--;\n            s = hls + sq;\n            p = prime_en(sq);\n            ps = p.size();\n            ans = T{};\n        }\n    }\n    vector<T> pi_table() {\n        if (M == 0) return {};\n        i64 hls = md(M, sq);\n        if (hls != 1 && md(M, hls - 1) == sq) hls--;\n\n        vector<i64> hl(hls);\n        for (int i = 1; i < hls; ++i) hl[i] = md(M, i) - 1;\n\n        vector<int> hs(sq + 1);\n        iota(begin(hs), end(hs), -1);\n\n        int pi = 0;\n        for (auto &x : p) {\n            i64 x2 = i64(x) * x;\n            i64 imax = min<i64>(hls, md(M, x2) + 1);\n            for (i64 i = 1, ix = x; i < imax; ++i, ix += x) {\n                hl[i] -= (ix < hls ? hl[ix] : hs[md(M, ix)]) - pi;\n            }\n            for (int n = sq; n >= x2; --n) hs[n] -= hs[md(n, x)] - pi;\n            pi++;\n        }\n\n        vector<T> res;\n        res.reserve(2 * sq + 10);\n        for (auto &x : hl) res.push_back(x);\n        for (int i = hs.size(); --i;) res.push_back(hs[i]);\n        return res;\n    }\n    vector<T> prime_sum_table() {\n        if (M == 0) return {};\n        i64 hls = md(M, sq);\n        if (hls != 1 && md(M, hls - 1) == sq) hls--;\n        vector<T> h(s);\n        T inv2 = T{2}.inverse();\n        for (int i = 1; i < hls; i++) {\n            T x = md(M, i);\n            h[i] = x * (x + 1) * inv2 - 1;\n        }\n        for (int i = 1; i <= sq; i++) {\n            T x = i;\n            h[s - i] = x * (x + 1) \/ 2 - 1;\n        }\n        for (auto &x : p) {\n            T xt = x;\n            T pi = h[s - x + 1];\n            i64 x2 = i64(x) * x;\n            i64 imax = min<i64>(hls, md(M, x2) + 1);\n            i64 ix = x;\n            for (i64 i = 1; i < imax; ++i, ix += x) {\n                h[i] -= ((ix < hls ? h[ix] : h[s - md(M, ix)]) - pi) * xt;\n            }\n            for (int n = sq; n >= x2; n--) {\n                h[s - n] -= (h[s - md(n, x)] - pi) * xt;\n            }\n        }\n        return h;\n    }\n    void dfs(int i, int c, i64 prod, T cur) {\n        ans += cur * f(p[i], c + 1);\n        i64 lim = md(M, prod);\n        if (lim >= 1ll * p[i] * p[i]) dfs(i, c + 1, p[i] * prod, cur);\n        cur *= f(p[i], c);\n        ans += cur * (buf[idx(lim)] - buf[idx(p[i])]);\n        int j = i + 1;\n        for (; j < ps && 1ll * p[j] * p[j] * p[j] <= lim; j++) {\n            dfs(j, 1, prod * p[j], cur);\n        }\n        for (; j < ps && 1ll * p[j] * p[j] <= lim; j++) {\n            T sm = f(p[j], 2);\n            int id1 = idx(md(lim, p[j])), id2 = idx(p[j]);\n            sm += f(p[j], 1) * (buf[id1] - buf[id2]);\n            ans += cur * sm;\n        }\n    }\n    T run(vector<T> &fprime) {\n        if (M == 0) return {};\n        set_buf(fprime);\n        ans = buf[idx(M)] + 1;\n        for (int i = 0; i < ps; i++) dfs(i, 1, p[i], 1);\n        return ans;\n    }\n\n    i64 md(i64 n, i64 d) { return double(n) \/ d; }\n    i64 idx(i64 n) { return n <= sq ? s - n : md(M, n); }\n    void set_buf(vector<T> &_buf) { swap(buf, _buf); }\n};\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n\n    for (int i = 1; i <= 60; i++) {\n        inv[i] = Z(i).inverse();\n    }\n\n    cin >> n >> k;\n\n    mf<Z, f> solve(n);\n    auto q = solve.pi_table();\n\n    for (auto &qq : q) qq *= Z(k);\n    auto ans = solve.run(q);\n    cout << ans;\n\n    return 0;\n}\n\n<\/code><\/pre>\n<\/details>\n","protected":false},"excerpt":{"rendered":"
\u9898\u610f\uff1a\u7ed9\u5b9an,k,\u6c42\u89e3\u957f\u5ea6\u4e3ak\u7684\u6570\u5217a,\u6ee1\u8db3a_{i...<\/p>\n","protected":false},"author":1,"featured_media":95,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[5],"tags":[],"_links":{"self":[{"href":"http:\/\/yuri3.cn\/index.php?rest_route=\/wp\/v2\/posts\/39"}],"collection":[{"href":"http:\/\/yuri3.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yuri3.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yuri3.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/yuri3.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=39"}],"version-history":[{"count":73,"href":"http:\/\/yuri3.cn\/index.php?rest_route=\/wp\/v2\/posts\/39\/revisions"}],"predecessor-version":[{"id":308,"href":"http:\/\/yuri3.cn\/index.php?rest_route=\/wp\/v2\/posts\/39\/revisions\/308"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/yuri3.cn\/index.php?rest_route=\/wp\/v2\/media\/95"}],"wp:attachment":[{"href":"http:\/\/yuri3.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=39"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yuri3.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=39"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yuri3.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=39"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}