杂题选做（2023.11.9-2023.11.13）

杂七杂八的题目。

Atcoder AGC041D Problem Scores

题目描述：

• 有 $n$ 道还未赋分的题目，你需要给这 $n$ 道题目赋分。
• 设第 $i$ 道题目的分数为 $A_i$。给题目赋分的方案需要满足：
  • 对于任意 $i \in [2, n]$，$A_{i-1} \leq A_{i}$。
  • 对于任意 $i \in [1, n]$，$1 \leq A_{i} \leq n$。
  • 对于任意一个大小为 $k$（$1 \leq k < n$）的题目子集 $S$ 和任意一个大小为 $k+1$ 的题目子集 $T$，需要满足：$\sum_{x \in S}A_x < \sum_{x\in T}A_x$。
• 你需要计算，有多少种给题目赋分的方案，使得能满足上述三个条件。请求出答案对 $M$ 取模的结果。

$2\ \leq\ N\ \leq\ 5000$

题目分析：

妙，实在是太妙了。

首先对于给定的 $k$ 限制最严的就是 $S$ 为 $A$ 的后 $k$ 个而 $T$ 为 $A$ 的前 $k+1$ 个，进一步发现随着 $k$ 的增大只要两个不交限制就是变得更加严格的，因此当 $k = \lfloor \frac{n-1}{2} \rfloor$ 时是限制最严的时候。

考虑维护 $\sum_{x \in T} A_x - \sum_{x \in S} A_x$，对于第一个限制的处理我们可以理解为一开始 $A$ 全是 $n$，然后每次选择一个前缀减 $1$，可以发现这种的操作对于维护的值得贡献必然为负值，所以预处理出来贡献就转化为了一个完全背包问题。

现在还有一个问题就是减 $1$ 的操作次数不能超过 $n$，因为维护的值初始为 $n$ 而我们每一次操作都至少将维护的值减 $1$，所以只要这个值最后大于 $0$ 我们的操作次数就不可能超，就直接背包就好。

代码：

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define N 5005
int n,P,ans,w[N],dp[N];
int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d %d",&n,&P);dp[n]=1;
	for(int i=1;i<=(n+1)/2;++i) w[i]=i;
	for(int i=1;i<=n/2;++i) w[n-i+1]=i;
	for(int i=1;i<=n;++i) for(int j=n;j>=w[i];--j)
		dp[j-w[i]]=(dp[j-w[i]]+dp[j])%P;
	for(int i=1;i<=n;++i) ans=(ans+dp[i])%P;
	printf("%d\n",ans);return 0;
}

CF762F Tree nesting

题目描述：

给定两棵树 $S,T$，求 $S$ 有多少个连通子图与 $T$ 同构。

$1 \le |S| \le 1000$，$1 \le |T| \le 12$

题目分析：

首先我们可以枚举一下 $T$ 的根来固定树的形态，然后枚举 $S$ 的一棵子树来匹配 $T$。

下面就可以类似 $dfs$ 解决这个问题，也就是说我们要能够得到 $S(i,j)$ 表示 $S$ 中子树 $i$ 匹配 $T$ 中子树 $j$ 的方案数。

设 $son$ 代表 $T$ 子树中与 $j$ 直接相连的 $j$ 的儿子集合，那么其实就是每次在 $S$ 中新加入一棵子树判断其与 $son$ 中的哪个儿子匹配即可，可以直接 $2^{|T|}$ 记录状态。

复杂度 $O(|S|^2|T|2^{|T|})$。

代码：

点击查看代码

CF1519F Chests and Keys

题目描述：

给定 $n,m$ 表示存在 $n$ 个宝箱和 $m$ 把钥匙，第 $i$ 把钥匙需要 $b_i$ 元，第 $i$ 个宝箱内部有 $a_i$ 元。

现在进行一场游戏，Bob 是本场游戏的玩家，而 Alice 则是场景布置者，Alice 可以给每个宝箱上一些锁（第 $j$ 种锁需要第 $j$ 种钥匙打开）

如果 Bob 可以购买一些钥匙，然后打开一些宝箱，使得 Bob 的收益大于 $0$，那么 Bob 就赢得了游戏，反之 Alice 获得了胜利。

现在 Alice 打算布置宝箱上的锁，第 $i$ 个宝箱上放置第 $j$ 种锁的花费为 $c_{i,j}$，请帮助 Alice 找到一种布置锁的方案，使得花费最小，且 Alice 将取得胜利。

$n,m\le 6,a_i,b_i\le 4,c_{i,j}\le 10^7$

特别的，一个箱子上可以放置若干把锁，Bob 需打开所有锁才能获得内部的钱。

题目分析：

考虑如果已知了一种布置锁的方案，我们能不能判断胜负。

其实这个是可以的，因为一种方案 Alice 能获胜当且仅当 Bob 无论选择开启哪些宝箱得到的收益都不够，也就是如果宝箱 $i$ 上有第 $j$ 个锁那么连边 $(i,j)$，设 $N(S)$ 表示与点集 $S$ 有直接连边的点，那么这个条件就是：

$$\forall S\subseteq [1,n]，\sum_{x \in S} a_x \le \sum_{x \in N(S)} b_x$$

这东西就是一个 hall 定理的形式，也就是说我们可以将宝箱 $i$ 看作 $a_i$ 个点钥匙 $j$ 看作 $b_j$ 个点，那么只要我们按照上述的方式连边，连出来的图有完美匹配则 Alice 赢。

在完美匹配的情况下必然是宝箱对应的点完全匹配没了，钥匙对应的点可能有剩下的，所以我们可以依次考虑每一个宝箱对应的 $a_i$ 个点然后判断这些点的连边情况，当我们考虑到第 $i$ 个宝箱的时候，我们只在意经过了前 $i-1$ 个宝箱之后 $b$ 是什么样子的，因为 $b_i \le 4$ 所以可以使用五进制压缩一下。

也就是设 $dp[i][S]$ 表示考虑到了第 $i$ 个宝箱，当前 $b$ 剩余的情况为 $S$ 的最小花费，转移就是枚举当前这个宝箱的连边情况，复杂度就是 $O(n5^{2m})$，据说可以通过。

考虑优化，这种题优化最常见的就是分步，我们不一次决定所有的连边情况，而一次只决定与一个钥匙的连边情况，虽然这样可能出现与同一个钥匙连边多次导致贡献被重复计算多次，但是这一定不优，所以这样得到的答案也是对的。

也就是设 $dp[i][S][j]$ 表示考虑到了第 $i$ 个宝箱，当前 $b$ 剩余的情况为 $S$，$a_i$ 还剩 $j$ 个的最小花费，转移就是枚举第几个宝箱连几条边，设 $n,m$ 同阶复杂度为 $O(16n^25^{n})$ 可以通过。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100],b[100],c[100][100],f[8][20000][8],p[20000][8],pw[10];
void get(int S){   //获得状态 S 下到底剩多少个。 
	int tS = S;
	for(int i=1; i<=m; i++){
		p[S][i] = tS % 5;
		tS /= 5;
	}
}
void chkmin(int &a,int b){
	a = min(a,b);
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	for(int i=1; i<=m; i++)	scanf("%lld",&b[i]);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%lld",&c[i][j]);
		}
	}
	pw[1] = 1;
	for(int i=2; i<=m; i++)	pw[i] = pw[i-1] * 5;
	int mx = 0;
	for(int i=1; i<=m; i++)	mx += pw[i] * b[i];
	for(int i=0; i<=mx; i++)	get(i);
	memset(f,0x3f,sizeof(f));
	int inf = f[0][0][0];
	f[1][mx][a[1]] = 0; 
	for(int i=1; i<=n; i++){
		for(int j=mx; j>=0; j--){
			for(int k=a[i]; k>=0; k--){
				if(f[i][j][k] == inf)	continue;
				for(int h=1; h<=m; h++){
					for(int g=1; g<=p[j][h] && g <= k; g++){
						chkmin(f[i][j-g*pw[h]][k-g],f[i][j][k]+c[i][h]);
					}
				}
			}
			chkmin(f[i+1][j][a[i+1]],f[i][j][0]);
		}
	}
	int ans = inf;
	for(int i=0; i<=mx; i++)	chkmin(ans,f[n+1][i][0]);
	if(ans == inf)	printf("-1\n");
	else	printf("%lld\n",ans);
	return 0;
}

CF710D Two Arithmetic Progressions

题目描述：

已知两个无限长的等差数列，首项分别为 $b_1, b_2$，公差分别为 $a_1, a_2$，求 $[L,R]$ 中有多少个数在两个等差数列中都出现了。

题目分析：

只要我们可以找到某一个数 $p$ 满足数 $p$ 同时在两个等差数列中出现，那么其他同时出现的数必然满足其为 $p + k\times \textup{lcm}(a_1,a_2)$。

而找到数 $p$ 其实就是要解方程：

$$b_1 + a_1 x = b_2 + a_2 y$$

这个东西移项之后就是一个 $Ax + By = C$ 的形式，直接使用 exgcd，最后 $p = b_1 + a_1 x$。

假设我们找到了数 $p$，那么答案其实就是区间 $[L-p,R-p]$ 中是 $\textup{lcm}(a_1,a_2)$ 倍数的数，所以我们的 $p$ 必须是最小正整数解或者干脆是一个负数解，不然的话 $L-p$ 或 $R-p$ 为负数就是一个很麻烦的情况。

比较好做的方法就是让 $p$ 直接成为一个负数解，就是每次暴力减 $\textup{lcm}(a_1,a_2)$ 直至合法即可。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int __int128
using namespace std;
inline int read(){
    int x=0,w=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*w;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

void exgcd(int a,int b,int &x,int &y){
	if(b == 0){
		x = 1,y = 0;
		return;
	}
	exgcd(b,a%b,x,y);
	int xx = x,yy = y;
	x = yy;
	y = xx - (a / b) * yy;
}
int get(int x,int y){
	if(x < 0)	return 0;
	return x / y + 1;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int a1,b1,a2,b2,L,R;
	a1 = read(),b1 = read(),a2 = read(),b2 = read(),L = read(),R = read();
	L = max(L,max(b1,b2));
	int A = a1,B = -a2,C = b2 - b1;
	if(C % __gcd(A,B) != 0){
		printf("0\n");
		return 0;
	}
	int x,y;exgcd(A,B,x,y);
	x *= C/__gcd(A,B);
	int mn = b1 + a1 * x,len = a1 / __gcd(a1,a2) * a2;
	while(L - mn <= 0){
		mn -= len;
	}
	L -= mn,R -= mn;
	if(L > R){
		printf("0\n");
	}
	else{
		write(get(R,len) - get(L-1,len));
	}
	return 0;
}

CF797F Mice and Holes

题目描述：

$n$ 个老鼠，$m$ 个洞，告诉你他们的一维坐标和 $m$ 个洞的容量限制，问最小总距离。

$1 \le n,m \le 5000$。

题目分析：

显然要先将老鼠和洞按照坐标从小到大排序。

首先必然是更靠前的老鼠占据更靠前的洞，也就是说必然是一个前缀的老鼠占据一个前缀的洞，且以后的老鼠不会再占据这个前缀的洞了。

进一步观察对于每一个洞，进这个洞的老鼠必然是某一个区间里的所有老鼠。

所以就可以设 $dp[i][j]$ 表示前 $i$ 个洞有了前 $j$ 只老鼠的最小总距离，设 $S(i,j)$ 表示前 $j$ 只老鼠全去第 $i$ 个洞的距离，转移就是：

$$dp[i][j] = \min_{0 \le k \le c_i} (dp[i-1][j-k] + S(i,j) - S(i,j-k))$$

从 $dp[i-1]$ 转移到 $dp[i]$ 的过程中相当于询问定长区间的 $\min$ 可以直接单调队列优化，复杂度为 $O(nm)$。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5005;
struct node{
	int x,c;
}p[N];
int dp[2][N],s[N],x[N];
bool cmp(node a,node b){
	return a.x < b.x;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++)	scanf("%lld",&x[i]);
	sort(x+1,x+n+1);
	for(int i=1; i<=m; i++)	scanf("%lld%lld",&p[i].x,&p[i].c);
	sort(p+1,p+m+1,cmp);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0] = 0;
	for(int i=1; i<=m; i++){
		int now = i & 1,lst = now ^ 1;
		memset(dp[now],0x3f,sizeof(dp[now]));
		s[0] = 1;
		for(int j=1; j<=n; j++)	s[j] = s[j-1] + abs(x[j] - p[i].x);
		deque<int> q;
		for(int j=0; j<=n; j++){
			while(!q.empty() && dp[lst][q.back()]-s[q.back()] > dp[lst][j] - s[j])	q.pop_back();
			q.push_back(j);
			while(!q.empty() && q.front() < j-p[i].c)	q.pop_front();
			dp[now][j] = dp[lst][q.front()]-s[q.front()]+s[j];
		}
	}
	
	if(dp[m&1][n] > 1ll * 1e17)	printf("-1\n");
	else	printf("%lld\n",dp[m&1][n]);
	return 0;
}

Luogu P9838 挑战 NPC IV

题目描述：

小 R 想为小 H 写一首情诗。他现在想出了 $n$ 个句子，每个句子的优美度分别为 $1, 2 \dots n$。小 R 需要按照一定的顺序将他们组合起来，拼成一首完整的诗。换句话说，小 R 需要重新排列这 $n$ 个句子，形成一个 $1 \sim n$ 的排列 $p_1, p_2\dots p_n$；第 $i$ 行诗句的优美度就是原先第 $p_i$ 个句子的优美度，也就是 $p_i$。

不过，由于小 R 是位 OIer，所以他的文采并不是很稳定。他实际上会严重高估自己诗句的优美程度。若一条诗句在小 R 眼里的优美度为 $x$，那么小 H 认为它的优美度是 $x$ 在二进制表示下最低位的 $1$ 的位置。其中，小 H 认为最低位的位置是 $1$，次低位为 $2$，以此类推。也就是说，小 H 眼中的优美度 $f(x)$ 为 $1 + \log_2 \operatorname{lowbit}(x)$。

小 R 知道，小 H 拿到诗后，只会选取诗的一段来看，而她感受到的优美度是所有她读到的诗句之和。具体的，若诗有 $n$ 句，则小 H 会在 $[1, n]$ 的所有长度 $> 0$ 的区间中抽取一个 $[l, r]$，感受到 $\displaystyle\sum_{l \leq i \leq r}f(p_i)$ 的优美度。小 R 为了衡量一首诗的优美度，决定将一首诗的总优美度定义为 所有情况下小 H 感受到的优美度之和。

照理来说，总优美度最大的组合方式必然是最好的。遗憾的是，在小 R 的精密计算下，他发现，只有他选择总优美度恰好为 第 $k$ 小 的情诗时，他才最有可能和小 H 走到一起。于是，小 R 想要知道，对于 $n!$ 首本质不同的诗，第 $k$ 小可能的总优美度是多少。两首诗本质相同当且仅当原排列 $p_1 \dots p_n$ 相同。

小 R 发现这是一个 NPC 问题，他只好来向你求助了。由于总优美度过于巨大，你只需要帮他求出答案对 $998244353$ 取模后的结果。

特别的，小 R 写了 $q$ 组诗句，所以你需要分别回答他的 $q$ 个问题。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^{18}$，$1 \leq k \leq \min(10^{18}, n!)$，$1 \leq q\le 10$。

题目分析：

不理解这个题为什么评为 省选/NOI−。

首先因为我们算贡献是只在意每一个数的 $\textup{lowbit}$ 所以可以直接将数 $x$ 变成 $1 + \log_2 \textup{lowbit}(x)$ 来考虑这个问题。

这样的话就会发现，对于一个转化后的序列其实是对应很多个转化前的序列的，设 $cnt_i$ 表示 $1 + \log_2 \textup{lowbit}(x) = i$ 的数的个数，则一个序列就代表着 $\prod cnt_i!$ 个原来的序列。

打个表就会发现当 $n \ge 30$ 的时候一个序列就已经代表着超过 $10^{18}$ 个序列，所以这个时候答案必然是最小的那个序列。

显然如果数 $x$ 被放在了位置 $i$ 那么会产生的贡献就是 $x \times i \times (n-i+1)$ 这个贡献是单谷的，并且从中间到两边都是相互对称的，所以最小的答案必然是从中间向两边一点点扩展，每一次放置最小的数，可以直接一次就将 $cnt_i$ 这些数全放了，这样的话差分之后我们就相当于要计算这个式子的值：

$$\sum_{i=1}^n i \times (n-i+1) = (n+1) \sum_{i=1}^n i - \sum_{i=1}^n i^2 = \frac{n(n+1)^2}{2} - \frac{n(n+1)(2n+1)}{6}$$

所以我们就可以以 $O(\log n)$ 的复杂度解决这个问题。

对于 $n \le 29$ 的情况感觉就是一个暴力，但是暴力写出来之后并不行，但是我们也可以发现一个性质就是值域只有 $10^4$ 左右，而且可以使用的数也很少，所以就考虑 $dp$。

设 $dp[a][b][c][d][e][v]$ 表示权值为 $1,2,3,4,5$ 的数分别使用了 $a,b,c,d,e$ 个，当前的权值和为 $v$ 的方案数，当 $n = 29$ 时状态数取得最大约为 $3 \times 10^7$，而转移是 $O(1)$ 的所以可以通过。

现在还有一个问题就是如何计算 $cnt_i$，显然不能每一次暴力跳。如果当前计算有多少位的 $\textup{lowbit} = 2^i$ 那么也就是说所有比第 $i$ 位小的位都可以忽略掉，认为每一次增加 $2^i$，这样就可以转化为计算第 $0$ 位的情况，因此：

$$cnt_i = \left\lceil \frac{\lfloor \frac{n}{2^{i-1}} \rfloor}{2} \right\rceil$$

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
const int MOD = 998244353;
int n,k,cnt[N],pw[N];
int lowbit(int x){
	return x & (-x);
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
int get1(int r){
	r %= MOD;
	return r * (r + 1)%MOD * power(2,MOD-2)%MOD;
}
int get2(int r){
	r %= MOD;
	return r * (r + 1)%MOD * (2 * r + 1)%MOD * power(6,MOD-2)%MOD;
}
int get(int n,int l,int r){
	return ((n+1)%MOD * (get1(r) - get1(l-1) + MOD) % MOD - (get2(r) - get2(l-1))%MOD + MOD)%MOD;
}
void add(int &a,int b){
	a = (a + b) % MOD;
}
namespace brute{
	int tot[N],sum,val[N],fac[N];
	int f[16][9][5][3][2][11005];
	void dfs(int now){
		if(now == n + 1){
			tot[sum]++;
			return;
		}
		for(int i=1; i<=6; i++){
			if(cnt[i]){
				cnt[i]--;
				sum += i * val[now];
				dfs(now+1);
				sum -= i * val[now];
				cnt[i]++;
			}
		}
	}
	void work(){
		f[0][0][0][0][0][0] = 1;
		for(int a=0; a<=cnt[1]; a++){
			for(int b=0; b<=cnt[2]; b++){
				for(int c=0; c<=cnt[3]; c++){
					for(int d=0; d<=cnt[4]; d++){
						for(int e=0; e<=cnt[5]; e++){
							for(int val=0; val<=11000; val++){
								if(!f[a][b][c][d][e][val])	continue;
								int pos = a + b + c + d + e + 1;
								if(a != cnt[1])	add(f[a+1][b][c][d][e][val+pos*(n-pos+1)],f[a][b][c][d][e][val]);
								if(b != cnt[2])	add(f[a][b+1][c][d][e][val+2*pos*(n-pos+1)],f[a][b][c][d][e][val]);
								if(c != cnt[3])	add(f[a][b][c+1][d][e][val+3*pos*(n-pos+1)],f[a][b][c][d][e][val]);
								if(d != cnt[4])	add(f[a][b][c][d+1][e][val+4*pos*(n-pos+1)],f[a][b][c][d][e][val]);
								if(e != cnt[5])	add(f[a][b][c][d][e+1][val+5*pos*(n-pos+1)],f[a][b][c][d][e][val]);
							}
						}
					}
				}
			}
		}
		int ans = 1;
		fac[0] = 1;
		for(int i=1; i<=16; i++)	fac[i] = fac[i-1] * i;
		for(int i=1; i<=5; i++)		ans = ans * fac[cnt[i]];
		for(int i=0; i<=10000; i++){
			tot[i] = f[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][i];
			tot[i] += tot[i-1];
			if(ans * tot[i] >= k){
				printf("%lld\n",i);
				break;
			}
		}	
		for(int a=0; a<=cnt[1]; a++){
			for(int b=0; b<=cnt[2]; b++){
				for(int c=0; c<=cnt[3]; c++){
					for(int d=0; d<=cnt[4]; d++){
						for(int e=0; e<=cnt[5]; e++){
							for(int val=0; val<=11000; val++){
								f[a][b][c][d][e][val] = 0;
							}
						}
					}
				}
			}
		}
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&k);
		pw[0] = 1;
		for(int i=1; i<=61; i++)	pw[i] = pw[i-1] * 2;
		for(int i=1; i<=61; i++){
			cnt[i] = (n / pw[i-1] + 1) / 2;
		}
		if(n <= 29){
			brute::work();
		}
		else{
			int ans = 0;
			int l = (cnt[1] + 1) / 2,r = cnt[1] / 2;
			ans = get(n,(n+1)/2-l+1,(n+1)/2+r);
			for(int i=2; i<=61; i++){
				if(!cnt[i])	continue;
				if(l > r)	++r,add(ans,get(n,(n+1)/2+r,(n+1)/2+r)*i % MOD),--cnt[i];
				if(!cnt[i])	continue;
				int L = (cnt[i] + 1) / 2,R = cnt[i] / 2;
				add(ans,(get(n,(n+1)/2-(l+L)+1,(n+1)/2+(r+R))-get(n,(n+1)/2-l+1,(n+1)/2+r)) * i % MOD);
				l += L;r += R;
			}
			printf("%lld\n",(ans%MOD + MOD)%MOD);
		}
	}
	return 0;
}

CF417D Cunning Gena

题目描述：

Gena 非常想参加“俄罗斯code cup”的决赛，或是至少得到一件T恤。但是比赛的题目太复杂了，所以他安排他的 $n$ 个朋友帮他解决这些问题。

在比赛中会有 $m$ 道题目提供给参赛者。对于每个朋友，Gena 知道他能解决什么问题。但是 Gena 的朋友不会无偿的去帮助 Gena 的，第 $i$ 个朋友会因为帮助 Gena 解决所有他会的问题而向 Gena 索要 $x$ 卢布。并且，只有在 Gena 的电脑连接到至少 $k$ 台显示器时，这个朋友才会去帮助 Gena 写代码。且每台显示器需要花费 $b$ 卢布。

Gena 很节约用钱，所以他希望尽可能少的花钱去解决所有问题。请你帮助 Gena，告诉他怎样花费最少的钱。最初，Gena 的电脑没有连接任何显示器。

$1 \le n \le 100$，$1 \le m \le 20$。

题目分析：

如果我们可以确定连接多少台显示器，那么就类似一个背包问题就比较好做了。

注意到我们最优的连接显示器的数量必然恰好是某个人要求的显示器数量，所以只有 $O(n)$ 种可能，所以可以直接对于每个人按照对于显示器需求的数量从小到大排序，这样的话每一次就相当于新加入一个人，就很好做了。

复杂度 $O(n2^m)$。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 2e18;
const int N = 1005;
struct node{
	int x,k,m,val;
}a[N];
int n,m,b,dp[2][1500005],ans;
bool cmp(node a,node b){
	return a.k < b.k;
}
void chkmin(int &a,int b){
	a = min(a,b);
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&b);
	for(int i=1; i<=n; i++){
		scanf("%lld%lld%lld",&a[i].x,&a[i].k,&a[i].m);
		a[i].val = 0;
		for(int j=1; j<=a[i].m; j++){
			int p;scanf("%lld",&p);
			a[i].val |= (1<<(p-1));
		}
	}
	sort(a+1,a+n+1,cmp);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0] = 0;ans = INF;
	for(int i=0; i<n; i++){
		int now = i & 1,nxt = now ^ 1;
		memset(dp[nxt],0x3f,sizeof(dp[nxt]));
		for(int j=0; j<(1<<m); j++){
			chkmin(dp[nxt][j],dp[now][j]);
			chkmin(dp[nxt][j|a[i+1].val],dp[now][j]+a[i+1].x);
		}
		chkmin(ans,dp[now][(1<<m)-1]+b*a[i].k);
	}
	chkmin(ans,dp[n&1][(1<<m)-1]+b*a[n].k);
	if(ans == INF)	printf("-1\n");
	else	printf("%lld\n",ans);
	return 0;
}

CF226C Anniversary

题目描述：

设 $F$ 是斐波那契数列，在 $[l,r]$ 中选 $k$ 个数 $a_{1}...a_{k}$,使得 $\gcd(F_{a_{1}},F_{a_{2}},...,F_{a_{k}})$ 尽可能大。输出对 $m$ 取模后的结果。

$1 \le l \le r \le 10^{12}$

题目分析：

有一个很神奇的结论就是 $\gcd(F_x,F_y) = F_{\gcd(x,y)}$，所以我们其实只需要选 $k$ 个数使得 $\gcd$ 最大即可。

假设 $\gcd = p$ 那么合法当且仅当，区间中 $p$ 的倍数的个数大于等于 $k$ 个即可，也就是这个式子成立：

$$\left\lfloor \frac{r}{p} \right\rfloor - \left\lfloor \frac{l-1}{p} \right\rfloor \ge k$$

所以可以考虑对于 $r$ 整除分块，假设现在的区间为 $[L,R]$ 那么因为随着 $p$ 的增大 $\left\lfloor \frac{l-1}{p} \right\rfloor$ 递减而我们又需要找到一个最大的 $p$，所以只需要判断一下 $R$ 是否满足条件即可。

然后这样我们就可以找到一个数 $pos$，最大值就是 $F_{pos}$，可以直接矩阵快速幂得到 $F_{pos}$ 的值。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int MOD;
void add(int &a,int b){
	a = (a + b) % MOD;
}
struct Matrix{
	int n,m;
	int a[2][2];
};
Matrix operator * (Matrix a,Matrix b){
	Matrix c;
	c.n = a.n,c.m = b.m;
	for(int i=0; i<c.n; i++){
		for(int j=0; j<c.m; j++){
			c.a[i][j] = 0;
			for(int k=0; k<a.m; k++){
				add(c.a[i][j],a.a[i][k] * b.a[k][j] % MOD);
			}
		}
	}
	return c;
}
int solve(int pos){
	if(pos == 1 || pos == 2)	return 1;
	Matrix a,f,res;
	a.n = 2,a.m = 2;
	a.a[0][0] = 0,a.a[0][1] = 1;
	a.a[1][0] = 1,a.a[1][1] = 1;
	f.n = 1,f.m = 2;
	f.a[0][0] = f.a[0][1] = 1;
	res.n = 2,res.m = 2;
	res.a[0][0] = 1,res.a[0][1] = 0;
	res.a[1][0] = 0,res.a[1][1] = 1;
	int b = pos - 2;
	while(b){
		if(b & 1)	res = res * a;
		a = a * a;
		b >>= 1;
	}
	return (f * res).a[0][1];
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int l,r,k;scanf("%lld%lld%lld%lld",&MOD,&l,&r,&k);
	int ans = 1;
	for(int L=1,R; L<=r; L=R+1){
		R = r / (r / L);
		if(r / R - (l-1) / R >= k)	ans = R;
	}
	printf("%lld\n",solve(ans) % MOD);
	return 0;
}

CF678E Another Sith Tournament

题目描述：

你是一位骑士，与其他 $n-1$ 个骑士同时爱上了 LKJ，所以你们不得不通过决斗的方式来选出谁能最终得到 LKJ。

幸运的是你知道任意骑士 $i$ 击败骑士 $j$ 的概率，你还被推选为组织委员。决斗一开始你需要任意选择两名骑士（包括自己）进行决斗，胜利方继续和你另外选择的一名骑士决斗，直到仅剩一人，最终的胜利者将得到 LKJ。

你非常渴望取得胜利，想知道自己得到 LKJ 的最大概率是多少，注意你是 $1$ 号。

$1 \le n \le 18$

题目分析：

感觉上就是需要 $dp$ 也就是设 $dp[i][S]$ 表示当前考虑了 $S$ 这些骑士胜者为 $i$ 的某些信息。

注意到我们的转移其实类似博弈的过程，也就是我们会选择一个后继里面最优的状态，然后转移到这个状态，所以上文的某些信息就可以理解为最后 $1$ 号获胜的最大概率。

直接做复杂度就是 $O(n^22^n)$，就可以通过了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 19;
double p[N][N];
double dp[1<<19][N];
void chkmax(double &a,double b){
	a = max(a,b);
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			scanf("%lf",&p[i][j]);
		}
		p[i][0] = 1;
	}
	dp[(1<<n)-1][1] = 1;
	for(int S=(1<<n)-1; S>=0; S--){
		for(int i=0; i<=n; i++){
			if(S != 0 && i == 0)	continue;
			for(int j=1; j<=n; j++){
				if((S>>(j-1)) & 1)	continue;
				chkmax(dp[S][i],p[i][j]*dp[S|(1<<(j-1))][i]+p[j][i]*dp[S|(1<<(j-1))][j]);
			}
		}
	}
	printf("%.7f\n",dp[0][0]);
	return 0;
}

CF93E Lostborn

题目描述：

小 Biu 最近喜欢上一款角色扮演游戏，游戏中的每一款武器有 $k$ 个参数 $a_{1},...,a_{k}$ ，并且根据游戏说明，这些参数两两互质。

游戏中的主角为英雄，英雄发起攻击时，造成的伤害不仅与武器有关，还与英雄的力量有关。如果英雄的力量为 $n$ ，那么一次攻击造成的伤害为区间 $[1,n]$ 中不能被武器参数整除的数的个数。

现在小 Biu 获得了一把新的武器装备，他想知道用某个英雄发起攻击时，造成的伤害值为多少。

$1 \le n \le 10^{13}$，$1 \le k \le 100$，$1 \le a_i \le 1000$。

题目分析：

复杂度比较玄学，但是的确跑得很快。

一个感觉就是暴力可以过，因为我们最多选 $15$ 个质数乘起来就超过 $10^{13}$ 了，所以可以直接容斥。

也就是对于选奇数个数的情况为负贡献，对于选偶数个数的情况为正贡献，因为 $\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \rfloor = \lfloor \frac{a}{b \times c} \rfloor$ 所以可以在选择一个数之后直接将 $n$ 变成 $\lfloor \frac{n}{a} \rfloor$ 即可。

将数按从大到小的顺序排序，然后对于 $n$ 比较小的情况直接记忆化就可以通过了。

代码：

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k, a[110], f[102][300010];
int dfs(int now, int x) {
	if (now > k) return x;
	if (x > 300000)
		return dfs(now + 1, x) - dfs(now + 1, x / a[now]);
	if (~f[now][x]) return f[now][x];
	return f[now][x] = dfs(now + 1, x) - dfs(now + 1, x / a[now]);
}
signed main() {
	memset(f, -1, sizeof(f));
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
		cin >> a[i];
	sort(a + 1, a + k + 1, greater<int>());
	cout << dfs(1, n) << endl;
	return 0;
}