AtCoder Beginner Contest 277 G（概率dp+计数）

\quad 题目大意：无向图有n个点m条边，人物初始level为0，初始在1号点，图上点有两种类型点0和1,遇到0会level++，遇到1会收益 += $leve{l}^2$，求k步内的收益期望(n<=3000,m<=3000)
\quad Solution:
\quad 一般期望题先考虑倒推，但是此题终态有点难定义（好像也有倒退做法）。考虑从定义角度入手。
\quad 观察一种走法，设w为一种走法线路，f(w)表示走法的收益,$f(w)={\sum }_{i=1}^{len}{X}_i^2$，其中$X_i$表示到i点的等级,而$X_i={\sum }_{j=1}^i[c_j=0],所以X_i^2={\sum }_{j=1}^i{\sum }_{k=j}^i[c_j=0and{c}_k=0]$,c表示点的类型。期望的计算$E(w)=f(w)\ast {\prod }_{u=1}^{len-1}\frac{1}{deg(u)}={\sum }_{u=1}^{len}{X}_u^2\ast {\prod }_{v=1}^{u-1}\frac{1}{deg(v)}={\sum }_{u=1}^{len}{\prod }_{v=1}^{u-1}\frac{1}{deg(v)}\ast {\sum }_{j=1}^u{\sum }_{k=j}^u[c_j==0\&\&c_k=0]$,其中deg(u)表示u点出度,这样一来就转化成计数问题了。
\quad 可以用dp来计数,$d{p}_{i,j,0/1,0/1}$表示走j步到了i点，上面那个柿子，点对类型为(0/1,0/1)的求和。
\quad 转移的话，这里贴个代码吧，感觉更清楚
复杂度$O(n\ast max(n,m))$

_for(i,0,k-1){
        _for(j,1,n){
            for(int u:G[j]){
                for(int a=0 ;a<2 ;a++){
                    for(int b=0 ;b<2 ;b++){
                        for(int na=a; na<2 ;na++){
                            for(int nb=b ; nb<2 ;nb++){
                                //下一步c[u]=1的话,na,nb不能变
                                if( c[u] && (na!=a || nb!=b) ) continue;
                                f[i+1][u][na][nb] = (f[i+1][u][na][nb] + i_du[j]*f[i][j][a][b]%mod)%mod;
                            }
                        }   
                    }
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

下一个点类型为1的时候，转移有限制。
\quad 答案就是${\sum }_{i=1}^n{\sum }_{j=1}^{k}d{p}_{i,j,1,1}$
（代码写的dp[j][i][1/0][1/0]，前两维反了一下，懒得改了

完整代码

int c[N],i_du[N];
std::vector<int> G[N];
int f[N][N][2][2];
//第i步，到j的概率和，[0/1][0/1]，表示点对(x,y)
ll qsm(int a,int b){
    ll ans = 1 , tmp = a;
    while( b ){
        if( b&1 ) ans = ans * tmp%mod;
        tmp = tmp * tmp%mod;
        b>>=1;
    }
    return ans;
}
signed main(){ 
    IOS;
    int n,m,k;cin>>n>>m>>k;
    _for(i,1,m){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    _for(i,1,n) {
        cin>>c[i];
        i_du[i] = qsm((int)G[i].size(),mod-2);
    }
    //起点在1
    f[0][1][0][0] = 1;
    //枚举前i步
    _for(i,0,k-1){
        _for(j,1,n){
            for(int u:G[j]){
                for(int a=0 ;a<2 ;a++){
                    for(int b=0 ;b<2 ;b++){
                        for(int na=a; na<2 ;na++){
                            for(int nb=b ; nb<2 ;nb++){
                                //下一步c[u]=1的话,na,nb不能变
                                if( c[u] && (na!=a || nb!=b) ) continue;
                                f[i+1][u][na][nb] = (f[i+1][u][na][nb] + i_du[j]*f[i][j][a][b]%mod)%mod;
                            }
                        }   
                    }
                }
            }
        }
    }
    int ans = 0;
    _for(i,1,k){
        _for(j,1,n) if(c[j]) ans = (ans + f[i][j][1][1])%mod;
    }
    cout<<ans<<endl;
}   
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