A. 字符画

知识点

思维、模拟。

大致思路

从左到右竖着遍历每一列，当遍历到 '#' 时依次查看当前字符是否是字符 2 -> 字符 3 -> 字符 1，如果是则把字符用'.'覆盖掉。

我们可以发现这种遍历方式可以唯一区分这三种字符，同时字符画本身又是合法，那么最终总能把所有字符覆盖掉，只需覆盖时计算即可。

此外，判断字符顺序并不唯一，同时也有从下到上的遍历方式也能得到正确答案。

参考代码

#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> Char = {
    {
        {0, 0}, {0, 1}, {0, 2},
        {1, 0},         {1, 2},
        {2, 0}, {2, 1}, {2, 2},
        {3, 0},
        {4, 0}
    },
    {
        {0, 0}, {0, 1}, {0, 2},
                        {1, 2},
                {2, 1}, {2, 2},
                        {3, 2},
                        {4, 2}
    },
    {
        {0, 0}, {0, 1}, {0, 2},
        {1, 0},         {1, 2},
        {2, 0}, {2, 1}, {2, 2},
        {3, 0},         {3, 2},
        {4, 0}, {4, 1}, {4, 2}
    }
};
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for(int i = 0; i < n; i++ ){
    	cin >> s[i];
    }

    vector<int> ans(3);
    auto print = [&](int i, int j, int id){
        for(auto [dx, dy] : Char[id]){
            int x = i + dx, y = j + dy;
            s[x][y] = '.';
        }
        ans[id] += 1;
    };
    for(int i = 0; i < m; i++ ){ //遍历列
        for(int j = 0; j < n; j++ ){ //竖着遍历每一列
            if(s[j][i] != '#'){
                continue;
            }
            // 先判断字符2
            if(s[j + 1][i] != '#'){
                print(j, i, 1);
                continue;
            }
            // 再判断字符3和字符1
            bool ok = true;
            for(auto [dx, dy] : Char[2]){
                int x = j + dx, y = i + dy;
                if(s[x][y] != '#'){
                    ok = false;
                }
            }
            print(j, i, (ok ? 2 : 0));
        }
    }

    for(int i = 0; i < 3; i++ ){
        cout << ans[i] << " \n"[i == 2];
    }
    return 0;
}

B. A+B Problem

知识点

$FFT$ ，根号分治。

大致思路

先考虑一个暴力做法，设 $c_i$ 表示数字 $i$ 在数组 $a$ 中的出现次数，对于询问到的每一个 $x$ ，求 $\sum_{i j=x}min(c_i,c_j)$ 即为当前询问的答案，单次询问的时间复杂度 $O(m)$ ；

一共有 $q$ 次询问，最坏情况下每次询问的 $x$ 都不一样，相当于对于每一个 $x\in[1,2m]$ ，我们都需要求一次 $\sum_{i j=x}min(c_i,c_j)$ ，总的时间复杂度 $O(mq)$ ；

$\\$ $\\$

考虑优化求和式子，用 $cnt$ 枚举数字的出现次数来将式子中的 $min$ 转换掉，这样一来，对于每一个 $x$ ，我们需要求的就是： $\sum_{cnt=1}^{n}\sum_{i j=x}[c_i\geq{cnt}][c_j\geq{cnt}]$ ；

令 $b_i=[c_i\geq cnt],b_j=[c_j\geq cnt]$ ，则可以将 $\sum_{i j=x}[c_i\geq{cnt}][c_j\geq{cnt}]$ 转换为 $\sum_{i j=x}b_i\times b_j$ ，不难发现这是一个卷积的形式，使用 $FFT$ 即可在 $O(mlogm)$ 的时间复杂度内计算该求和式子；

再注意到 $n=\sum_{i=1}^{m}c_i$ ，有一个经典性质：不同的 $c_i$ 种数至多只有 $\sqrt n$ 种；

因此，在式子 $\sum_{cnt=1}^{n}\sum_{i j=x}[c_i\geq{cnt}][c_j\geq{cnt}]$ 中， $cnt$ 至多只有 $\sqrt n$ 种不同的取值，整个式子可以在 $O(m\sqrt n logm)$ 的时间复杂度内计算；

$\\$ $\\$

考虑继续优化，设置阈值 $B$ ，对 $cnt$ 的大小进行分别处理：

①：当 $cnt\leq B$ 时，使用上述式子 $\sum_{cnt=1}^{B}\sum_{i j=x}[c_i\geq{cnt}][c_j\geq{cnt}]$ 来计算，时间复杂度 $O(Bmlogm)$ ；

②：当 $cnt>B$ 时，满足这个条件的不同数字个数不超过 $O(\frac{n}{B})$ 个，于是可以通过 $O(\frac{n^2}{B^2})$ 的时间复杂度暴力枚举两个数字 $i,j$ 来计算，即 $\sum_{i j=x}min(c_i,c_j)-B$ ，注意这里减 $B$ 是为了减去 $cnt\leq B$ 时数字 $i,j$ 的贡献；

令 $Bmlogm=\frac{n^2}{B^2}$ ，则当 $B=(\frac{n^2}{mlogm})^{\frac{1}{3}}$ 时，复杂度达到最优；

相比于 ② 的暴力枚举，① 的 $FFT$ 的常数较大，可以将 $B$ 适当降低以达到更快的程序运行效率；

总体时间复杂度为 $O((nmlogm)^{\frac{2}{3}})$ 。

$\\$ $\\$

输出答案的时候不要忘记除 $2$ 。

参考代码

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define vv vector
#define ll int


struct comp{
    double x,y;
    comp(double _x=0.0,double _y=0.0){x=_x,y=_y;}
    comp operator-(const comp&b)const{return comp(x-b.x,y-b.y);}
    comp operator+(const comp&b)const{return comp(x+b.x,y+b.y);}
    comp operator*(const comp&b)const{return comp(x*b.x-y*b.y,x*b.y+y*b.x);}
};
const double PI=acos(-1.0); 
void change(vector<comp>&f,ll len){
    for(ll i=1,j=len/2,k;i<len-1;++i){
        if(i<j)swap(f[i],f[j]);
        k=len/2;
        while(j>=k)j-=k,k/=2;
        if(j<k)j+=k;
    }
}
void fft(vector<comp>&f,ll len,ll op) {
    change(f,len);
    for(ll i=2;i<=len;i<<=1){
        comp wn(cos(2*PI/i),sin(op*2*PI/i));
        for(ll j=0;j<len;j+=i){
            comp w(1,0);
            for(ll k=j;k<j+i/2;++k){
                comp u=f[k],t=w*f[k+i/2];
                f[k]=u+t,f[k+i/2]=u-t;
                w=w*wn;
            }
        }
    }
    if(op==-1)
        for(ll i=0;i<len;++i)
            f[i].x/=len;
}
void polymul(vector<ll> &f){
    ll len=1,deg=2*f.size()+1;
    while(len<deg)len<<=1;
    vector<comp> a;
    f.resize(len),a.resize(len);
    for(ll i=0;i<len;++i)a[i]={1.0*f[i],0.0};
    fft(a,len,1);
    for(ll i=0;i<len;++i)a[i]=a[i]*a[i];
    fft(a,len,-1);
    for(ll i=0;i<len;++i)f[i]=(ll)(a[i].x+0.5);
    f.resize(deg);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    ll n,m,q;cin>>n>>m>>q;
    ll B=pow(m/__lg(m),0.25);

    vv<ll> c(m+1);
    for(ll i=1;i<=n;++i){
        ll x;cin>>x;
        ++c[x];
    }

    vv<ll> ans(2*m+1);

    //<B
    for(ll i=1;i<=B;++i){
        vv<ll> a(m+1);
        for(ll j=1;j<=m;++j){
            if(c[j]>=i)a[j]=1;
        }
        polymul(a);
        for(ll j=1;j<=2*m;++j){
            ans[j]+=a[j];
        }
    }

    //>B
    vv<ll> b;
    for(ll i=1;i<=m;++i){
        if(c[i]>B)b.push_back(i);
    }
    for(ll i:b){
        for(ll j:b)
            ans[i+j]+=min(c[i],c[j])-B;
    }

    for(ll i=1;i<=2*m;++i){
        ans[i]/=2;
    }
    while(q--){
        ll x;cin>>x;
        cout<<ans[x]<<"\n";
    }

    return 0;
}

题外话

$idea$ 来自 $thisislike\_fan$ ；

第一眼看上去就感觉很毒瘤的复杂度；

C. 一日之计在于晨

知识点

扩展欧几里得（ $\mathrm{exgcd}$ ）。

大致思路

题意等价于求出绝对值最小的 $x$ 使得 $(t - 1 ax)\%m$ 的值最小；

令 $t-1 ax my=ans$ ，问题等价于求一组 $x,y$ 使得 $ans$ 最小；

$\\$ $\\$

移项得 $ax my=ans-t 1$ ，根据裴蜀定理可知，若有解，则必须满足 $gcd(a,m)|(ax my)$ ；

那么就有 $(ans-t 1)\%gcd(a,m)=0$ ；

即 $ans\%gcd(a,m)=(t-1)\%gcd(a,m)$ ，那么有 $ans=(t-1)\%gcd(a,m) k*gcd(a,m)$ ；

$\\$ $\\$

显然当 $k=0$ 时， $ans$ 取得最小值，此时有 $ans=(t-1)\%gcd(a,m)$ ；

将 $ans$ 带入 $ax my=ans-t 1$ 可得 $ax my=(t-1)\%gcd(a,m)-t 1$ ；

$\\$ $\\$

用 $\rm{exgcd}$ 求解出最小的正整数解和最大的负整数解即可。

参考代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>

#define ll long long
#define int long long
using namespace std;

int exgcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

void solve(){
  	int t, a, m;
  	cin >> t >> a >> m;
    int x, y;
    int d = exgcd(a, m, x, y); // ax + my = d
    t = t - 1;
    t = ((t % d - t) % m + m) % m;// ax + my = t % d - t 
  	x = x * t / d;
  	x = (x % (m / d) + (m / d)) % (m / d);
	cout << min(x, m / d - x) << '\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T = 1; 
    cin >> T;
    while(T--){
        solve();
    }
}

D. qfl_zzz的mex

知识点：

双指针、队列。

大致思路：

先考虑写一个暴力的做法，枚举左端点 $l$ ，然后从 $l$ 的位置开始往右边枚举右端点 $r$ ，在这个过程中可以动态地维护 $mex$ 的值，然后累加答案，时间复杂度 $O(n^2)$ ；

$\\$ $\\$

注意到有这样一个性质：若区间 $[l,r]$ 的 $mex$ 为 $d$ ，则 $0,1,2,...,d-1$ 必定出现在区间 $[l,r]$ 中；

设区间元素和为 $sum$ ，则有 $\frac{(d-1)*d}2\leq{sum}\leq{x}$ ，于是有 $d\leq{\sqrt{2x}}$ ；

至此，不难发现，在枚举右端点 $r$ 的过程中， $mex$ 至多能改变 $\sqrt{2x}$ 次，因此，我们只需要关注 $[0,\sqrt{2x}]$ 在左端点 $l$ 之后的首次出现位置；

$\\$ $\\$

对于区间和小于 $x$ 的限制，可以使用双指针来解决；

对于 $[0,\sqrt{2x}]$ 的首次出现位置，可以在双指针的过程中用队列动态地维护；

对于每个左端点 $l$ ，通过 $O(\sqrt{x})$ 的复杂度枚举 $mex$ 值发生变化的右端点 $r$ 的位置，然后统计答案即可；

时间复杂度 $O(n\sqrt{x})$ 。

参考代码；

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define vv vector
#define ll long long

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    ll n,x;cin>>n>>x;
    
    vv<ll> a(n+1);
    for(ll i=1;i<=n;++i)cin>>a[i];

    ll m=sqrt(2*x)+5,ans=0,sum=0;
    vv<queue<ll>> q(m+1);

    for(ll l=1,r=0;l<=n;++l){
        while(l>r||(r<=n&&sum<=x)){
            if(++r>n)break;
            sum+=a[r];
            if(a[r]<=m){
                q[a[r]].push(r);
            }
        }

        ll pre=l;
        for(ll i=0;i<=m;++i){
            if(q[i].size()==0){
                if(pre<r)ans+=i*(r-pre);
                break;
            }
            ll next=q[i].front();
            if(next>pre){
                ans+=i*(next-pre);
                pre=next;
            }
        }

        sum-=a[l];
        if(a[l]<=m){
            q[a[l]].pop();
        }
    }

    cout<<ans<<"\n";

    return 0;
}

题外话

卡不满 $O(nx^{\frac{1}{2}}log(x^{\frac{1}{2}}))$ 的做法，在验题时还被 $O(nx^{\frac{1}{4}}log(x^{\frac{1}{4}}))$ 的做法爆了标程（悲

E. 数星星

知识点

$dfs$ 序，前缀 $max$ 。

大致思路

要判断一个子树内是否存在相同的颜色，我们可以很套路地用 $dfs$ 序将子树表示为区间；

于是问题就变为了：给定 $n$ 个区间，判断区间内是否存在相同颜色的两个点；

$\\$ $\\$

我们可以按照 $dfs$ 序从 $1$ 到 $n$ 的顺序枚举每个点，同时维护下面两个值：

$id_i$ 表示 $dfs$ 序为 $i$ 的点对应的颜色的上一次出现位置对应的 $dfs$ 序；

$mx_i$ 表示 $dfs$ 序在 $[1,i]$ 中的所有点的最大的上一次出现位置对应的 $dfs$ 序，即 $mx_i=max_{j=1}^{i}id_j$ ；

$\\$ $\\$

令 $[l,r]$ 表示某棵子树对应的 $dfs$ 序区间，若要判断区间内是否存在相同的颜色，即判断区间内是否存在一个位置 $i$ 使得 $id_i\geq l$ ；

由于当 $i<l$ 时，显然有 $id_i<l$ ，所以，判断区间 $[l,r]$ 等价于判断前缀 $[1,r]$ ；

$\\$ $\\$

至此，对于每一个子树对应的区间 $[l,r]$ ，我们直接判断是否满足 $mx_r<l$ 即可；

对于 $mx_i$ 的值，我们可以在 $dfs$ 的过程中动态地维护；

时间复杂度 $O(n)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

int n,dfn,ans,mx;
vector<int> a,id;
vector<vector<int>> e;
void dfs(int u){
    int l=++dfn;
    mx=max(mx,id[a[u]]);
    id[a[u]]=dfn;
    for(int v:e[u])dfs(v);
    int r=dfn;
    if(mx<l)++ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    int n;cin>>n;
    a.resize(n+1);
    id.resize(n+1);
    e.resize(n+1);
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=2;i<=n;++i){
        int x;cin>>x;
        e[x].push_back(i);
    }
    dfs(1);
    cout<<ans<<"\n";

    return 0;
}

F. 最长严格上升子序列和

知识点

数位 $dp$ ，最长上升子序列。

大致思路

考虑数位 $dp$ 。

令 $dp_{zero , limit,cur , stu}$ ：表示当前枚举的前缀是否全为前导 $0$ ，是否有上界限制，此时枚举第 $cur$ 位，前缀数码的状态记录为 $stu$ 的所有可表达数字 $x$ 的 $f(x)$ 之和；

$\\$ $\\$

下面探讨 $stu$ 的定义方式：

定义一个长度为 $10$ 的数组来压缩已遍历的前缀信息（长度只需要定义为 $10$ ，因为只有 $9$ 种数字的情况下，最长严格上升子序列的长度至多为 $10$ ）；

定义 $Arrays_i$ ：表示严格上升子序列的长度为 $i$ 的最小尾部元素的值;

$\\$ $\\$

数组满足以下形式：

①：数组总存在前缀严格连续上升的。数组后缀总是全为 $10$ ；

②：总体上数组的形式为，严格严格且连续上升的前缀全 $10$ 的后缀；

容易看出该数组一共有 $1024$ 种形式，证明如下：

①：不妨枚举前缀一共有多少种数字，对于 $i$ 种数字前缀，容易看出一共有 $C_{10}^{i}$ 种情况；

②：集合根据 $i = 0 ..... 10$ 得到一个划分;

③：因此数组的形式总数为 $\sum _{i = 0} ^{10} C_{10}^{i} = 2^{10} = 1024$ ；

$\\$ $\\$

基于上述观察，使用的一些trick(技巧)

①：通过 $11$ 进制可以将上述数组状态压缩表示， $10$ 用来表示无穷大；

②：由于压缩的状态是离散的，考虑用 $map$ 存储转移；

$\\$ $\\$

状态转移：

①：综合考虑当前 $zero$ ， $limit$ 的标记情况确定可枚举数字的范围后，枚举当前数位上放置的数字 $dig$ ；

②：更新 $Array_i$ 的步骤：

-对于 $1 \le i \le 9$ 从后往前遍历 $i$ ：如果 $Array_{i-1} < d_{i}$ 则 $Array_i = min(Array_i , dig)$ ；否则，结束遍历；

-对于 $i = 0$ , $Array_0 = min(Array_0 , i)$

$\\$ $\\$

时间、空间复杂度分析：

空间复杂度：

$S＝2\times2\times100\times 1024 = 4\times 10^5$ ，参照 $dp[2][2][100][stu]$ ;

时间复杂度：

①： $map$ 查询，总查询次数约为空间总数，每次查询的话费为 $10$ ； ②：转移花费，计算每个状态的花费为 $100$ ； ③：最终规模可以控制在 $4\times 10^7$ ；

参考代码

#include<bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()

const int mod = (int)1E9 + 7;
long long p11[15];
void init() {
    p11[0] = 1;
    for (int i = 1; i < 11; i++) {
        p11[i] = p11[i - 1] * 11LL;
    }
}

void add(int& x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

array<int, 10> number_array(long long x) {
    array<int, 10> res;
    // long long tx = x;
    for (int i = 0; i < 10; i++) {
        res[i] = x % 11;
        x /= 11;
    }

    return res;
}

long long array_number(array<int, 10> dig) {
    long long res = 0;
    for (int i = 0; i < 10; i++) {
        res += dig[i] * p11[i];
    }
    for (int i = 1; i < 10; i++) {
        if (dig[i] < dig[i - 1]) {
            cout << res << "\n";
        }
    }
    return res;
}

vector<int> d;
map<long long, int> f[2][2][110];
int dfs(int zero, int limit, int cur, long long pre) {
    if (cur == -1) {
        return pre / p11[9];
    }
    if (f[zero][limit][cur].count(pre)) {
        return f[zero][limit][cur][pre];
    }
    int& res = f[zero][limit][cur][pre] = 0;
    int mx = limit ? d[cur] : 9;
    array<int, 10> t;
    for (int i = 0; i <= mx; i++) {
        t = number_array(pre);

        bool flag = true;
        if (i == 0) {
            if (t[i] == 1) flag = false;
            else if (zero == false) t[0] = 1;
        }
        else {
            if (t[i] == t[i - 1] + 1) flag = false;
            else t[i]++;
        }
        if (flag) {
            for (int j = i + 1; j <= 9 && t[j] < t[i]; j++) {
                t[j] = t[i];
            }
        }
        add(res, dfs(zero & (i == 0), (i == mx) & limit, cur - 1, array_number(t)));
    }
    return res;
}

long long solve(string x) {
    for (auto s : x) {
        d.push_back(s - '0');
    }
    reverse(all(d));
    return dfs(true, true, d.size() - 1, 0);
}

signed main() {
    init();
    string r;
    cin >> r;
    cout << solve(r) << "\n";
}

G. 能赢吗？会赢的！

知识点

二分。

大致思路

如果能力值 $x$ 能够战胜所有 boss，那么显然对于 $y>x$ 的能力值 $y$ 也能够战胜所有 boss；

答案具有单调性，二分答案即可；

参考代码

#include<iostream>
#include<vector>
using namespace std;
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<long long> a(n + 2);
     
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    auto check = [&](long long x){
        auto b = a; 
        for(int i = 1; i <= n; i++){
            if(x <= b[i]){
                return false;
            }
            x += a[i] / 2;
            b[i + 1] += (a[i] + 1) / 2;
        }
        return true;
    };
 
    long long low = 1 , high = 1E9 + 10;
    while(low < high){
        long long mid = (low + high) / 2;
        if(check(mid)){
            high = mid;
        }else{
            low = mid + 1;
        }
    }
    cout << low << "\n";
}

H. NING-NING-chatgpt

知识点

模拟。

大致思路

签到题，模拟即可，注意对空格的处理。

参考代码

#include <bits/stdc++.h>
using namespace std;

char p[26]={'4','6','c','d','3','f','9','h','i','j','k','1','m','n','0','p','q','r','5','7','u','v','w','x','y','2'};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    map<char,char> mp;
    for(int i=0;i<26;++i)mp[p[i]]=char(i+'a');

    string s;
    getline(cin,s);

    for(int i=0;i<s.size();++i)
        if('0'<=s[i]&&s[i]<='9')cout<<mp[s[i]];
        else cout<<s[i];

    return 0;
}

I. 不是莫比乌斯反演，不是欧拉反演

知识点

容斥，数论，组合数学， $dp$ 。

大致思路

设 $dp_i$ 为满足 $gcd(f(T),n)=i$ 的子集个数；

则答案 $ans=\sum_{i|n}i\times dp_i$ ；

$\\$ $\\$

考虑怎么去求每一个 $dp_i$ 的值，不难想到一个暴力的做法；

用 $x$ 暴力枚举 $[l,r]$ 中的每一个数字，用 $i$ 枚举 $gcd(f(T),n)$ 的值，对于每一个 $x$ 都有两种选择：

①：不考虑加入子集，则有转移方程 $dp_i=dp_i$ ；

②：考虑将其加入子集，则有转移方程 $dp_{gcd(i\cdot x,n)} =dp_i$ ；

至此，我们有一个 $O(r\cdot d(n))$ 的一个做法，其中 $d(n)$ 表示 $n$ 的因子个数；

$\\$ $\\$

考虑优化，不难发现有这样一个性质: $gcd(i\cdot x,n)=gcd(i\cdot gcd(x,n),n)$ ；

因此，若存在两个不同的整数 $x,y$ 满足 $gcd(x,n)=gcd(y,n)$ ，我们显然可以在 $dp$ 转移的时候，将 $x,y$ 作为同一种数字去考虑；

注意到 $gcd(x,n)$ 的值至多只有 $d(n)$ 种，这启发我们可以通过将所有 $x\in [l,r]$ 按照 $gcd(x,n)$ 的值进行分类，来优化 $dp$ 转移的过程中枚举 $x$ 所耗费的复杂度；

进一步地，设 $cnt_i$ 表示 $[l,r]$ 中满足 $gcd(x,n)=i$ 的 $x$ 的个数，可以通过枚举倍数和容斥来计算所有的 $cnt_i$ ，即 $cnt_i=\lfloor \frac{r}{i}\rfloor - \lfloor \frac{l-1}{i}\rfloor -\sum_{i|j,i<j}cnt_j$ ；

$\\$ $\\$

接下来，考虑怎么转移：

用 $i$ 枚举 $gcd(x,n)$ 的值，用 $j$ 枚举 $gcd(f(T),n)$ 的值，用 $k$ 枚举选择多少个 $i$ ，则对于每一个 $i^k$ 都有两种选择：

①：不考虑将 $i^k$ 加入子集，则有转移方程 $dp_j=dp_j$ ；

②：考虑将 $i^k$ 加入子集，则有转移方程 $dp_{gcd(j\cdot i^k,n)} =C_{cnt_i}^{k}\cdot dp_j$ ；

$\sum cnt_i$ 的数量级是 $O(r)$ 的，此时的时间复杂度仍然是 $O(r\cdot d(n))$ ，不足以通过本题；

$\\$ $\\$

注意到，若 $gcd(j\cdot i^{k},n)<gcd(j\cdot i^{k 1},n)$ ，则有 $2\cdot gcd(j\cdot i^{k},n)\leq gcd(j\cdot i^{k 1},n)$ ，进而有 $\frac{gcd(j\cdot i^{k 1},n)}{gcd(j\cdot i^{k},n)}\geq 2$ ；

也就是说，在从小到大枚举 $k$ 的过程中 $gcd(j\cdot i^k,n)$ 的值至多会连续变化 $log(n)$ 次，设 $m=min(cnt_i,log(n))$ ，则枚举 $k$ 的复杂度降为了 $O(m)$ ；

而对于 $k>m$ 的部分，则有转移 $dp_{gcd(j\cdot i^m,n)} =(2^{cnt_i}-\sum_{t=0}^{m}C_{cnt_i}^{t})\cdot dp_j$ ，由于 $cnt_i$ 较大，记得递推预处理组合数；

至此，总体时间复杂度 $O(d(n)^2logn)$ 。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod=1e9+7;
ll qpow(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1)res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cin.tie(0);

    ll l,r,n;cin>>l>>r>>n;

    vector<ll> d;
    for(ll i=1;i<=n;++i){
        if(n%i==0)d.push_back(i);
    }

    vector<ll> cnt(d.size());
    for(ll i=d.size()-1;i>=0;--i){
        cnt[i]=r/d[i]-(l-1)/d[i];
        for(ll j=i+1;j<d.size();++j){
            if(d[j]%d[i]==0)cnt[i]-=cnt[j];
        }
    }

    vector<ll> inv(__lg(n)+1);
    for(ll i=1;i<=__lg(n);++i){
        inv[i]=qpow(i,mod-2);
    }

    vector<ll> id(n+1);
    for(ll i=0;i<d.size();++i){
        id[d[i]]=i;
    }

    vector<ll> dp(d.size());
    dp[0]=1;
    for(ll i=0;i<d.size();++i){

        ll m=min(cnt[i],__lg(n));
        vector<ll> c(m+1,1);
        for(ll j=1;j<=m;++j){
            c[j]=c[j-1]*inv[j]%mod*(cnt[i]-j+1)%mod;
        }

        ll tot=qpow(2,cnt[i]);
        vector<ll> f(d.size());
        for(ll j=0;j<d.size();++j){
            ll x=d[j],rest=tot;
            for(ll k=0;k<=m;++k){
                (f[id[x]]+=c[k]*dp[j]%mod)%=mod;
                rest=(rest-c[k]+mod)%mod;
                x=__gcd(x*d[i],n);
            }
            (f[id[x]]+=rest*dp[j]%mod)%=mod;
        }
        dp=f;

    }

    ll ans=0;
    for(ll i=0;i<d.size();++i){
        ans=(ans+dp[i]*d[i]%mod)%mod;
    }
    cout<<ans<<"\n";

    return 0;
}

题外话

$idea$ 来自 $thisislike\_fan$ ；

被他推荐写这题的时候，红温了快三个小时（悲

J. 矩阵最大路径与

知识点

贪心，拆位，搜索。

大致思路

定义最后的答案为 $ans$ ，对 $ans$ 关注其二进制，我们可以很套路地拆位，然后从高到低确定每一位：

①：对于第 $k$ 位，如果存在一条合法路径使得路径上所有的数字 $((a_{i,j}>>k)\ \$ 。那么 $ans$ 在第 $k$ 位上的值也必须为 $1$ ；

②：对于第 $k-1$ 位，在满足第 $k$ 位最优的前提下，继续尝试寻找一条合法路径使得路径上所有的数字 $((a_{i,j}>>(k-1))\ \$ ；

③：若找不到，则将所有满足 $((a_{i,j}>>(k-1))\ \$ 的合法路径作为下一位需要考虑的路径；

④：按照从高到低的顺序依次处理每一个二进制位即可。

参考代码

#include<vector>
#include<iostream>
#include<array>
#include<queue>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    vector<vector<int>> vis(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    int ans = 0;
    for (int i = 29; i >= 0; i--) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                vis[i][j] = 0;
            }
        int tag = ans + (1 << i);
        queue<array<int, 2>> que;
        if ((a[1][1] & tag) == tag) {
            que.push({ 1 , 1 });
            vis[1][1] = 1;
        }

        int dx[] = { 0 , 0 , 1 , -1 };
        int dy[] = { 1 , -1 , 0 , 0 };

        while (que.size()) {
            array<int, 2> t = que.front();
            int x = t[0], y = t[1];

            que.pop();
            for (int i = 0; i < 4; i++) {
                int tx = x + dx[i];
                int ty = y + dy[i];

                bool flag = (tx >= 1) && (tx <= n) && (ty >= 1) && (ty <= m) && (vis[tx][ty] == 0);
                if (flag) {
                    if ((a[tx][ty] & tag) == tag) {
                        vis[tx][ty] = 1;
                        que.push({ tx , ty });
                    }
                    else vis[tx][ty] = 2;
                }
            }
            if (vis[n][m] == 1) {
                ans |= (1 << i);
            }
        }
    }
    cout << ans << "\n";
}

K. gzhu is all you need！

知识点

模拟。

大致思路

从头到尾枚举一遍 $n$ 个城市，每到达一个城市，先判断一下力量值 $x$ 是否大于 $0$ ；

若是，就消耗一点力量值，然后无代价地通关当前城市并忽略掉当前城市的字母；

否则，令代价 $ans=ans 1$ 并将当前城市的字母收集起来，收集之后判断一下当前是否已经收集了 'g' 'z' 'h' 'u' 这四个字母；

若已集齐四个字母，则更新一下力量值 $x$ ，然后将所有收集到的字母丢弃；

按照以上顺序逐个处理每个城市即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    int n;cin>>n;
    string a;cin>>a;a=" "+a;

    int ans=0,x=0,sum=0;
    map<char,int> cnt;
    for(int i=1;i<=n;++i){
        if(x>0)--x;
        else{
            ++ans;
            if(a[i]=='g'||a[i]=='z'||a[i]=='h'||a[i]=='u'){
                ++cnt[a[i]],++sum;
            }
            if(cnt.size()==4){
                x=sum,cnt.clear(),sum=0;
            }
        }
    }

    cout<<ans<<"\n";

    return 0;
}

L.qfl_zzz的树上距离

知识点：

最近公共祖先（ $lca$ ），调和级数。

大致思路：

我们可以先假设，对于所有的 $u,v$ 都有 $dist(u,v)\leq{u\times v}$ ，这样便可以先计算出来 $\sum dist(u,v)$ 的值，然后再减去 $dist(u,v)>{u\times v}$ 时的贡献，即是正确的答案；

对于 $\sum dist(u,v)$ 的计算是比较容易的：我们可以单独地考虑每一条边的对答案的贡献，即将 $(x,y)$ 这条边断开后，点 $x$ 所在的连通块的大小与点 $y$ 所在连通块的大小的乘积（记得再乘 $2$ ）；

$\\$ $\\$

接下来考虑怎么减去 $dist(u,v)>{u\times v}$ 时的贡献；

注意到，对于任意两点 $u,v$ 都有 $dist(u,v)<n$ ，若 $u,v$ 还满足 $u\times v<dist(u,v)$ ，则必然有 $u\times v<n$ ；

至此，我们可以枚举点 $u$ ，然后再枚举满足 $u\times v<n$ 条件的点 $v$ ，以此来得到 $u\times v$ 和 $dist(u,v)$ 的值，若满足 $dist(u,v)>{u\times v}$ ，则令答案 $ans=ans u\times v-dist(u,v)$ ；

$\\$ $\\$

枚举 $u,v$ 的时间复杂度 $O(nlogn)$ ，可以通过调和级数来证明;

对于某一对 $u,v$ 求 $dist(u,v)$ 则可以通过 $O(logn)$ 的时间复杂度求最近公共祖先（ $lca$ ）以及预处理结点深度来计算；

总体时间复杂度 $O(nlog^2n)$ 。

参考代码：

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    int n;cin>>n;

    vector<vector<int>> e(n+1);

    for(int i=1;i<=n-1;++i){
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    long long ans=0;

    vector<int> sz(n+1),son(n+1),top(n+1),fa(n+1),dep(n+1);

    function<void(int,int)> dfs1=[&](int u,int pre){
        sz[u]=1;
        fa[u]=pre;
        dep[u]=dep[pre]+1;
        int mx=-1;
        for(int v:e[u]){
            if(v==pre)continue;
            dfs1(v,u);
            ans+=(long long)2*sz[v]*(n-sz[v]);
            sz[u]+=sz[v];
            if(mx<sz[v]){
                son[u]=v;
                mx=sz[v];
            }
        }
    };
    dfs1(1,0);

    function<void(int,int)> dfs2=[&](int u,int tp){
        top[u]=tp;
        if(!son[u])return;
        dfs2(son[u],tp);
        for(int v:e[u]){
            if(v==fa[u]||v==son[u])continue;
            dfs2(v,v);
        }
    };
    dfs2(1,1);

    auto lca=[&](int u,int v){
        while(top[u]!=top[v]){
            if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
            else v=fa[top[v]];
        }
        return dep[u]>dep[v]?v:u;
    };

    auto dist=[&](int u,int v){
        return dep[u]+dep[v]-2*dep[lca(u,v)];
    };

    for(int i=1;i<=n;++i)
        for(int j=1;i*j<=n;++j){
            int dis=dist(i,j);
            if(i*j<dis)ans+=i*j-dis;
        }

    cout<<ans<<"\n";

    return 0;
}

题外话

本题原本是 $\sum\sum min(u v,dist(u,v))$ 版本的启发式合并+树状数组，后来验题人反应整场题目有点偏难，于是就换成了 $u\times v$ 版本的了（悲

M. 计算几何

知识点

构造。

大致思路

给出一个比较显然的构造思路：

将点的坐标存入 $pair$ ，然后排序，先比较第一维 $first$ ，如果相等进而比较第二维 $second$ ；

$\\$ $\\$

基于上述的偏序关系，采取以下连点策略：

将排好序之后的点，两两配对相连，即对于每一个奇数 $i<n$ ，将点 $i$ 与点 $i 1$ 相连；

这种方法保证了线段的数量为 $\left \lfloor \frac{n}{2} \right \rfloor$ ，且任意两条线段之间是不会相交。

$\\$ $\\$

证明如下：

可以通过反证法证明：

①：假设上述方式中，存在情况 $AB$ 与 $CD$ 相交的情况。

②：对点 $A,B,C,D$ 按照上述规则进行排序。

③：不妨假设排序后， $A$ 点处于第一位。

关注 $A,B$ 之间的位置， $C,D$ 两点中必定存在一点 $M$ ，满足 $A.x \le M.x \le B.x$ ；

如果 $A.x = B.x = M.x$ ，亦会存在 $A.y \le M.y \le C.y$ ；

否则，两线段不会相交。

同时这种现象和我们的构造策略相矛盾，因为在上述策略中 $A$ 应该连接 $M$ ，而不是 $B$ 。

参考代码

#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
using namespace std;

#define all(x) (x).begin(),(x).end()

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;

	vector<array<int , 3>> arr;
	for(int i = 0; i < n; i++){
		int x , y ;
		cin >> x >> y;
		arr.push_back({y , x , i + 1});
	}
	sort(all(arr));
	cout << n / 2 << "\n";
	for(int i = 1; i < n; i += 2){
		cout << arr[i][2] << " " << arr[i - 1][2] << "\n";
	}
}

第十八届广州大学ACM程序设计竞赛题解

A. 字符画

知识点

大致思路

参考代码

B. A+B Problem

知识点

大致思路

参考代码

题外话

C. 一日之计在于晨

知识点

大致思路

参考代码

D. qfl_zzz的mex

知识点：

大致思路：

参考代码；

题外话

E. 数星星

知识点

大致思路

参考代码

F. 最长严格上升子序列和

知识点

大致思路

参考代码

G. 能赢吗？会赢的！

知识点

大致思路

参考代码

H. NING-NING-chatgpt

知识点

大致思路

参考代码

I. 不是莫比乌斯反演，不是欧拉反演

知识点

大致思路

参考代码

题外话

J. 矩阵最大路径与

知识点

大致思路

参考代码

K. gzhu is all you need！

知识点

大致思路

参考代码

L.qfl_zzz的树上距离

知识点：

大致思路：

参考代码：

题外话

M. 计算几何

知识点

大致思路

参考代码