🌑

小羊儿的心情天空

2019 ICPC南京网络赛部分题解

Sep 1, 2019 由 小羊

B. super_log

就考察一下你是不是真的理解了拓展欧拉定理。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e6+5;
int pri[MAXN], pcn, phi[MAXN];
bool isnp[MAXN];

lld fpow(lld a, lld k, lld m)
{
    lld b = 1;
    for (; k; k>>=1, a=a*a%m)
        if (k&1) b=b*a%m;
    return b;
}

bool judge(lld a, lld k, lld m)
{
    lld b = 1;
    while (k)
    {
        b = b * a;
        if (b >= m) return true;
        k--;
    }
    return false;
}

lld getAns(int a, int b, int m)
{
    if (m == 1) return a < m ? 0 : m;
    if (b == 0) return 1;
    lld t = getAns(a, b-1, phi[m]);
    lld ans = fpow(a, t, m);
    bool lg = t < phi[m] ? judge(a, t, m) : true;
    if (lg) ans += m;
    //printf("f(%d,%d,%d)=%lld\n", a, b, m, ans);
    return ans;
}

void solve()
{
    int a, b, m;
    scanf("%d %d %d", &a, &b, &m);
    printf("%lld\n", getAns(a,b,m)%m);
}

int main()
{
    phi[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i]) pri[pcn++] = i, phi[i] = i-1;
        for (int j = 0; j < pcn; j++)
        {
            int k = i * pri[j];
            if (k >= MAXN) break;
            isnp[k] = true;
            if (i % pri[j] == 0) { phi[k] = phi[i] * pri[j]; break; }
            else phi[k] = phi[i] * (pri[j] - 1);
        }
    }

    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

C. Tsy’s number 5

抄题解。令 fk=i=1n[φ(i)=k]f_k = \sum_{i=1}^n [\varphi(i)=k],则有

ans=i=1nj=1nφ(i)φ(j)2φ(i)φ(j)=i=1nj=1nfifjij2ij=2i=1nj=1ififjij2iji=1nfi2i22j2=2i=1nfiij=1ifjj22iji=1nfi2i22j2=2i=1nfii2i2j=1ifjj2j22(ij)2i=1nfi2i22j2\begin{aligned} ans & = \sum_{i=1}^n \sum_{j=1}^n \varphi(i) \varphi(j) 2^{\varphi(i) \varphi(j)} \\ & = \sum_{i=1}^n \sum_{j=1}^n f_i f_j ij 2^{ij} \\ & = 2 \sum_{i=1}^n \sum_{j=1}^i f_i f_j ij 2^{ij} - \sum_{i=1}^n {f_i}^2 i^2 2^{j^2} \\ & = 2 \sum_{i=1}^n f_ii \sum_{j=1}^i f_jj {\sqrt2}^{2ij} - \sum_{i=1}^n {f_i}^2 i^2 2^{j^2} \\ & = 2 \sum_{i=1}^n f_ii {\sqrt2}^{i^2} \sum_{j=1}^i f_jj {\sqrt2}^{j^2} {\sqrt2}^{-(i-j)^2} - \sum_{i=1}^n {f_i}^2 i^2 2^{j^2} \end{aligned}

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
const int MOD = 998244353, G = 3;
const int SQRT2 = 116195171;
int phi[MAXN], sp[MAXN], qwq[MAXN], A[262144], B[262144];

inline lld fpow(lld a, lld k)
{
    lld b = 1;
    for (; k; k>>=1, a=a*a%MOD)
        if (k & 1) b=b*a%MOD;
    return b;
}

inline void init_prime()
{
    static int pri[MAXN], pcn;
    static bool isnp[MAXN];

    phi[1] = sp[0] = 1; sp[1] = fpow(SQRT2, MOD-2);
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i]) pri[pcn++] = i, phi[i] = i-1;
        sp[i] = fpow(SQRT2, MOD-1-1ll*i*i%(MOD-1));
        for (int j = 0; j < pcn; j++)
        {
            if (i * pri[j] >= MAXN) break;
            isnp[i * pri[j]] = true;
            if (i % pri[j] == 0) { phi[i * pri[j]] = phi[i] * pri[j]; break; }
            else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
}

inline void dft(int a[], int DFT, int N)
{
    static int rev[262144], wmk[262144];
    for (int i = 0; i < N; i++)
        rev[i] = (rev[i>>1]>>1)|((i&1)?(N>>1):0);
    for (int i = 0; i < N; i++)
        if (i < rev[i]) swap(a[i], a[rev[i]]);

    for (int m = 2, m2 = 1; m <= N; m <<= 1, m2 <<= 1) {
        wmk[0] = 1, wmk[1] = fpow(G, (MOD-1)/m*DFT+(DFT==-1?MOD-1:0));
        for (int j = 2; j < m2; j++) wmk[j] = 1ll * wmk[j-1] * wmk[1] % MOD;
        for (int k = 0; k < N; k += m)
            for (int j = 0, u, t; j < m2; j++)
                t = 1ll * wmk[j] * a[k+j+m2] % MOD, u = a[k+j],
                a[k+j] = (u+t)%MOD, a[k+j+m2] = (u-t+MOD)%MOD;
    }

    if (DFT == -1)
        for (int i = 0, invN = fpow(N, MOD-2); i < N; i++)
            a[i] = 1ll * a[i] * invN % MOD;
}

inline void solve()
{
    int n; scanf("%d", &n);
    int len = 1; while (len < n+1) len <<= 1; len <<= 1;
    for (int i = 0; i < len; i++) A[i] = B[i] = 0;
    for (int i = 0; i <= n; i++) B[i] = sp[i], A[phi[i]]++;
    for (int i = 0; i <= n; i++)
        qwq[i] = A[i] = 1ll * i * A[i] % MOD * fpow(SQRT2, 1ll*i*i%(MOD-1)) % MOD;
    dft(A, 1, len); dft(B, 1, len);
    for (int i = 0; i < len; i++) A[i] = 1ll * A[i] * B[i] % MOD;
    dft(A, -1, len); lld ans = 0;
    for (int i = 1; i <= n; i++)
        ans += (2ll * A[i] - qwq[i]) * qwq[i] % MOD;
    ans %= MOD; if (ans < 0) ans += MOD;
    printf("%lld\n", ans);
}

int main()
{
    init_prime();
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

D. Robots

考虑从 uu 出发,到达 nn 的期望步数,逆向建图拓扑排序搞定。

dp[u]=1d(u)+1(dp[u]+(u,v)Gdp[v])+1dp[u] = \frac{1}{d(u) + 1} \left( dp[u] + \sum_{(u,v)\in G} dp[v] \right) + 1

再考虑从 uu 出发,到达 nn 的期望消耗天数累计值,则有

dp2[u]=1d(u)+1(dp2[u]+(u,v)Gdp2[v])+dp[u]dp2[u] = \frac{1}{d(u) + 1} \left( dp2[u] + \sum_{(u,v)\in G} dp2[v] \right) + dp[u]

其实是乱搞猜结论出来的,但是后面那个 dp[u]dp[u] 的意义其实可以理解为,我这一步到终点的天数,是由路径上的每条边叠加得到的。

这个期望的期望好像题解没给证明,先这样吧QAQ。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
vector<int> G[MAXN];
int d[MAXN], d2[MAXN], Q[MAXN];
double one[MAXN], dp[MAXN], dp2[MAXN];

void run(double dp[], double dist[], int n)
{
    int front = 0, rear = 0; Q[rear++] = n;
    memcpy(d, d2, sizeof(d));

    while (front < rear)
    {
        int u = Q[front++];
        if (u != n) dp[u] = (d2[u]+1.0)/d2[u]*dist[u] + dp[u]/d2[u];

        for (auto v : G[u])
        {
            d[v]--; if (d[v] == 0) Q[rear++] = v;
            dp[v] += dp[u];
        }
    }
}

void solve()
{
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        dp2[i] = dp[i] = d2[i] = 0, G[i].clear(), one[i]=1;
    for (int i = 0, u, v; i < m; i++)
        scanf("%d %d", &u, &v), G[v].push_back(u), d2[u]++;
    run(dp, one, n);
    run(dp2, dp, n);
    printf("%.2lf\n", dp2[1]);
}

int main()
{
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

E. K Sum

套路变换。

fn(k)=d=1nd2(li=1n)k[gcd(li)=1]=d=1nd2i=1n/dμ(i)nidk=s=1n(id=sd2μ(i))nsk\begin{aligned} f_n(k) & = \sum_{d=1}^n d^2 \left({\sum_{l_i=1}^n}\right)^k [\gcd(l_i) = 1] \\ & = \sum_{d=1}^n d^2 \sum_{i=1}^{\lfloor n/d \rfloor} \mu(i) \left\lfloor \frac{n}{id} \right\rfloor^k \\ & = \sum_{s=1}^n \left(\sum_{id=s}d^2 \mu(i)\right)\left\lfloor\frac{n}{s}\right\rfloor^k \end{aligned}

合并,后面那个等比数列求和,注意特判 11,所以需要得到 kmod1e9+7k \mod 1e9+7kmod1e9+6k \mod 1e9+6

i=2kfn(i)=s=1ng(s)i=2knsi\sum_{i=2}^k f_n(i) = \sum_{s=1}^n g(s) \sum_{i=2}^k\left\lfloor\frac{n}{s}\right\rfloor^i

杜教筛部分看起来像是 id2μid^2 * \mu,那么配上 11

S(n)=i=1ng(i)=n(n+1)(2n+1)6i=2nS(ni)S(n) = \sum_{i=1}^n g(i) = \frac{n(n+1)(2n+1)}{6} - \sum_{i=2}^n S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MOD = 1e9+7;
const int MAXN = 3e6+5;
int _G1[MAXN];

void init_prime()
{
    static int pri[MAXN], pcn;
    static bool isnp[MAXN];

    _G1[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i]) pri[pcn++] = i, _G1[i] = (1ll * i * i-1) % MOD;
        for (int j = 0; j < pcn; j++)
        {
            if (i * pri[j] >= MAXN) break;
            isnp[i * pri[j]] = true;
            if (i % pri[j] == 0)
            {
                _G1[i * pri[j]] = _G1[i] * 1ll * pri[j] % MOD * pri[j] % MOD;
                break;
            }
            else
            {
                _G1[i * pri[j]] = _G1[i] * (1ll * pri[j] % MOD * pri[j] - 1)% MOD;
            }
        }
    }

    for (int i = 1; i < MAXN; i++)
        _G1[i] = (_G1[i-1] + _G1[i]) % MOD;
}

lld sumG(int n)
{
    static map<int,lld> _G2;
    if (n < MAXN) return _G1[n];
    if (_G2.count(n)) return _G2[n];

    lld ans = n * (n+1ll) % MOD * (2ll*n+1) % MOD * ((MOD+1)/6) % MOD;
    for (int L = 2, R; L <= n; L = R+1)
    {
        R = n / (n / L);
        ans -= (R-L+1) * sumG(n/L) % MOD;
    }

    ans %= MOD; if (ans < 0) ans += MOD;
    return _G2[n] = ans;
}

inline lld fpow(lld a, lld k)
{
    lld b = 1;
    for (; k; k>>=1, a=a*a%MOD)
        if (k&1) b=a*b%MOD;
    return b;
}

inline lld powers(int ns, int k, int k2)
{
    if (ns == 1) return k2-1;
    lld ans = fpow(ns, k+1) - 1ll * ns * ns % MOD;
    ans = ans * fpow(ns-1, MOD-2) % MOD;
    return ans;
}

inline void solve()
{
    int n, k = 0, k2 = 0; lld ans = 0;
    static char kk[MAXN];
    scanf("%d %s", &n, kk);
    for (int i = 0; kk[i]; i++)
        k = (k * 10ll + kk[i] - '0') % (MOD-1),
        k2 = (k2 * 10ll + kk[i] - '0') % MOD;

    for (int L = 1, R; L <= n; L = R+1)
    {
        R = n / (n / L);
        ans += (sumG(R) - sumG(L-1)) * powers(n/L, k, k2) % MOD;
    }

    ans %= MOD; if (ans < 0) ans += MOD;
    printf("%lld\n", ans);
}

int main()
{
    init_prime();
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

G. Quadrilateral

参考题解。我怎么写了一坨屎QAQ。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
inline lld sum1(lld c) { return c*(c+1)/2; }
inline lld sum2(lld c) { return c*(c+1)*(2*c+1)/6; }

// count the pairs for [1,a] + [1,b] <= [1,c]
inline lld func1(lld a, lld b, lld c)
{
    if (a > b) swap(a, b); c--;
    if (a < 1 || b < 1) return 0;
    if (c <= 0) return 0;
    else if (c < a) return sum1(c)*(c+1) - sum2(c);
    else if (c <= b) return (c+1-a)*(c+1-a)*a - sum1(c-a)*a + sum1(a-1)*(c+1) - sum2(a-1);
    else if (c < a+b) return (c-b)*(a+b)*(c+1) - (a+b+c+1)*(sum1(c)-sum1(b)) + (sum2(c)-sum2(b)) + (b+1-a)*(c+1-a)*a - sum1(b-a)*a + sum1(a-1)*(c+1) - sum2(a-1);
    else return a*(a+b)*(c+1) - (a+b+c+1)*(sum1(a+b)-sum1(b)) + (sum2(a+b)-sum2(b)) + (b+1-a)*(c+1-a)*a - sum1(b-a)*a + sum1(a-1)*(c+1) - sum2(a-1);
}

// calc the valid pairs of ([1,a], [1,b], [1,c], d)
inline lld func2(lld a, lld b, lld c, lld d)
{
    return a * b * c
         - func1(b, c, a-d)
         - func1(a, c, b-d)
         - func1(a, b, c-d)
         - func1(a, b, d-1)
         + func1(a, b, d-c-1);
}

// calc the valid pairs of ([la,ra], [lb,rb], [lc,rc], d)
inline lld func3(pair<int,int> a, pair<int,int> b, pair<int,int> c, int d)
{
    return func2(a.second, b.second, c.second, d)
         - func2(a.second, b.first-1, c.second, d)
         - func2(a.first-1, b.second, c.second, d)
         - func2(a.second, b.second, c.first-1, d)
         + func2(a.first-1, b.first-1, c.second, d)
         + func2(a.first-1, b.second, c.first-1, d)
         + func2(a.second, b.first-1, c.first-1, d)
         - func2(a.first-1, b.first-1, c.first-1, d);
}

inline void solve()
{
    pair<int,int> iv[4]; lld ans = 0;
    for (int i = 0; i < 4; i++)
        scanf("%d %d", &iv[i].first, &iv[i].second);
    for (int i = iv[3].first; i <= iv[3].second; i++)
        ans += func3(iv[0], iv[1], iv[2], i);
    printf("%lld\n", ans);
}

int main()
{
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}