2020.1.17考试总结

T1
\(n \le 20 ,m \le n!\)
这道题可以证明一定有解，我们每次找出 比我们要凑成的数小且是n!的约数 里最大的数就可以了。跑得飞快~

#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
LL n, m, jc, tot, js;
const LL N = 3700010, inf = 0x3f3f3f3f3f3f3f3f;
LL w[N], cnt[N], ans[N];
inline int read() 
{
    int res = 0; char ch = getchar(); bool XX = false;
    for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
    for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
    return XX ? -res : res;
}
void fen() 
{
    LL t = jc;
    for (int i = 2; i * i <= t; ++i)
        if (!(t % i)) 
        {
            w[++tot] = i;
            while (!(t % i))++cnt[tot], t /= i;
        }
    if (t != 1)w[++tot] = t, ++cnt[tot];
}
LL dfs2(LL now, LL ans, LL top) 
{
    if (now == tot + 1)return ans;
    if (ans > top)return 0;
    LL res = 0;
    for (int i = 0; i <= cnt[now]; ++i) 
    {
        res = max(res, dfs2(now + 1, ans, top));
        ans *= w[now];
        if (ans > top)break;
    }
    return res;
}
void dfs(LL x) 
{
    if (!(jc % x)) {ans[++js] = x; return;}
    LL t = dfs2(1, 1, x);
    ans[++js] = t;
    dfs(x - t);
}
signed main() 
{
    cin >> n >> m; jc = 1;
    for (int i = 1; i <= n; ++i)jc *= i;
    fen(); dfs(m);
    cout << js << endl;
    for (int i = 1; i <= js; ++i)printf("%lld ", ans[i]);
    fclose(stdin); fclose(stdout);
    return 0;
}

T2
\(n \le 10^6\)
这道题之前做过，其实就是把求有多少个不同的子串放到了树上，我们只需要在建后缀自动机的时候把id[fa[x]]当成last就行了，统计的时候ans += len[i] - len[fa[i]];就行了.

#include<iostream>
#include<cstdio>
#include<map>
#define LL long long
using namespace std;
int n, tot, x, y, cnt;
LL ans;
const int N = 1000010;
int head[N], du[N], fa[N << 1], id[N], len[N << 1];
map<int, int>tr[N << 1];
struct bian {int to, nt;} e[N << 1];
void add(int f, int t) 
{
    e[++tot] = (bian) {t, head[f]};
    head[f] = tot;
}
inline int read() 
{
    int res = 0; char ch = getchar(); bool XX = false;
    for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
    for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
    return XX ? -res : res;
}
void Insert(int x, int Q, int las) 
{
    int np = ++cnt, p = las, q, nq;
    len[np] = len[p] + 1; id[Q] = cnt;
    for (; p && tr[p].find(x) == tr[p].end(); p = fa[p])tr[p][x] = np;
    if (!p)fa[np] = 1;
    else if (len[q = tr[p][x]] == len[p] + 1)fa[np] = q;
    else 
    {
        len[nq = ++cnt] = len[p] + 1;
        fa[nq] = fa[q]; fa[q] = fa[np] = nq; tr[nq] = tr[q];
        for (; p; p = fa[p]) 
        {
            if (tr[p].find(x) == tr[p].end() || tr[p][x] != q)break;
            tr[p][x] = nq;
        }
    }
}
void dfs(int x, int fa) 
{
    Insert(du[x], x, id[fa]);
    for (int i = head[x]; i; i = e[i].nt)
        if (e[i].to != fa)dfs(e[i].to, x);
}
int main() 
{
    cnt = id[0] = 1; cin >> n;
    for (int i = 1; i < n; ++i)
        x = read(), y = read(), add(x, y), add(y, x), ++du[x], ++du[y];
    dfs(1, 0);
    for (int i = 2; i <= cnt; ++i)ans += len[i] - len[fa[i]];
    cout << ans;
    return 0;
}

T3
提交答案题，这里就不讲了...
下午
对于任意的积性函数 \(f\),有\(f(gcd(a,b)) \times f(lcm(a,b)) = f(a) \times f(b)\)。然后就变成了\(\displaystyle (\sum_{i=1}^nf(i))^2\)
然后就是杜教筛了，\(g\)为\(id\),\(f*g=1\),证明.
注意取模

#include<iostream>
#include<cstdio>
#include<map>
#define LL long long
using namespace std;
LL n, tot, ans;
const int mod = 1e9 + 7, inv2 = (mod + 1) >> 1, N = 1000010, M = 1000000;
int vis[N], zhi[N], f[N];
map<LL, LL>mp;
void YYCH() 
{
    vis[1] = f[1] = 1;
    for (int i = 2; i <= M; ++i) 
    {
        if (!vis[i])zhi[++tot] = i, f[i] = 1 - i;
        for (int j = 1; j <= tot && i * zhi[j] <= M; ++j) 
        {
            vis[i * zhi[j]] = 1;
            if (!(i % zhi[j])) {f[i * zhi[j]] = f[i]; break;}
            f[i * zhi[j]] = f[i] * f[zhi[j]];
        }
    }
    for (int i = 2; i <= M; ++i)(f[i] += f[i - 1]) %= mod;
}
LL Sum(LL l, LL r) {return (l + r) * (r - l + 1) % mod * inv2 % mod;}
LL S(LL n) 
{
    if (n <= M)return f[n];
    if (mp.count(n))return mp[n];
    LL res = 0;
    for (LL l = 2, r; l <= n; l = r + 1) 
    {
        r = n / (n / l);
        (res += Sum(l, r) % mod * S(n / l) % mod) %= mod;
    }
    return mp[n] = (n - res) % mod;
}
signed main() 
{
    cin >> n;
    YYCH();
    ans = S(n);
    cout << (ans * ans % mod + mod) % mod;
    fclose(stdin); fclose(stdout);
    return 0;
}