比赛传送门
作者： fn

---

签到题

1010题 Sum Plus Product / 和+积

题目大意
给定 $n$ 个数，每次随机选两个数 $a,b$ 合并成为 $ab+a+b$ ，直到剩下一个数为
止。求剩下的数字的期望。答案对998244353取模。

考察内容
签到

分析
最终答案和操作顺序无关。枚举一遍就可以。

#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=505;
const ll mod=998244353;
ll n,m,a[N];

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i]; 
		}
		ll ans=0;
		
		for(int i=1;i<=n-1;i++){
			ll cnt=0;
			cnt+=(a[i]+a[i+1])%mod;
			cnt%=mod;
			cnt+=a[i]*a[i+1]%mod;
			cnt%=mod;
			
			a[i+1]=cnt;
		}
		cout<<a[n]<<endl;
	}
	return 0;
}
/*
1
10
1 2 4 8 16 32 64 128 256 512

*/ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

基本题

1008题 Shortest Path in GCD Graph / GCD图中的最短路径

题目大意
给定 $n$ 个点的完全图，两个点之间距离为它们的最大公因数(gcd)，$q$ 次询问两个点之间的最短路以及方案数。
$(2\le n\le 10^7,1\le q\le 50000)$

考察内容
容斥

分析
因为沿路径 $x\to 1\to y$ 即可得到一条长度为2的路径，所以最短路长度不超过2。

最短路长度为1当且仅当 $gcd(x,y)=1$ ，否则等价于询问 $[1,n]$ 中满足 $gcd(x,z)=1$ 且 $gcd(y,z)=1$ 的 $z$ 的数量，
先跑一遍欧拉筛，然后对 $x,y$ 分解质因数，用这些质因数把 $[1,n]$ 中选不了的数字筛掉。如果直接在 $[1,n]$ 筛，不容易判断是向下取整还是向上取整，所以考虑容斥，“把多筛的补回来，把多补的筛回来”。

注意特判：$gcd(x,y)=2$ 时，直接 $x\to y$ 也是一条长度为2的路径。

#pragma GCC optimize(3)
#include
#define ll long long
#define int long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e7+5;
const ll mod=998244353;
ll read(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
ll n,m,q,a[N];

bool isPrime[10000005];

// isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
// Prime存质数

void findPrime(ll n) {
	memset(isPrime, 1, sizeof(isPrime));
	isPrime[1] = 0;// 1不是素数

	for (int i = 2; i <= n; i++){
		if (isPrime[i])// 没筛掉 
			Prime[++cnt] = i; // i成为下一个素数

		for (int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++){
			// 从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
			// 当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
			isPrime[i*Prime[j]] = 0;

			if (i % Prime[j] == 0)break; 
		}
	}
}

signed main(){ // 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	read(n); read(q);
	findPrime(n);

	ll x,y;
	for(int i=1;i<=q;i++){ // q<=50000,O(qlonn)左右可以通过 
		read(x); read(y);

		if(__gcd(x,y)==1){ // 互质 
			cout<<"1 1"<<endl;
			continue;
		}
	
		// x,y不互质时 
		unordered_map<int,bool> mp;
		vector<int> v;
		
		ll cnt3=0;
		if(isPrime[x]){
			if(mp[x]==0){
				mp[x]=1;
				cnt3++;	
				v.push_back(x);
			}
		} 
		else{
			ll x2=x;
			ll p=2;
			while(x2>=2){
				while(x2%p==0){
					if(mp[p]==0){
						mp[p]=1;
						cnt3++;	
						v.push_back(p);
					}
					x2/=p;
				}
				p++;
				if(isPrime[x2]){ // x2是质数 
					if(mp[x2]==0){
						mp[x2]=1;
						cnt3++;	
						v.push_back(x2);
					}
					break; // 提前退出 
				} 
			}
		}
		if(isPrime[y]){
			if(mp[y]==0){
				mp[y]=1;
				cnt3++;
				v.push_back(y);	
			}
		} 
		else{
			ll x2=y;
			ll p=2;
			while(x2>=2){
				while(x2%p==0){
					if(mp[p]==0){
						mp[p]=1;
						cnt3++;	
						v.push_back(p);
					}
					x2/=p;
				}
				p++;
				if(isPrime[x2]){ // x2是质数 
					if(mp[x2]==0){
						mp[x2]=1;
						cnt3++;	
						v.push_back(x2);
					}
					break; // 提前退出 
				} 
			}
		}
		
		sort(v.begin(),v.end());
		int len=v.size(); // len<=8
		// len>=9时的n>=223092870,所以len<=8 
		
		// 容斥 
		ll ans=n;
		for(int i=0;i<=len-1;i++){
			ans-=n/v[i]; // 向下取整 
			for(int j=0;j<=i-1;j++){
				ll sum=v[i]*v[j];
				if(sum>n)break;
				
				ans+=n/sum;
				for(int k=0;k<=j-1;k++){
					sum*=v[k];
					if(sum>n){
						sum/=v[k];
						break;
					}
					ans-=n/sum;
					
					for(int k2=0;k2<=k-1;k2++){
						sum*=v[k2];
						if(sum>n){
							sum/=v[k2];
							break;
						}
						ans+=n/sum;
							
						for(int k3=0;k3<=k2-1;k3++){
							sum*=v[k3];
							if(sum>n){
								sum/=v[k3];
								break;
							}
							ans-=n/sum;
							
							for(int k4=0;k4<=k3-1;k4++){
								sum*=v[k4];
								if(sum>n){
									sum/=v[k4];
									break;
								}
								ans+=n/sum;
								
							for(int k5=0;k5<=k4-1;k5++){
								sum*=v[k5];
								if(sum>n){
									sum/=v[k5];
									break;
								}
								ans-=n/sum;
								
							for(int k6=0;k6<=k5-1;k6++){
								sum*=v[k6];
								if(sum>n){
									sum/=v[k6];
									break;
								}
								ans+=n/sum;	
								sum/=v[k6];		
							}	
							sum/=v[k5];		
							}
							sum/=v[k4];		
							}
							sum/=v[k3];
						}
						sum/=v[k2];
					}
					sum/=v[k];
				}
			}
		}
		
		// 特判2 
		if(__gcd(x,y)==2){
			ans++;
		} 
		
		cout<<"2 "; 
		cout<<ans%mod<<endl;
	}
	return 0;
}
/*
100000 1
4 6


10000000 1
2 9699690

正确输出： 
2 1710234


99999 1
2 10

正确输出： 
40000

*/ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

---

进阶题

1007题 Matryoshka Doll / 俄罗斯套娃

题目大意
有 $n$ 个套娃，现在要将这些套娃分成 $k$ 组，每组套娃按照大小排序后相邻两个套娃之间的大小差距要求 $\ge r$ ，求方案数。

考察内容
动态规划

分析

这道题主要是转移比较难想。。。

状态：
$f[i][j]:$ 前 $i$ 个格子，分成 $j$ 组的方案数。

边界：
$f[0][0]=1$
可以用来转移，使 $f[1][1]=1$

转移：
$f[i][j]=f[i-1][j-1]+f[i-1][j]\ast max(0,j-g[i])$
其中 $g[i]$ 表示满足 $1\le z<i$ 且 $a_i-r<a_z$ 的 $z$ 的个数。

对转移的解释：
右半部分前一项 $f[i-1][j-1]$ 表示第 $i$ 个套娃单独分一组的情况；

右半部分后一项 $f[i-1][j]\ast max(0,j-g[i])$ 表示第 $i$ 个套娃套到前面的套娃上面的情况，此时套娃的组数 $j$ 不变，所以是从 $f[i-1][j]$ 转移过来。
$j-g[i]\le 0$ 的时候，找不到可以套的娃，不用转移。
$j-g[i]\ge 0$ 的时候，前面有 $j-g[i]$ 个可以套的娃，转移方案数。

#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=5005;
const ll mod=998244353;

ll n,m,k,r,a[N];
ll f[N][N]; // f[i][j]:前i个格子，分成j组的方案数 
ll g[N];

int main(){ // AC
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n>>k>>r;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=0;i<=n;i++){ // 初始化 
			for(int j=0;j<=k;j++){ 
				f[i][j]=0; 
			}
		}
		
		f[0][0]=1; // 边界	

		// 转移 
		for(int i=1;i<=n;i++){ // 枚举到第i个格子 
			g[i]=0;
			for(int j=1;j<=i-1;j++){
				if(a[i]-r<a[j]){ // 统计塞不下的个数 
					g[i]++;
				}
			} 
			
			for(int j=1;j<=k;j++){ // 分成j组 
				f[i][j]=f[i-1][j-1]; // 第i个单独分一组
				
				f[i][j]+=f[i-1][j]*max(0ll,j-g[i])%mod;
				f[i][j]%=mod;
			}
		}
		cout<<f[n][k]%mod<<endl;
	}
	return 0;
}
/*
1
4 3 2
1 2 3 4

正确输出： 
3


1
4 4 100
1 2 3 4

正确输出： 
1
*/ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

---

1003题 Fast Bubble Sort / 快速冒泡排序

题目大意
对于一个长度为𝑁的数组𝐴，令𝐵(𝐴)表示对𝐴进行冒泡排序中的一轮循环之后得到的数组。
令𝑛𝑢𝑚(𝐴)表示从𝐴到𝐵(𝐴)最少需要移动元素(数组区间循环移位)的次数。

给定一个1 − 𝑛的排列𝑃。𝑞次询问，每次询问𝑛𝑢𝑚(𝑃 [𝑙, 𝑟])

考察内容
单调栈，树状数组，线段树

分析
假设 $P=n_1{\lambda }_1{n}_2{\lambda }_2\cdot \cdot \cdot n_k{\lambda }_k$ ,则 $B(P)={\lambda }_1{n}_1{\lambda }_2{n}_2\cdot \cdot \cdot {\lambda }_k{n}_k$ ，其中 $n_1,\cdot \cdot \cdot ,n_k$ 为从左到右的局部最大值且有 $n_1<n_2<\cdot \cdot \cdot <n_k$ ，则不难证明答案为 $[l,r]$ 区间里非空 ${\lambda }_i$ 的个数。

将询问离线，每次从 $n$ 到 $1$ 倒序扫描左端点𝑙并回答所有左端点为 $l$ 的询问。
对于每个固定的左端点 $l$ ，$[l,n]$ 中从左到右的局部最大值可以通过单调栈维护，局部最大值插入/删除对于答案的影响可以用树状数组/线段树快速更新/求解。

单组数据时间复杂度为 $O((n+q)logn)$ 。

#pragma GCC optimize("O3")
#pragma GCC optimize("O2")

#include
#define int long long
#define double long double
using namespace std;
 
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

namespace internal {

int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

template <class S, S (*op)(S, S), S (*e)()> struct segtree { // 线段树 
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n((int)(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

using S=int;
S op(S l,S r){return l+r;}
S e(){return 0;}

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
const int mod=998244353;
const int base[]={12321,32123};
const double EPS=1e-9;
const double pi=acos(-1);
const int INF=1e18;
const int N=100017;
mt19937 rng(1235);

int n,q;
int p[N];
int ans[N],C[N],now[N];
vector<pii> info[N];
int st[N];

int lowbit(int u){return u&(-u);}
void update(int u,int w){for (int i=u;i<=n+7;i+=lowbit(i)) C[i]+=w;}
int query(int u){int ans=0; for (int i=u;i;i-=lowbit(i)) ans+=C[i]; return ans;}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int _;
	cin>>_;
	while (_--){
		cin>>n>>q;
		rep(i,n) cin>>p[i];
		for (int i=1;i<=n+5;++i) C[i]=0,now[i]=0;
		rep(i,N) info[i].clear();
		p[n]=n+1;
		rep(i,q){
			int u,v;
			cin>>u>>v;
			u--, v--;
			info[u].pb({i,v});
		}
		
		int cnt=0;
		st[cnt++]=n; 
		auto upd=[&](int u){
			update(u+1,(now[u+1]?-1:1)), now[u+1]^=1;
			update(u+2,(now[u+2]?-1:1)), now[u+2]^=1;
		};
		for (int i=n-1;i>-1;--i){
			while (cnt&&p[i]>p[st[cnt-1]]) {
				cnt--; 
				upd(st[cnt]);
			}
			st[cnt++]=i, upd(i);
			for (auto c:info[i]){
				int id=c.F, r=c.S;
				if (i==r) ans[id]=0;
				else ans[id]=(query(r+1)-query(i))/2;
			}
		}
		
		rep(i,q) cout<<ans[i]<<"\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

---