Codeforces Round-711 Virtual

一个马来西亚老哥出的一场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$

首先考虑答案就是
$$
\frac{\prod\limits_{i=2^n-k+1}^{2^n-1}i}{2^{n \cdot {k-1}}}
$$
然后就变成了如果把这个东西求出来传统艺能.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中的引理,就有一个比较经典的做法。就是我们可以得到
$$
\begin{aligned}
(\prod\limits_{i=2^n-k+1}^{2^n-1}i,2^n)&=(\prod\limits_{i=2^n-k+1}^{2^n-1}(2^n-i), 2^n)\ &=(\prod\limits_{i=1}^{k}i,2^n)\ &=(k!,2^n)
\end{aligned}
$$

再结合抽屉原理,只需要枚举$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 ;
}