致謝名單

感謝三位學長林煜傑、吳威錡、霍朝元提供各種好題目還有協助出題，沒有你們這個比賽不會辦成。

感謝tester abc864197532對於題敘跟難度的寶貴意見。

感謝幹部陳連恩協助測題並提供神奇唬爛想法。

各題AC人數

點這裡展開

A	B	C	D	E	F	G
18	16	3	11	11	0	0

A. A letter for you

Idea: niter
Task Prepration: niter
Statement Writer: niter

Tags（點此展開）

none

實體組首殺：snorlax_snorlax
線上組首殺：raypeng1729

題目給的數列為：

$[87,48,16,6,21,70,40]$

重排表格之後（數字

$83$用不到），直接依序輸出就好了。

數字	字串
87	Enjoy
48	Your
16	Pizza
6	And
21	Have
70	Fun
40	!

輸出內容：EnjoyYourPizzaAndHaveFun!

B. Test File Generator

Idea: niter
Task Prepration: niter
Statement Writer: niter

Tags（點此展開）

bitmask, greedy

實體組首殺：sakinu_ruigao_9487
線上組首殺：raypeng1729

因為相同數字的OR值等於自己，所以取

$2$個重複的數字時，就會有

$1$個沒有被取到，同理，取

$x$個重複的數字（其他均不重複）時，就會有

$x-1$個沒有被取到，也就相當於取了

$n-x+1$種數字。

結論就是：此題等價於問你從集合中取一個非空子集合的OR值的最大及最小值。

記得開IO優化，沒開而吃TLE不負責。

Subtask 1

$O(2^n)$枚舉所有非空子集合，然後取最大最小即可。

部分分解(niter)

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
using namespace std;

int a[200005];
int ans, ans_min;
int n;

void recursive_solve(int ind, int now, bool have_one){
    if(ind == n){
        ans = max(ans, now);
        if(have_one) ans_min = min(ans_min, now);
        return;
    }
    recursive_solve(ind + 1, now | a[ind], true);
    recursive_solve(ind + 1, now, have_one);
}

void solve(){
    ans_min = (1 << 30);
    ans = 0;
    loop(i,0,n){
        cin >> a[i];
    }
    recursive_solve(0, 0, false);
    cout << ans << ' ' << ans_min << '\n';
}

int main(){
    int t;
    cin >> t;
    loop(i,0,t){
        cin >> n;
        solve();
    }
}

Subtask 2

觀察到一堆數字OR起來只會變大不會變小，所以最小值即為所有數字中最小的數、最大值即為全部都OR起來所得到的值。

官解(niter)

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

void solve(){
    int n;
    cin >> n;
    int ans_min = (1 << 30), ans_max = 0, inp;
    for(int i = 0; i < n; i++){
        cin >> inp;
        ans_min = min(ans_min, inp);
        ans_max |= inp;
    }
    cout << ans_max << " " << ans_min << "\n";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        solve();
    }
}

C. 王老先生有快遞

Idea: wcwu
Task Prepration: wcwu
Statement Writer: wcwu

Tags（點此展開）

binary search, math

實體組首殺：學長帶我飛
線上組首殺：raypeng1729

Subtask 1

可以用手畫。

時間複雜度：

$O(1)$

Subtask 2

預期解

注意到所求的

$k$ 值最大只會是

$\frac{n\cdot (n+1)}{2}$，即將全部正方形放在同一個邊上，以下我們令

$C=\frac{n\cdot (n+1)}{2}$。

由於我們填的正方形長度嚴格遞減，在將正方形填入土地時若遇到需轉彎的情況，可以發現新填入的正方形絕不會與轉彎前的邊上填入的正方形重疊。

令

$n^{\prime }$ 為第一個其中一邊與土地上方的邊貼合的正方形植株之邊長，因

$n\ne 1$ 時必有

$k\ge n+(n-1)+...\ge n+n^{\prime }$，所以我們有

$n+n^{\prime }\le k$，所以可以觀察到任兩個與土地貼合的邊互相平行的正方形植株，永遠不會發生重疊的情況。

由以上兩個結論，我們知道對於每一個邊填入正方形時，只需考慮同一水平方向的空間是否足夠即可，換句話說我們只需對每一個邊檢查其長度最多能填幾個正方形的邊長。

對於一個給定的

$k$ 值，我們可以用

$O(n)$ 跑過所有正方形的邊長，如果目前即將填入土地的邊長超過

$k$ 就轉彎。轉彎三次後，如果最後剩餘未填的邊長總和超過

$k-n$，則此

$k$ 值不存在一種滿足條件填入正方形的方法。

在此子題中，我們可以從

$1$ 到

$C$ 枚舉

$k$ 值，然後找最小合法的

$k$ 即可。

時間複雜度：

$O(nC)$

非預期解

又或者你可以暴力枚舉轉彎時正方形的長度，再計算四個邊長的最大值即可。

時間複雜度：

$O(n^3)$

預期部分分解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(ll i=0;i<n;i++)
void solve() {
    ll n;
    cin>>n;
    if(n==1) {
        cout<<"1\n";
        return;
    }
    ll ans=1, cur, now;
    for(ll i=n*(n+1)/2;i>=1;i--) {
        ll k=i;
        cur=n, now=n;
        while(now && cur<=k) {
            now--;
            cur+=now;
        }
        if(cur>k) {cur=now+1; now++;}
        while(now && cur<=k) {
            now--;
            cur+=now;
        }
        if(cur>k) {cur=now+1; now++;}
        while(now && cur<=k) {
            now--;
            cur+=now;
        }
        if(cur>k) {cur=now+1; now++;}
        if(now==0) continue;
        if((cur+1)*cur/2+n>k) {
            ans=k+1;
            break;
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    int T=1;
    cin>>T;
    while(T--) solve();
}

Subtask 3

觀察到如果

$k$ 是合法的，那麼

$k^{\prime }=k+1$ 也是合法的，所以我們只需要對

$k$ 值做二分搜即可。

時間複雜度：

$O(n\log C)$

Subtask 4

因為

${\displaystyle \sum _{i=l}^{r}i=\frac{(l+r)\times (r-l+1)}{2}}$，

所以可以用二分搜來計算填幾個正方形之後要轉彎。因此僅需

$O(\log n)$ 的時間來跑過正方形的邊長。

時間複雜度：

$O(T\log n\log C)$

官解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(ll i=0;i<n;i++)

ll binary_search(ll len, ll now) {
    ll l=1, r=now;
    while(l<r) {
        ll mid=(l+r)>>1;
        if((now+mid)*(now-mid+1)/2<=len) {
            r=mid;
        }
        else l=mid+1;
    }
    return l;
}

void solve() {
    ll n;
    cin>>n;
    if(n==1) {
        cout<<"1\n";
        return;
    }
    ll l=1, r=(ll)500000000500000000;
    while(l<r) {
        ll mid=(l+r)>>1;
        ll now=n;
        now=binary_search(mid, now);
        now=binary_search(mid, now);
        now=binary_search(mid, now);
        if((1+now)*now/2<=mid-n) r=mid;
        else l=mid+1;
    }
    cout<<l<<"\n";
}

signed main() {
    int T=1;
    cin>>T;
    while(T--) solve();
}

D. 學科能力測驗

Idea: wcwu
Task Prepration: wcwu
Statement Writer: wcwu

Tags（點此展開）

graph, dfs

實體組首殺：electromagnetism
線上組首殺：raypeng1729

Subtask 1

暴力枚舉群組內詢問成績的順序，然後對所有順序找出所求的最小值即可。

時間複雜度：

$O(n!)$

Subtask 2

把每個人視為一個點，如果任兩者之間有其中一科成績相同，則在兩點之間建一條邊，代表彼此可以問到彼此的分數。

可以用兩個迴圈跑過所有的點，藉此建出所有點之間的邊，接著透過dfs或並查集來找出LCB無法走到哪些點即可。

時間複雜度：

$O(n^2)$

Subtask 3

如果把一個人都視為點的話，光建邊就至少需要花

$O(n^2)$ 的複雜度了！所以我們要換個角度思考，如果我們改對分數建圖呢？把每個分數視為一個點，而對於每個點去儲存有哪些人在這個點上，即在這個科目有這個級分，這樣一來我們只需建

$90$ 個點即可。

接著對於同一個點上的所有人，我們只需建一條鍊來讓他們彼此是連通的即可，接下來就可以透過一次 dfs 或並查集來完成這題。

時間複雜度：

$O(n)$

DFS官解(wcwu)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int MOD1=1e9+7;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(ll i=0;i<n;i++)

const int N=2e5+5;
vector<ll> G[N];
bool vis[N];
vector<ll> score[6][15];
void dfs(ll u) {
    for(auto v:G[u]) {
        if(!vis[v]) {
            vis[v]=1;
            dfs(v);
        }
    }
}
void solve() {
    ll n;
    cin>>n;
    rep(i, n) {
        G[i].clear();
        vis[i]=0;
    }
    rep(i, 6) rep(j, 15) score[i][j].clear();
    rep(i, n) {
        rep(j, 6) {
            ll x;
            cin>>x;
            score[j][x-1].pb(i);
        }
    }
    rep(i, 6) {
        rep(j, 15) {
            if(score[i][j].empty()) continue;
            ll now=score[i][j][0];
            for(ll k=1;k<(ll)score[i][j].size();k++) {
                G[now].pb(score[i][j][k]);
                G[score[i][j][k]].pb(now);
                now=score[i][j][k];
            }
        }
    }
    vis[0]=1;
    dfs(0);
    ll ans=0;
    rep(i, n) {
        if(!vis[i]) ans++;
    }
    cout<<ans<<"\n";
}

signed main() {
    IOS
    int T=1;
    cin>>T;
    while(T--) solve();
}

---

DSU另解(Aestivate)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define IO ios::sync_with_stdio(false);cin.tie(0); 
#define rep(i,a) for(int i=1;i<=a;i++)
#define rep0(i,a) for(int i=0;i<a;i++)
 
vector<int>all[7][20];
int dsu[200005], sz[200005];
int find(int g){
    if(g==dsu[g]) return g;
    dsu[g]=find(dsu[g]);
    return dsu[g];
}
void un(int g,int h){
    g=find(g),h=find(h);
    if(g==h) return;
    dsu[g]=h,sz[h]+=sz[g];
}
void solve()
{
    rep(i,6) rep(j,15) all[i][j].clear();
    int n;
    cin>>n;
    rep(i,n) dsu[i]=i,sz[i]=1;
    rep(i,n){
        rep(j,6){
            int g;
            cin>>g;
            all[j][g].pb(i);
        }
    }
    rep(i,6){
        rep(j,15){
            if(!all[i][j].size()) continue;
            int k=all[i][j].back();
            all[i][j].pop_back();
            for(int kk:all[i][j]) un(kk,k);
        }
    }
    int ans=sz[find(1)];
    cout<<n-ans<<"\n";
}
 
signed main()
{
    IO
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

E. 訂機票

Idea: Fysty
Task Prepration: Fysty
Statement Writer: Fysty

Tags（點此展開）

data structure

實體組首殺：CYhuang
線上組首殺：raypeng1729

Subtask 1

$O(n^2)$枚舉所有

$(i,j)$即可。

Subtask 2

線性掃過陣列，同時用一個大小為

$10$的陣列來記錄前面有幾個

$1,2,\dots ,10$，對於每個位置

$j$，

$O(10)$枚舉前面的

$a_i$，然後更新答案即可。

時間複雜度：

$O(10n)=O(n)$

Subtask 3

直接開一個大小為值域的陣列

$sum$ 紀錄有多少個

$a_i\le x$，

對於每個

$i$，直接將

$sum[k-a_i]$ 加到

$ans$，特別的，如果

$2a_i\le k$，則再將

$ans$ 加

$1$。

最後的答案即為

$ans/2$。

Subtask 4

題目要求：

$a_i+a_j\le k$

$l\le j-i+1\le r$

改寫可得：

$a_j\le k-a_i$

$j-l+1\le i\le j-r+1$

這可以用BIT維護（由

$j$找

$i$），因為每次移動

$j$，與之對應的

$i$的區間

$[j-l+1,j-r+1]$只會平移

$1$而已，相當於兩次BIT操作（

$1.$把超出區間範圍的刪掉

$2.$把剛進入區間範圍的加進去）。

因為

$k$不超過

$2\cdot {10}^5$，所以開一個大小比

$2\cdot {10}^5$大一點的陣列就好，無需離散化。

時間複雜度：

$O(n\log n)$

F. 又是一個序列問題

Idea: Aestivate
Task Prepration: wcwu
Statement Writer: wcwu

Tags（點此展開）

dp

實體組首殺：
線上組首殺：

Subtask 1

兩個子序列分別為「全部都是

$1$」跟「全部都是

$3$」時，子序列相鄰兩項同餘

$10$的條件必成立，故答案恆為

$n$。

Subtask 2

發現

$n$ 特別小，所以可以定義

$dp[i][j]$是第一個子序列的尾巴在

$i$ ,第二個尾巴在

$j$ 的最大答案，且

$dp[i][i]=0$。

在轉移時可以著重在第二個子序列，考慮枚舉

$i$ 從

$1$ ~

$n$ ， 再從

$dp[i][i]$轉移到

$dp[i][n]$，在記得

$j$ 從

$1$ ~

$i$ 時跟

$dp[j][i]$ 取max，再多弄個

$dp1[i]$ 表轉移時尾巴數字是

$i$ 的答案，

$dp2[i]$ 表尾巴數字 %10 是

$i$ 的答案，質數的條件就直接暴力枚舉。

複雜度 :

$O(25\cdot n^2)$

Subtask 3

因為題目對於子序列的要求只限於「相鄰兩項」，所以一個數字能不能接在子序列最後面只受到這個子序列最後面的值影響。

再加上

$v_i$的值域極小，所以我們可以直接設

$dp[i][j][k]$為「只考慮陣列前

$i$項時，分別以

$j,k$為兩個子陣列結尾的值的最大子陣列長度和」（

$1\le i\le n,1\le j,k\le 50$）。

設

$v_i$的最大值域

$c=50$，這樣會有

$n{c}^2$個狀態。

轉移時，先把所有的

$dp[i][j][k]$都設為

$dp[i-1][j][k]$，考慮目前的位置有沒有可能接在

$j$或

$k$的後面（

$O(c^2)$建表），如果可以，就把

$dp[i][v_{now}][k]$更新為

$max(dp[i][v_{now}][k],dp[i-1][j][k]+1)$、

$dp[i][j][v_{now}]$更新為

$max(dp[i][j][v_{now}],dp[i-1][j][k]+1)$，因此轉移的複雜度是

$O(1)$ （對單個狀態而言）。

總時間複雜度：

$O(n{c}^2)$

G. 正整數的冪次

Idea: Fysty
Task Prepration: Fysty
Statement Writer: Fysty

Tags（點此展開）

math, number theory

實體組首殺：
線上組首殺：

Subtask 1

$n^m\le {10}^{10}⟹$ 直接暴力 unique

Subtask 2

有幾個偏門的酷酷方法：砸python、用hash

$x=1$ 直接特判加

$1$ 到答案，因為永遠是

$1$ 也只有他會是

$1$。

對於正整數

$x>1$，我們可以找到正整數

$t,k$，使得

$x=t^k$，且

$k$ 最大。以下稱

$x$ 對應的

$t$ 為

$t_x$。

$2,3,...,n$ 的

$t,k$ 可以

$O(n)$ 預處理，實作上類似質數篩。

對於每個

$(x,y)$，把

$(t,ky)$ 存到一個 set。

時間複雜度：

$O(nm\log nm)$

Subtask 3

觀察到若

$t_a\ne t_b$，則

$a$ 的冪次和

$b$ 冪次永遠不會一樣，所以只要對每個可能的

$t$ 算答案。

假設

$t^s\le n<t^{s+1}$，則所有以

$t$ 為底且會出現的數字為

$t^{ij}$，其中

$1\le i\le s,1\le j\le m$。而這其實就只是在算

$i\cdot j$ 有幾種值，注意到這個個數只跟

$s,m$ 有關，以下稱作

$f(s)$。

我們可以

$O(n)$ 提前算出每個

$t$ 以及其對應的

$s=\lfloor {\log }_{t}n\rfloor$。

假設每個

$s$ 對應的

$f(s)$，答案就是

$\sum _{t}f(\lfloor {\log }_{t}n\rfloor )$

注意到因為

$t\le n\le {10}^6$，所以

$\lfloor {\log }_{t}n\rfloor \le 20$，而因為

$m\le {10}^6$，所以我們可以暴力開一個

$20\cdot {10}^6=2\cdot {10}^7$ 的 vis 陣列/bitset 來算有幾種不同的值。

時間複雜度為

$O(n+m\log n)$。

Subtask 4

$m$ 太大不能打表 :(

瓶頸是算出

$f(1),f(2),\dots$

我們希望解決以下問題：

給定

$n,m$，求有多少

$x$ 滿足

$x=i\cdot j$ for some

$1\le i\le n,1\le j\le m$。

對於一個集合

$S\subseteq \{1,2,\dots ,n\}$，令

$F(S)$ 為滿足以下條件的

$1\le N\le nm$ 的個數：

$i\in S⟹i|N$ 且

$\frac{N}{i}\le m$

考慮排容原理，我們其實就是要算

$$\sum _{S\ne \mathrm{\varnothing }}(-1{)}^{|S|+1}F(S)$$

所以我們只需要能快速算

$F(S)$ 就好。令

$lcm(S)$ 為

$S$ 中的元素的最小公倍數。

注意到若

$a<b$ 且

$\frac{N}{a}\le m$，則

$\frac{N}{b}\le m$。

所以我們只需要算滿足

$lcm(S)|N$ 且

$\frac{N}{min(S)}\le m$ 的

$N$ 有幾個就好，也就是滿足

$\frac{lcm(S)}{min(S)}y\le m$ 的個數，即

$F(S)=\lfloor \frac{m\cdot min(S)}{lcm(S)}\rfloor$。

整個排容只需要做位元 dp 即可，因此時間複雜度為

$O(n{2}^n)$。

回到原題，我們只需要算出

$f(1),f(2),\dots ,f(\log n)$ 即可。因此複雜度為

$O(1\cdot 2^1+2\cdot 2^2+\cdots )=O(n\log n)$

Subtask 5

連

$n$ 都變超大怎麼辦

注意到

$lcm(S)\le m\log n$ 的值在

$maxS\le 46$ 時其實沒有很多種。

因為

$F(S)$ 只和

$(lcm(S),min(S))$ 有關，所以可以考慮對每個

$(lcm(S),min(S))$ 算他們在排容中的係數，即

$(-1{)}^{|S|+1}$ 的總和。

令

$dp[i][x][y]$ 為滿足

$lcm(S)=x,min(S)=y,S\subseteq \{1,2,\dots ,i\}$ 的

$(-1{)}^{|S|+1}$ 的總和。

轉移式很簡單直接，這裡就不贅述。注意到可以滾動，然後狀態必須要放在 map 或是一個 vector 裡。

所以我們就可以在

$O(\mathrm{玄}\mathrm{學}\cdot {\log }^{2}n\cdot \log \log n)$ 的時間內得出

$f(1),f(2),\dots ,f(\log n)$ 了。 :D

你以為結束了嗎，還有一個問題：因為

$n$ 變大了，所以我們需要有辦法更快的對所有

$1\le s\le \log n$ 算出有多少

$t$ 滿足

$t$ 不是一個冪次且

$t^s\le n<t^{s+1}$。

再次考慮排容，排容真好用。

令

$cnt[i]$ 為有多少

$x$ 滿足

$x^i\le n$ 且

$x$ 不是冪次，

$sum[i]$ 為有多少

$x$ 滿足

$x^i\le n$。

顯然有

$sum[i]=\lfloor {\log }_{i}n\rfloor -1$。而根據排容：

$$cnt[i]=sum[i]-(cnt[2i]+cnt[3i]+\cdots )$$

還沒完，我們需要知道滿足

$x^i\le n<x^{i+1}$ 的

$x$ 中有多少個不是冪次，但根據定義可以知道就只是

$cnt[i]-cnt[i+1]$ 而已，因此這部分可以

$O(\log n\log \log n)$ 解決。

總時間複雜度為

$O(\mathrm{我}\mathrm{也}\mathrm{不}\mathrm{會})$。

Remark

原本只想出到

$n\le {10}^6,m\le {10}^{14}$，但是這樣看起來好醜(X)有點太暗示做法(?)，所以和 tester abc864197532 討論過後就變成

$n,m\le {10}^{14}$ 了，不客氣(X)。

Solution Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int MOD=998244353;
 
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
 
ll val[50],cnt[50];
 
void calc(ll n,ll m)//credit: abc
{
    ll B=m*n;
    vector<vector<pll> > cur(n+1);
    rep1(i,n)
    {
        rep1(x,i-1)
        {
            vector<pll> nxt;
            for(auto &p:cur[x])
            {
                __int128 lcm=(__int128)p.F/__gcd(p.F,(ll)i)*i;
                if(lcm<=B) nxt.pb({lcm,(MOD-p.S%MOD)%MOD});
            }
            for(auto &p:cur[x]) nxt.pb(p);
            sort(nxt.begin(),nxt.end());
            cur[x].clear();
            int pos=0;
            while(pos<nxt.size())
            {
                ll sum=0;
                int to=pos;
                while(to<nxt.size()&&nxt[pos].F==nxt[to].F)
                {
                    sum=(sum+nxt[to].S)%MOD;
                    to++;
                }
                if(sum!=0)
                {
                    cur[x].pb({nxt[pos].F,sum});
                    val[i]=(val[i]+(m/(nxt[pos].F/x))%MOD*sum%MOD+MOD)%MOD;
                }
                pos=to;
            }
        }
        cur[i].pb({i,1});
        val[i]=(val[i]+m)%MOD;
    }
}
 
void solve()
{
    ll n,m;
    cin>>n>>m;
    if(n==1)
    {
        cout<<"1\n";
        return;
    }
    ll t=__lg(n);
    calc(t,m);
    rep1(i,t)
    {
        ll l=1,r=n;
        while(l<r)
        {
            ll mid=(l+r+1)/2;
            ll cur=1;
            bool can=1;
            rep(j,i)
            {
                if(cur>n/mid)
                {
                    can=0;
                    break;
                }
                cur*=mid;
            }
            if(can) l=mid;
            else r=mid-1;
        }
        cnt[i]=l-1;
    }
    for(int i=t;i>=1;i--) for(int j=i+i;j<=t;j+=i) cnt[i]-=cnt[j];
    rep1(i,t-1) cnt[i]-=cnt[i+1];
    ll ans=1;
    rep1(i,t) ans=(ans+cnt[i]%MOD*val[i])%MOD;
    cout<<ans<<"\n";
}
 
signed main()
{
    MottoHayaku
    int t;
    //cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
}