\quad题目大意：无向图有n个点m条边，人物初始level为0，初始在1号点，图上点有两种类型点0和1,遇到0会level++，遇到1会收益 += level2level^2level2，求k步内的收益期望(n<=3000,m<=3000)
\quadSolution:
\quad一般期望题先考虑倒推，但是此题终态有点难定义（好像也有倒退做法）。考虑从定义角度入手。
\quad观察一种走法，设w为一种走法线路，f(w)表示走法的收益,f(w)=∑i=1lenXi2f(w) = \sum_{i=1}^{len}X_i^2f(w)=∑i=1len​Xi2​，其中XiX_iXi​表示到i点的等级,而Xi=∑j=1i[cj=0],所以Xi2=∑j=1i∑k=ji[cj=0andck=0]X_i = \sum_{j=1}^i[c_j=0],所以X_i^2=\sum_{j=1}^i\sum_{k=j}^i[c_j=0 \quad and \quad c_k=0]Xi​=∑j=1i​[cj​=0],所以Xi2​=∑j=1i​∑k=ji​[cj​=0andck​=0],c表示点的类型。期望的计算E(w)=f(w)∗∏u=1len−11deg(u)=∑u=1lenXu2∗∏v=1u−11deg(v)=∑u=1len∏v=1u−11deg(v)∗∑j=1u∑k=ju[cj==0&&ck=0]E(w)=f(w)*\prod_{u=1}^{len-1} \frac{1}{deg(u)} = \sum_{u=1}^{len}X_u^2 * \prod_{v=1}^{u-1}\frac{1}{deg(v)} = \sum_{u=1}^{len} \prod_{v=1}^{u-1}\frac{1}{deg(v)} *\sum_{j=1}^u \sum_{k=j}^u[c_j==0 \&\&c_k=0]E(w)=f(w)∗∏u=1len−1​deg(u)1​=∑u=1len​Xu2​∗∏v=1u−1​deg(v)1​=∑u=1len​∏v=1u−1​deg(v)1​∗∑j=1u​∑k=ju​[cj​==0&&ck​=0],其中deg(u)表示u点出度,这样一来就转化成计数问题了。
\quad可以用dp来计数,dpi,j,0/1,0/1dp_{i,j,0/1,0/1}dpi,j,0/1,0/1​表示走j步到了i点，上面那个柿子，点对类型为(0/1,0/1)的求和。
\quad转移的话，这里贴个代码吧，感觉更清楚
复杂度O(n∗max(n,m))O(n*max(n,m))O(n∗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的时候，转移有限制。
\quad答案就是∑i=1n∑j=1kdpi,j,1,1\sum_{i=1}^n\sum_{j=1}^kdp_{i,j,1,1}∑i=1n​∑j=1k​dpi,j,1,1​
（代码写的dp[j][i][1/0][1/0]，前两维反了一下，懒得改了

完整代码

int c[N],i_du[N];
std::vector 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);}//起点在1f[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<