Fork me on GitHub

[概率论][DP]CF1511E

第一次接触这样的$trick$记录一下吧

题目链接

发现如果在没有黑色格子的情况下能直接DP,但是在有黑色格子的情况下统计答案比较麻烦,所以考虑一种新的$trick$.

我们考虑期望,可以把这总共的$2^\omega$种情况的期望$E$算出来,然后最后的答案就是$2^\omega \times E$. 所以现在的问题变成了怎么求$E$.
然后我们又发现在期望的条件下,横着和竖着放的格子是互不影响的,所以可以分别计算横着放和竖着放多米诺骨牌的贡献.
然后考虑一个式子$E=\sum_{d \in D} e_d$,其中$D$是所有能放多米诺骨牌的格子的位置.根据期望的可加性,每个格子期望能被多少个多米诺骨牌覆盖的期望之和就是这整个棋盘的期望.而且由于一个多米诺骨牌会覆盖两个格子,所以我们记每个格子的期望为以这个格子为左/右或者上/下端点的多米诺骨牌的期望数,这样每个格子最多只能放一个以它为端点的多米诺骨牌,那么期望就是$1 \times p$即$e_d=p_d$,我们只需要求出每个格子能放多米诺骨牌的概率即可.. 然后我们考虑一段连续的白色格子,以横着为例,如果我们想要放至少一个多米诺骨牌,那么这一段连续的白色格子中就至少有连续的两个红色的格子,这里我们假设每个枚举到的格子都是多米诺骨牌的右端点,那么在这个我们枚举到的白色的格子之前至少要有一个连续的白色格子,这个时候我们枚举到的这个格子能放多米诺骨牌的概率就是$\frac{1}{4}$,接着我们来考虑这个枚举的格子之前有$2,3,…,n$个连续的白色格子的情况.
我们发现当前边有两个连续的白色格子时,那么概率就是$P_2=\frac{1}{4}-\frac{1}{8}$为最后两个格子都为红色,第一个不为红色的概率.同理,当之前有三个连续的白色格子时,我们需要这四个都是白色的格子,那么概率$P=\frac{1}{2}-\frac{1}{4}+\frac{1}{8}$以此类推,我们可以递推出每个格子可以放的多米诺骨牌的期望数量.

然后因为横竖是分开的,所以我们分开递推横竖然后把答案相加即可.-

代码:

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
const int P = 998244353;

int n , m , p[N] , w , ans;
char s[N];
string mp[N];

inline int ksm ( int x , int y ) {
int res = 1;
while ( y ) {
if ( y & 1 )
res = ( res * x ) % P;
x = ( x * x ) % P;
y >>= 1;
}
return res % P;
}
inline int inv ( int x ) {
return ksm ( x , P - 2 );
}

signed main ( void ) {
scanf ( "%lld%lld" , &n , &m );
for ( int i = 0 ; i < n ; i++ ) {
scanf ( "%s" , s );
mp[i] = s;
}
for ( int i = 0 ; i < n ; i++ )
for ( int j = 0 ; j < m ; j++ )
if ( mp[i][j] != '*' )
w++;
for ( int i = 2 ; i <= max ( n , m ) ; i++ ) {
if ( i & 1 )
p[i] = ( p[i - 1] + P - inv ( ksm ( 2 , i ) ) ) % P;
else
p[i] = ( p[i - 1] + inv ( ksm ( 2 , i ) ) ) % P;
}
for ( int i = 0 ; i < n ; i++ ) {
int c = 0;
for ( int j = 0 ; j < m ; j++ ) {
if ( mp[i][j] == '*' )
c = 0;
else
ans = ( ans + p[++c] ) % P;
}
}
for ( int j = 0 ; j < m ; j++ ) {
int c = 0;
for ( int i = 0 ; i < n ; i++ ) {
if ( mp[i][j] == '*' )
c = 0;
else
ans = ( ans + p[++c] ) % P;
}
}
unsigned long long ansl = ksm ( 2 , w ) % P;
printf ( "%u\n" , 1ull * ansl * ans % P );
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[概率论][DP]CF1511E

文章作者:兮水XiShui丶

发布时间:2021年04月21日 - 18:04

最后更新:2021年04月22日 - 10:04

原始链接:http://krrrr.top/2021/04/21/概率论-DP-CF1511E/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。