【题解】Codeforces Round-711 Virtual

Posted on Edited on In , Comments: Views:

一个马来西亚老哥出的一场Div2，题目还算有点意思，于是就virtual了后三个题。

$C$

给定一段序列，要对着短序列进行涂色。有些位置涂了色，就不能再涂了；没涂色的位置可以涂任意颜色，同一个位置$i$涂不同的颜色$j$有不同的代价。求将整个序列涂成$k$个颜色段的最小代价。

$n,m\leq 100$

一眼$dp$。然后就是设计状态，记$\mathsf {f_{i,j,k}}$表示前$i$个涂成了$j$段，最后一段颜色是$k$的最小代价，暴力转移即可。

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
cin >> N >> M >> K ; 
for (i = 1 ; i <= N ; ++ i) cin >> base[i] ;
for (i = 1 ; i <= N ; ++ i)
	for (j = 1 ; j <= M ; ++ j)
		cin >> val[i][j] ;
for (i = 0 ; i <= N ; ++ i)
	for (j = 0 ; j <= K ; ++ j)
		for (k = 0 ; k <= M ; ++ k)
			dp[i][j][k] = Inf ; 
/*for (i = 1 ; i <= N ; ++ i)
	for (j = i - 1 ; j >= 1 ; -- j)
		if (base[j]) {pos[i] = j + 1 ; break ;}*/
/*for (i = 1 ; i <= N ; ++ i){
	for (j = 1 ; j < i; ++ j)
		if (j >= pos[i]){
			for (k = 1 ; k <= M ; ++ k)
				for (l = 1 ; l <= M ; ++ l)
					for (w = 1 ; w <= K ; ++ w)
						if (l != k) dp[i][w][k] = max(dp[i][w][k], dp[j][w - 1][l] + ) ;
		}
		else {
			
		}
}*/
if (base[1]) dp[1][1][base[1]] = 0 ;
else for (i = 1 ; i <= M ; ++ i) dp[1][1][i] = val[1][i] ;
for (i = 2 ; i <= N ; ++ i){
	for (j = 1 ; j <= K ; ++ j){
		if (!base[i]){
			for (k = 1 ; k <= M ; ++ k){
				dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k] + val[i][k]);
				for (l = 1 ; l <= M ; ++ l)
					if (k != l) 
             dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][l] + val[i][k]) ;
			}
		}
		else{
			dp[i][j][base[i]] = min(dp[i][j][base[i]], dp[i - 1][j][base[i]]) ;
			for (k = 1 ; k <= M ; ++ k )
				if (k != base[i]) 
           dp[i][j][base[i]] = min(dp[i][j][base[i]], dp[i - 1][j - 1][k]) ;
		}
	}
}
for (Ans = Inf, i = 1 ; i <= M ; ++ i) Ans = min(Ans, dp[N][K][i]) ; 
cout << (Ans == Inf ? - 1 : Ans) << endl ; return 0 ;

$D$

有$n$个点和$n$条边，第$i$条边从$i$连到$a_i$ 。

每条边需要指定一个方向（无向边变为有向边）。问有多少种指定方向的方案使得图中不出现环

一道计数题，但是比较睿智。给定的图显然是一堆基环树。那么考虑不在环上的边显然怎么定向都无所谓，在环上的边也只会是恰好都顺时针或者恰好都逆时针不合法。乘法原理乘起来就完了。

好早之前做的题了，然后当时这题卡了半天原因是我忘了怎么dfs找环了……大概就是祖先记一记，树上游一游，就做完了…类似于tarjan？…可海星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline ll expow(int b){
	ll res = 1, base = 2 ;
	while (b){ if (b & 1) res = res * base % Mod ; (base *= base) %= Mod, b >>= 1 ; }
	return res ;
}
void dfs(int u, int deep){
	dep[u] = deep, vis[u] = 1 ;
	for (int k = head[u] ; k ; k = E[k].next){
		if (!vis[to(k)]) dfs(to(k), deep + 1) ;
		else if (vis[to(k)] <= 1) rop[++ tot] = dep[u] - dep[to(k)] + 1 ;
 	}
	vis[u] = 3 ;
}
int main(){
	cin >> N, Ans = 1 ; int qaq ;
	for (i = 1 ; i <= N ; ++ i) scanf("%d", &qaq), Add(i, qaq) ;
	for (i = 1 ; i <= N ; ++ i) if ( !dep[i] ) dfs(i, 1) ; cnt = 0 ;
	for (i = 1 ; i <= tot ; ++ i) 
	    cnt += rop[i], (Ans *= (expow(rop[i]) - 2 + Mod)) %= Mod ;
	Ans = Ans * expow(N - cnt) % Mod ; cout << Ans << endl ; return 0 ;
}

$E$

求一年有$2^n$天，$k$个人出现两人生日相同的可能性是多少。

$n,k\leq 10^{18},\rm Mod=1e6+3$

首先考虑答案就是

然后就变成了如果把这个东西求出来传统艺能.jpg

1、如果$k>P=1e6+3$，那么根据抽屉原理分子中肯定至少有一项$\bmod \rm P=0$。

2、因为分母是$2$的幂，所以最后实际上就是在求分子中有多少个$2$乘起来

3、考虑如何求分子有多少个$2$。考虑一个引理，就是$2^n-m$和$m$中的$2$的个数一样。证明大概就是考虑令$m=2^p\cdot q$，其中$p$为极大的$2$的幂指数，那么$2^n-m=2^n-2^p\cdot q=2^p(2^{n-p}-q)$。根据整除的性质$a|b-c,a|b\Longleftrightarrow a|c$，而$2\not| ~~ q$，所以$2^n-m$中$2$的次数就是$p$.

4、然后由3中的引理，就有一个比较经典的做法。就是我们可以得到

再结合抽屉原理，只需要枚举$2$的幂就可以算了。

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
#include <cstdio>
#include <iostream>

#define Mod 1000003
#define ll long long

using namespace std ; ll Son, Mom ;
ll N, M, Inv, _gcd, qwq, i, base = 1, ans = 1 ;

inline ll expow(ll x, ll y){
	ll res = 1 ;
	while (y){
		if (y & 1) (res *= x) %= Mod ;
		(x *= x) %= Mod, y >>= 1 ;
	}
	return res % Mod ; 
}
int main(){
	cin >> N >> M ;
	for (i = 1 ; i <= N ; ++ i){
		base <<= 1 ; if (base >= M) { ans = 0 ; break ;} 
 	}
 	if (ans) return puts("1 1"), 0 ;  Son = 1 ;
 	for (i = 2 ; i <= M - 1 ; i <<= 1) qwq += (M - 1) / i ;  
	_gcd = expow(2, qwq), 
  Inv = expow(_gcd, Mod - 2) ; 
  Mom = expow(2, N  % (Mod - 1) * (M - 1) % (Mod - 1)) ;
  (Mom *= Inv) %= Mod ; 
  if (M - 1 >= Mod) 
    return printf("%I64d %I64d", Mom, Mom), 0 ; 
	for (i = 1 ; i < M ; ++ i) 
    Son = Son * (expow(2, N) - i + Mod) % Mod ; 
  (Son *= Inv) %= Mod, 
  Son = ((Mom - Son) % Mod + Mod) % Mod ; 
  cout << Son << " " << Mom << endl ; 
}