$\mathrm {Subtask}1: n\le 5$。

直接 $\mathcal O(n^m)$ 爆搜，暴力判强连通即可。

$\mathrm{Subtask} 2: n\le 15$。

这个我没有写，不知道对不对。

考虑状压 dp。

思考强连通图的形成过程，一定是从 $1$ 所在的强连通分量中的某个点出发，走到某些还不在这个强连通分量的点，然后走回 $1$ 所在的强连通分量中的某个点。

并且，我们并不关心起点终点具体是那个点。

据此，设 $f(S,t)$ 表示 $t$ 秒后 $1$ 所在的强连通分量为 $S$ 的方案数。

转移大概就是设 $g(S,t)$ 表示经过 $t$ 秒经过了 $S$ 中这些点的方案数，然后转移做一个二维的合并：$f(S_1,t_1)\times g(S_2,t_2)\to f(S_1\cup S_2, t_1+t_2)[S_1\cap S_2 = \emptyset]$。

复杂度 $\mathcal O(3^n \mathrm{poly}(n))$。

$\mathrm{Subtask 3}:n\le 300$。

考虑优化状压 dp。两种方法优化到正解：重构 dp 状态，分步转移。两者殊途同归。

因为我们并不关心 $1$ 所在的强连通分量具体是啥，所以设 $f(i,j,k)$ 表示 $i$ 次操作后 $1$ 所在的强连通分量大小为 $j$，目前往外扩展了 $k$ 个新点的方案数。

初始状态 $f(0,1,0)=1$。三种转移，分别对应走回 $1$ 所在的强连通分量，走一个新点，走到一个还在构建的点。

$$f(i,j,k)\times j\to f(i+1,j+k,0)$$

$$f(i,j,k)\times (n-j-k)\to f(i+1,j,k+1)$$

$$f(i,j,k)\times k\to f(i+1,j,k)$$

答案就是 $f(m,n,0)$。

注意！！！这里有个大坑点！！！

模数是 $10^9 + 7$ 而不是 $998244353$。有人缺省源里 $\mathrm{mod}=998244353$ 调了一年。

考虑线段树，显然操作 1,3,4 均能用线段树解决。

操作 2 并不好处理，如果直接硬除，操作复杂度为单次 $O(n)$。

考虑将其转化为便于线段树维护的操作。

对于区间 $[l,r]$，记 $p$ 为 $[l,r]$ 间的最大值，$q$ 为 $[l,r]$ 的最小值。

若 $p-\lfloor \frac{p}{d}\rfloor=q-\lfloor \frac{q}{d}\rfloor$，那么此时可以将这个操作转化为区间加法。

原因不难理解，显然 $a_i-\lfloor \frac{a_i}{d}\rfloor$ 单调不降，如果满足上述条件，显然 $a_i-\lfloor \frac{a_i}{d}\rfloor$ 都相等，那么直接作整体加（实际上是减）即可。

这种操作的复杂度如何？

根据直觉，其实会发现每次 2 操作 $a_i$ 减小得比 $\lfloor\frac{a_i}{d} \rfloor$ 快得多，主观上时间复杂度并不高。

严谨的时间复杂度证明需要势能分析。

（注：此处贺了 LOJ 讨论区的证明，加了点我自己的理解，大概率是错的，看个乐就行）

不妨设 $n,v$ 同阶。

定义势能为 $\sum \log_2 (|a_i-a_{i-1}|)$。

显然，开始时势能为 $O(n\log n)$。

一次区间加后，区间 $[l,r]$ 内部势能不变，两端各增加 $O(\log_2 n)$。总体来说变化量可以忽略（其实此时的势能为 $O((n+q)\log_2 n)$）。

每个势能的连续段在树上被分为 $\log$ 段，而每次区间除法操作珂以使两个相邻连续段之间的势能减 1。

相当于用 $\log$ 的代价减去了 1。

那么总的时间复杂度即为 $O((n+q)\log ^2 n)$。

#include <bits/stdc++.h>
typedef long long ll;
const ll INF = 1e18;

int read() {
    int s = 0,f = 1;
    char c = getchar();
    for(;c < '0'||c > '9';c = getchar())
        if(c == '-')f = -1;
    for(;c >= '0'&&c <= '9';c = getchar())
        s = (s << 1) + (s << 3) + (c ^ '0');
    return s * f;
}

const int maxn = 1e5 + 5;
int n,m;

int ls[maxn << 2],rs[maxn << 2];
ll sum[maxn << 2],lz[maxn << 2],maxv[maxn << 2],minv[maxn << 2];

void pushup(int i) {
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
    maxv[i] = std::max(maxv[i << 1] , maxv[i << 1 | 1]);
    minv[i] = std::min(minv[i << 1] , minv[i << 1 | 1]);
    return ;
}

void pushdown(int i) {
    if(!lz[i])return ;
    lz[i << 1] += lz[i];
    lz[i << 1 | 1] += lz[i];
    minv[i << 1] += lz[i];
    minv[i << 1 | 1] += lz[i];
    maxv[i << 1] += lz[i];
    maxv[i << 1 | 1] += lz[i];
    sum[i << 1] += 1ll * (rs[i << 1] - ls[i << 1] + 1) * lz[i];
    sum[i << 1 | 1] += 1ll * (rs[i << 1 | 1] - ls[i << 1 | 1] + 1) * lz[i];
    lz[i] = 0;
    return ;
}

void build(int i,int l,int r) {
    ls[i] = l;
    rs[i] = r;
    if(l == r) {
        sum[i] = maxv[i] = minv[i] = read();
        return ;
    }
    int mid = l + r >> 1;
    build(i << 1 , l , mid);
    build(i << 1 | 1 , mid + 1 , r);
    pushup(i);
    return ;
}

void modify(int i,int l,int r,int k) {
    if(ls[i] >= l&&rs[i] <= r) {
        sum[i] += 1ll * k * (rs[i] - ls[i] + 1);
        lz[i] += k;
        maxv[i] += k;
        minv[i] += k;
        return ;
    }
    if(ls[i] > r||rs[i] < l)return ;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    if(l <= mid)modify(i << 1 , l , r , k);
    if(r > mid)modify(i << 1 | 1 , l , r , k);
    pushup(i);
    return ;
}

void Maintain(int i,int l,int r,int k) {
    if(ls[i] >= l&&rs[i] <= r) {
        int x = maxv[i] - (int)std::floor((double)(1.0 * (double)maxv[i] / (double)k));
        int y = minv[i] - (int)std::floor((double)(1.0 * (double)minv[i] / (double)k));
        if(x == y) {
            sum[i] -= 1ll * (rs[i] - ls[i] + 1) * x;
            lz[i] -= x;
            maxv[i] -= x;
            minv[i] -= x;
            return ;
        }
    }
    if(ls[i] > r||rs[i] < l)return ;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    if(l <= mid)Maintain(i << 1 , l , r , k);
    if(r > mid)Maintain(i << 1 | 1 , l , r , k);
    pushup(i);
    return ;
}

ll Querymin(int i,int l,int r) {
    if(ls[i] >= l&&rs[i] <= r)return minv[i];
    if(ls[i] > r||rs[i] < l)return INF;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    ll s = INF;
    if(l <= mid)s = std::min(s , Querymin(i << 1 , l , r));
    if(r > mid)s = std::min(s , Querymin(i << 1 | 1 , l , r));
    return s;
}

ll Querysum(int i,int l,int r) {
    if(ls[i] >= l&&rs[i] <= r)return sum[i];
    if(ls[i] > r||rs[i] < l)return 0;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    ll s = 0;
    if(l <= mid)s += Querysum(i << 1 , l , r);
    if(r > mid)s += Querysum(i << 1 | 1 , l , r);
    return s;
}

int main() {
    n = read();
    m = read();

    build(1 , 1 , n);

    while(m --) {
        int op = read(),l = read() + 1,r = read() + 1,k;
        switch(op) {
            case 1: {
                k = read();
                modify(1 , l , r , k);
                break ;
            }
            case 2: {
                k = read();
                Maintain(1 , l , r , k);
                break ;
            }
            case 3: {
                printf("%lld\n",Querymin(1 , l , r));
                break ;
            }
            case 4: {
                printf("%lld\n",Querysum(1 , l , r));
                break ;
            }
        }
    }
    return 0;
}

注意：这道题的“先到先得”是让我们按照飞机到达的时间升序排序。

首先发现，国内和国外可以分开处理，最后枚举统计。

这就要求我们对国内和国外求出分配 $i$ 个廊桥时的飞机数。

观察到一个性质：如果分配 $i$ 个廊桥时飞机 $j$ 有位置，则分配 $i+1$ 个廊桥时飞机仍有位置。

观察一下样例的那张图，手玩一下样例，不难发现这个性质。

那么我们只需要求出每个飞机 $j$ 所需的最小廊桥数，再用前缀和统计即可。

不妨把廊桥按照 $1\sim m$ 标号，用两个优先队列维护空闲和非空闲的廊桥，设为 $q_1,q_2$。

当遍历到一个新飞机，弹出 $q_2$ 中飞走的飞机，把这些廊桥放入 $q_1$，再从 $q_1$ 取出最小的廊桥。

国内国外的飞机都处理一遍，用前缀和维护一下，然后枚举即可。

时间复杂度 $O(N\log N)$。

// Problem: #3542. 「CSP-S 2021」廊桥分配
// Contest: LibreOJ
// URL: https://loj.ac/p/3542
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
const int maxn = 1e5 + 5;
typedef pair<int,int> pii;
struct node {
	int x,y;
	node() {
		x = y = 0;
	}
}a[maxn],b[maxn];
int n,m,k;
int sum1[maxn],sum2[maxn];
priority_queue<pii,vector<pii>,greater<pii> > q;
priority_queue<int,vector<int>,greater<int> > s;
int main() {
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
	scanf("%d %d %d",&n,&m,&k);
	for(int i = 1;i <= m;++ i) {
		scanf("%d %d",&a[i].x,&a[i].y);
	}
	sort(a + 1 , a + 1 + m , [&](const node& p,const node& q) {
		return p.x < q.x;
	});
	for(int i = 1;i <= k;++ i) {
		scanf("%d %d",&b[i].x,&b[i].y);
	}
	sort(b + 1 , b + 1 + k , [&](const node& p,const node& q) {
		return p.x < q.x;
	});
	while(!q.empty())q.pop();
	while(!s.empty())s.pop();
	for(int i = 1;i <= m;++ i)s.push(i);
	for(int i = 1;i <= m;++ i) {
		for(;!q.empty()&&q.top().fir < a[i].x;q.pop())s.push(q.top().sec);
		int ans = s.top();
		s.pop();
		++ sum1[ans];
		q.push(mp(a[i].y , ans));
	}
	while(!q.empty())q.pop();
	while(!s.empty())s.pop();
	for(int i = 1;i <= k;++ i)s.push(i);
	for(int i = 1;i <= k;++ i) {
		for(;!q.empty()&&q.top().fir < b[i].x;q.pop())s.push(q.top().sec);
		int ans = s.top();
		s.pop();
		++ sum2[ans];
		q.push(mp(b[i].y , ans));
	}
	for(int i = 1;i <= n;++ i)sum1[i] += sum1[i - 1],sum2[i] += sum2[i - 1];
	int ans = 0;
	for(int i = 0;i <= n;++ i)ans = max(ans , sum1[i] + sum2[n - i]);
	printf("%d\n",ans);
	return 0;
}

（注：为了方便，本文将 $S$ 中 $1$ 的个数限制设为 $K$）

这种计数类的问题大概率是 DP，可以往这个方面想。

考虑状态的设计，由于这道题存在进位的问题，而且进位是从低到高的，所以可以按二进制位从低到高考虑。

那么状态里肯定要有两维：$(i,j)$，分别表示当前的位数，和已经确定的 $a$ 中元素的数量。

但是题中对二进制 $1$ 的个数限制为 $K$，而且进位相当烦人，这时就可以考虑直接把它们设进状态。

毕竟这题数据范围不大，就算不是正解也能拿不少分。

由此，设计出一个 DP：

设 $f(i,j,k,q)$ 表示 $0\sim i-1$ 位已经考虑过，当前考虑第 $i$ 位，$a$ 中已经有 $j$ 个元素确定，目前 $S$ 中有 $k$ 个 $1$，且从 $0\sim i-1$ 推过来的进位数为 $q$ 时的权值和。

初始状态：$f(0,0,0,0)=1$。

发现这个状态并不是很好从前面转移来，那么我们就用已有的状态往后转移（刷表）。

考虑在第 $i$ 位放 $t(0\le t\le n-j)$ 个 $a$ 中的元素，那么 $S$ 中 $1$ 的个数会变成 $k + ((t + q)\bmod 2)$，向第 $i+1$ 位进 $\lfloor \frac{t+q}{2} \rfloor$ 个 $1$。

那么接下来的状态就是 $f(i+1,j+t,k+((t+q)\bmod 2),\lfloor \frac{t+q}{2} \rfloor)$。

现在来算一算这次转移的贡献，直接放式子：

$$f(i,j,k,q) \times \mathrm C_{n-j}^t \times v_i^t$$

这个式子并不难理解，就是在 $a$ 剩下的 $n-j$ 个元素中选 $t$ 个，会产生 $v_i^t$ 的权值。

剩余要注意的就是统计答案。累加上所有的 $f(m+1,n,k,q)$。

但因为这题二进制 $1$ 的个数至多为 $K$，而且 $m+1$ 位及以后显然还会有进位产生的 $1$，不难发现，这个状态的 $S$ 中真正的 $1$ 的个数是 $k+\text{popcount}(q)$。

所以还要在枚举时判断一下 $k+\text{popcount}(q) \le K$。

那么这道题就做完了。时间复杂度 $O(mn^4)$，卡得很紧，组合数和 $v_i^t$ 都要预处理出来。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 35;
const int maxm = 105;
ll C[maxn][maxn];
int n,m,K;
ll v[maxm],pw[maxm][maxn],popcnt[maxn];
int lowbit(int x) {
	return x & -x;
}
int popcount(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))++ ans;
	return ans;
}
ll f[maxm][maxn][maxn][maxn >> 1];
int main() {
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	scanf("%d %d %d",&n,&m,&K);
	for(int i = 0;i <= m;++ i) {
		scanf("%lld",&v[i]);
		pw[i][0] = 1ll;
		for(int j = 1;j <= n;++ j)pw[i][j] = pw[i][j - 1] * v[i] % mod;
	}
	for(int i = 0;i <= n;++ i) {
		C[i][0] = 1ll;
		for(int j = 1;j <= i;++ j) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
		}
		popcnt[i] = popcount(i);
	}
	f[0][0][0][0] = 1ll;
	for(int i = 0;i <= m;++ i) {
		for(int j = 0;j <= n;++ j) {
			for(int k = 0;k <= K;++ k) {
				for(int q = 0;q <= (n >> 1);++ q) {
					for(int t = 0;t <= n - j;++ t) {
						(f[i + 1][j + t][k + (t + q & 1)][t + q >> 1] += f[i][j][k][q] * C[n - j][t] % mod * pw[i][t] % mod) %= mod;
					}
				}
			}
		}
	}
	ll ans = 0;
	for(int k = 0;k <= K;++ k) {
		for(int q = 0;q <= (n >> 1);++ q) {
			if(k + popcnt[q] <= K) {
				(ans += f[m + 1][n][k][q]) %= mod;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}