CVBB ACM Team

题意:无限个$7$位数码管，可以点亮$n$位，问最大数字。

题解:显然应该追求所得数字的位数大，因此每一位用的应该尽量少，如果是奇数就填个$7$然后全填$1$，如果是偶数就全填$1$。

题意:一个无限循环的$01$串，给定循环节，问有多少个前缀（可为空）满足$0$的数量减$1$的数量等于$x$，若有无限个输出$-1$。

题解:如果一个循环节的$01$数量相等，那么只要有一个前缀（可为空）满足条件就有无限个前缀满足条件。否则，解的数量是有限的，考虑第一个循环节中的每一位，如果它和目标值的差值可以通过非负整数个循环节来填补，则答案$+1$。另外注意如果$x=0$空串也满足条件需要特判。

题意:给定字符串$s$和$t$，问要多少个$s$拼在一起才能使得$t$是它的子序列，或判断无解。

题解:设$f[i][j]$表示离$s$的第$i$位最近的下一个字符$j$的位置，一位位跳即可，如果没有可匹配的则返回第一位并让答案$+1$，如果某个字符第一位都没有可匹配的则无解。上学期程设周末练习赛的原题，当时空间限制被改的很小这样写会MLE，不知正解是什么（不会正解的我用short卡过去了）

题意:$T$次询问，每次询问给定数字$a$和$m$，求满足下列条件的$x$的个数，$0 \le x < m$且$\gcd(a, m) = \gcd(a + x, m)$。$(1 \le T \le 50, 1 \le a < m \le 10^{10})$

题解:设$d=gcd(a,m)$，则题目等价于$gcd(\frac{a}{d},\frac{m}{d})=gcd(\frac{a+x}{d},\frac{m}{d})=gcd(\frac{a+x}{d} \ mod \frac{m}{d},\frac{m}{d})=1$，可以发现$0 \le x < m$的取值可以使得$\frac{a+x}{d} \ mod \frac{m}{d}$是整数的前提下恰好取遍$<\frac{m}{d}$的正整数，又因为要求互质，所以答案就是$\phi(\frac{m}{d})$，直接对于每一个询问$O(\sqrt{m})$求欧拉函数即可。

题意:给定一个$1$到$n$的排列，每个元素有一个权值$a_i$，你可以先将这个排列分成互不相交的非空前缀（称作第一个集合）和非空后缀（称作第二个集合）两个集合，然后可以将一些元素移动到另一个集合，使得最终第一个集合的所有元素都小于第二个集合的所有元素。最小化经过移动的元素的权值和。$(2 \le n \le 2 \cdot 10^5)$

题解:线段树维护$n-1$个值表示此时以该点为分界点分割前后缀所需的权值和，枚举最终第一个集合中的最大值，一开始为$0$，逐渐增加到$n$，每次用全局最小值和答案进行比较。每次增加最大值的时候，设此时对应的值为于$pos_i$，则$1$到$pos_i-1$的分界方案需要额外将这个元素移到第一个集合，区间加$a_{pos_i}$，$pos_i$到$n-1$的分界方案不需要再将这个元素移到第一个集合，区间加$-a_{pos_i}$，使用线段树维护即可。

题意:$n$个位置，每个位置等概率出现$l_i$到$r_i$中的数，求序列不增的概率，对取模。$(2 \le n \le 50, 0 \le l_i \le r_i \le 998244351)$

题解:离散化成$O(n)$个左闭右开的区间$[l_i,r_i+1)$进行dp，如果两个数不出现在同一个区间那么直接累加即可，如果多个数出现在同一区间就比较复杂了。我们现在考虑的问题是，在$l$个不同的数中可以重复地选择$k$个数组成一个单调不增的序列，有多少种方案。我们构造一个序列$$\underbrace{\text{0 0 0 $ \dots $ 0}}_{k-1 \text{个} } \text{ 1 2 3 $ \dots l $}$$在这个序列中选择$k$个数，每一种选择方案和上述问题的某种方案一一对应。如果第$i$个$0$被选，代表第$i$个数和第$i+1$个数相同，对于剩下的第$i$个$0$没有被选的$i$，他们依次是$1\,2\,3\,\dots l$中被选择的数，因为最后一位不能和后面一位相同，所以前面的$0$只有$k-1$个。因此方案数为$\binom{l+k-1}{k}$。因此我们设$f[i][j]$为考虑到第$i$个数且第$i$个数位于第$j$个区间的方案数，$sum[i][j]=\sum_{k=1}^{j}{f[i][k]}$，转移的时候枚举前面有多少个数和自己位于同一个区间，则$f[i][j]=sum[i-k+1][j-1] \times \binom{l+k-1}{k}$，其中$l$是对应区间长度。对于枚举的$k$，当某个数的合法范围不包括对应区间的时候停止即可。

#include <bits/stdc++.h>
#define maxn 150
//debug:数组开两倍 
using namespace std;
 
const int p = 998244353;
 
int n, n0;
int l[maxn], r[maxn];
int a[maxn];
int f[maxn][maxn], sum[maxn][maxn];
 
inline int inv(int x){
	int y = p - 2, ans = 1;
	while(y){
		if(y & 1) ans = 1ll * ans * x % p;
		x = 1ll * x * x % p, y >>= 1;
	}
	return ans;
}
 
int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) scanf("%d%d", &l[i], &r[i]), a[++n0] = l[i], a[++n0] = ++r[i];
	sort(a + 1, a + 1 + n0);
	n0 = unique(a + 1, a + 1 + n0) - (a + 1);
	for(int i = 1;i <= n;i++){
		l[i] = lower_bound(a + 1, a + 1 + n0, l[i]) - a;
		r[i] = lower_bound(a + 1, a + 1 + n0, r[i]) - a;
	}
	for(int i = 1;i <= n0;i++) sum[0][i] = 1;
	for(int i = 1;i <= n;i++){
		for(int j = n0 - 1;j;j--){
			if(l[i] <= j && j < r[i]){
				int len = a[j + 1] - a[j], C = 1;//debug:len打成了a[r[i]] - a[l[i]] 
				for(int k = 1;k <= i;k++){
					if(!(l[i + 1 - k] <= j && j < r[i + 1 - k])) break;
					C = 1ll * C * (len + k - 1) % p * inv(k) % p;
					f[i][j] += 1ll * C * sum[i - k][j + 1] % p;
					//printf("%d %d %d %d %d--\n", i, j, k, len + k - 1, k);
					if(f[i][j] >= p) f[i][j] -= p;
				}
			}
			//printf("%d %d %d--\n", i, j, f[i][j]);
			sum[i][j] = sum[i][j + 1] + f[i][j];
			if(sum[i][j] >= p) sum[i][j] -= p;
		}
	}
	int ans = sum[n][1];
	for(int i = 1;i <= n;i++) ans = 1ll * ans * inv(a[r[i]] - a[l[i]]) % p;
	printf("%d", ans);
}

这里还有一道几乎一样的题，只不过因为某些数可以不选，因此转移的时候枚举$k$遇到不在对应区间的数不要跳出，只需默认这个数不选，不更新组合数即可。P3643 [APIO2016]划艇