网站相册代码,wordpress仿豆瓣,我们做网站 出教材 办育心经,word网页 WordPress正题
题目链接:https://www.luogu.com.cn/problem/P4321 题目大意
给出nnn个点mmm条边的一张无向图#xff0c;qqq次询问。
每次询问给出一个点集和一个起点#xff0c;求从起点出发随机游走经过所有点集的期望步数。 n∈[1,18],m∈[1,n(n−1)2],q∈[1,105]n\in[1,18],m\i…正题
题目链接:https://www.luogu.com.cn/problem/P4321 题目大意
给出nnn个点mmm条边的一张无向图qqq次询问。
每次询问给出一个点集和一个起点求从起点出发随机游走经过所有点集的期望步数。
n∈[1,18],m∈[1,n(n−1)2],q∈[1,105]n\in[1,18],m\in[1,\frac{n(n-1)}{2}],q\in[1,10^5]n∈[1,18],m∈[1,2n(n−1)],q∈[1,105] 解题思路
首先nnn很小可以状压经过点的状态然后因为这个询问是给出起始状态所以需要倒推。设fs,xf_{s,x}fs,x表示目前状态是sss在点xxx覆盖所有点的期望次数。
那么有方程 fS,x∑x−yfS∩y,yf_{S,x}\sum_{x-y}f_{S\cap y,y}fS,xx−y∑fS∩y,y
然后SSS不同的当常数相同的高斯消元转移即可。
时间复杂度O(2nn3)O(2^nn^3)O(2nn3) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N19,M1e510,P998244353;
ll n,m,q,inv[M],deg[N],a[N][N],f[1N][N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
namespace G{ll a[N][N],b[N];void clear(){memset(a,0,sizeof(a));memset(b,0,sizeof(b));return;}void solve(ll *f){for(ll i1;in;i){ll pi;for(ll ji;jn;j)if(a[j][i]){pj;break;}swap(a[i],a[p]);swap(b[i],b[p]);ll invpower(a[i][i],P-2);for(ll ji;jn;j)a[i][j]a[i][j]*inv%P;b[i]b[i]*inv%P;for(ll ji1;jn;j){int rateP-a[j][i];for(ll ki;kn;k)a[j][k](a[j][k]a[i][k]*rate%P)%P;b[j](b[j]b[i]*rate%P)%P;}}for(ll in;i1;i--){for(ll ji1;jn;j)b[i](b[i]-a[i][j]*b[j]%PP)%P;f[i]b[i];}return;}
}
signed main()
{scanf(%lld%lld,n,m);inv[1]1;for(ll i2;im;i)inv[i]P-(P/i)*inv[P%i]%P;for(ll i1;im;i){ll x,y;scanf(%lld%lld,x,y);a[x][y];a[y][x];deg[x];deg[y];}ll MS(1n);for(ll sMS-2;s0;s--){G::clear();for(ll i1;in;i)if((si-1)1)G::a[i][i]P-1,G::b[i]P-1;for(ll i1;in;i){if(!((si-1)1))continue;for(ll j1;jn;j){if(!a[i][j])continue;if((s|(1j-1))s)(G::a[i][j]inv[deg[i]])%P;else (G::b[i]P-inv[deg[i]]*f[s|(1j-1)][j]%P)%P;}}G::solve(f[s]);}scanf(%lld,q);while(q--){ll m,s0,x;scanf(%lld,m);for(ll i1;im;i)scanf(%lld,x),s|(1x-1);scanf(%lld,x);printf(%lld\n,f[(MS-1-s)|(1x-1)][x]);}return 0;
}
