建立网站需要多少钱?,h网站开发,精准营销软件,西安响应式网站设计正题
题目链接:https://www.luogu.com.cn/problem/P7293 题目大意
有kkk张联通无向图#xff0c;有kkk个人从每张图的点111出发#xff0c;定义所有人的位置合为一个状态#xff0c;求初始状态到达所有能到达状态的最短时间的和。
输出答案对 109710^971097 取模。 ∑n≤…正题
题目链接:https://www.luogu.com.cn/problem/P7293 题目大意
有kkk张联通无向图有kkk个人从每张图的点111出发定义所有人的位置合为一个状态求初始状态到达所有能到达状态的最短时间的和。
输出答案对 109710^971097 取模。
∑n≤105,∑m≤2×105\sum n\leq 10^5,\sum m\leq 2\times 10^5∑n≤105,∑m≤2×105 解题思路
因为可以反复横跳对于每个点我们求出到达的最短的奇数/偶数距离记为dis1/dis2dis1/dis2dis1/dis2。
那么对于一个状态(i1,i2,...,in)(i_1,i_2,...,i_n)(i1,i2,...,in)答案就是 min{max{dis1ij},max{dis2i,j}}\min\{\ \max\{dis1_{i_j}\},\max\{dis2_{i,j}\}\ \}min{ max{dis1ij},max{dis2i,j} }
然后这个又有min\minmin又有max\maxmax的很难搞但是我们有一个式子abmax{a,b}min{a,b}ab\max\{a,b\}\min\{a,b\}abmax{a,b}min{a,b}好像很废话然后就有min{a,b}ab−max{a,b}\min\{a,b\}ab-\max\{a,b\}min{a,b}ab−max{a,b}这样就把max\maxmax消掉了。
那么答案有 max{dis1ij}max{dis2ij}−max{dis1ij,dis2ij}\max\{dis1_{i_j}\}\max\{dis2_{i_j}\}-\max\{dis1_{i_j},dis2_{i_j}\}max{dis1ij}max{dis2ij}−max{dis1ij,dis2ij}
然后跑出dis1,dis2dis1,dis2dis1,dis2排个序就很好统计了。
注意不能统计上无法达到的状态。
时间复杂度O(NlogNM)O(N\log NM)O(NlogNM) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includequeue
#define mp(x,y) make_pair(x,y)
#define ll long long
using namespace std;
const ll N2e510,P1e97;
struct node{ll to,next;
}a[N2];
ll k,n,m,ans,tot,ls[N],c[N],dis[N];
vectorpairll,ll b[3];
queuell q;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void bfs(){q.push(1);dis[1]1;while(!q.empty()){ll xq.front();q.pop();for(ll ils[x];i;ia[i].next){ll ya[i].to;if(dis[y]dis[x]1)continue;dis[y]dis[x]1;q.push(y);}}return;
}
void calc(ll id,ll op){ll res0,now0;memset(c,0,sizeof(c));for(ll i0;ib[id].size();i){ll db[id][i].first,pb[id][i].second;if(d1dis[0])break;now!c[p];c[p];ll invnpower(c[p],P-2);if(nowk){res1;for(int i1;ik;i)resres*c[i]%P;}resres*invn%P;(ansres*d*op%P)%P;resres*c[p]%P;}return;
}
signed main()
{scanf(%lld,k);for(ll i0;iN;i)dis[i]2147483647;for(ll p1;pk;p){scanf(%lld%lld,n,m);for(ll i1,x,y;im;i){scanf(%lld%lld,x,y);addl(x,yn);addl(xn,y);addl(y,xn);addl(yn,x);}bfs();for(ll i1;in;i){b[0].push_back(mp(dis[i]-1,p));b[1].push_back(mp(dis[in]-1,p));b[2].push_back(mp(max(dis[i],dis[in])-1,p));}for(ll i1;i2*n;i)ls[i]0,dis[i]dis[0];tot0;}sort(b[0].begin(),b[0].end());sort(b[1].begin(),b[1].end());sort(b[2].begin(),b[2].end());calc(0,1);calc(1,1);calc(2,-1);printf(%lld\n,(ansP)%P);return 0;
}
