A. Traditional questions

Let the answer be \ (\ sum \ limits {I = 1} ^ NIF (I) \)

\(F(i) \) is the number of schemes with the answer \ (i \)

If you can't find it directly, it can be simply transformed into \ (\ sum \ limits {I = 1} ^ n (m ^ n-f (ANS < I)) \)

Then consider finding \ (\ sum \ limits {I = 1} ^ NF (ANS < I) \ rightarrow \ sum \ limits_ {i=0}^{n-1}F(ans\leq i)\)

The final answer to the enumeration is divided into \ (j \) segments, which are \ (\ sum \ limits {I = 0} ^ n \ sum \ limits {j = 1} ^ nm * (m-1) ^ {j-1} \)

The color of each paragraph is not the same as the previous paragraph, so it is \ (m*(m-1)^{j-1} \)

Then, each scheme shall be multiplied by a scheme number, which means that the sum of \ (j \) numbers less than or equal to \ (i \) is the number of schemes of \ (n \)

If there is no limit, it is \ (\ binom{n-1}{j-1} \) the same board as yesterday

It can be excluded that enumerating a \ (K \) indicates that the number of \ (K \) is greater than \ (i \), then allocate \ (i \) to these numbers first, and then plug in \ (\ sum \ limits {k = 0} ^ J (- 1) ^ k \ binom {J} {K} \ binom {n-ik-1} \)

The formula becomes \ (\ sum \ limits {I = 0} ^ n \ sum \ limits {J = 1} ^ nm * (m-1) ^ {J-1} \ sum \ limits_ {k=0}^j(-1)^k\binom{j}{k}\binom{n-ik-1}{j-1}\)

Lift \ (m \) and \ (K \) to \ (m \ sum \ limits {I = 0} ^ {n-1} \ sum \ limits {k = 1} ^ n (- 1) ^ k \ sum \ limits_ {j=1}^n(m-1)^{j-1}\binom{j}{k}\binom{n-ik-1}{j-1}\)

The next step is to magically change \ (\ binom{n-ik-1}{j-1} \) into \ (\ frac{1}{n-ik}\binom{n-ik}{j}*j \)

Then it is found that the following one becomes \ (\ sum \ limits {UJ = 1} ^ n (m-1) ^ {J-1} \ binom {J} {K} \ binom {n-ik} {J} J \)

Pretend to change his meaning according to a combination

Choose \ (j \) from \ (n-ik \), and then choose a special ball from \ (j \) without dyeing, and the rest are dyed with \ (m-1 \)

Classify and discuss again to see whether the selected non stained balls are inside or outside \ (k \)

1. Inside, select \ (k-1 \) dyed balls and then select a non dyed \ (k(m-1)^{k-1} \), and select a subset of the remaining balls to dye, which is equivalent to using \ (m \) colors to dye, and an additional color is equivalent to not selecting \ (m^{n-ik-k} \)

2. On the outside, dye the inner \ (K \), and the outer subset is the same as the above, and choose another non dyed \ ((m-1)^k(n-ik-k)m^{n-ik-k-1} \)

So \ (f(k,ik)=\sum\limits_{j=1}^n(m-1)^{j-1}\binom{j}{k}\binom{n-ik}{j}j=k(m-1)^{k-1}m^{n-ik-k}+(m-1)^k(n-ik-k)m^{n-ik-k-1}\binom{n-ik}{k}\)

The last combination number represents the \ (k \) you selected in total

Finally it becomes \ (m \ sum \ limits {I = 0} ^ {n-1} \ sum \ limits {k = 1} ^ n (- 1) ^ k \ frac {1} {n-ik} f (k, IK) \)

By limiting the boundary according to \ (k+ik\leq n \), you can achieve \ (O(n\log n) \)

Code

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m,mod,ans,cnt;
int k2[300010];
int fac[300010],ifac[300010],inv[300010];
int Sm[300010],Sm1[300010];
inline int C(int n,int m){return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
inline int qpow(int x,int k){
	int res=1,base=x;
	while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
	return res;
}
inline int calc(int k,int ik){
	int res=0;
	if(k-1>=0&&n-ik-k>=0) res+=k*Sm1[k-1]%mod*Sm[n-ik-k]%mod;
	if(n-ik-k-1>=0&&k>=0) res+=Sm1[k]*(n-ik-k)%mod*Sm[n-ik-k-1]%mod; 
	return res%mod*C(n-ik,k)%mod;
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	n=read(),m=read(),mod=read();
	k2[0]=1;for(int i=1;i<=300000;i++) k2[i]=k2[i-1]*2%mod;
	inv[1]=1;for(int i=2;i<=300000;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	fac[0]=ifac[0]=1;for(int i=1;i<=300000;i++) fac[i]=fac[i-1]*i%mod,ifac[i]=ifac[i-1]*inv[i]%mod;
	Sm[0]=1,Sm1[0]=1;for(int i=1;i<=300000;i++) Sm[i]=Sm[i-1]*m%mod,Sm1[i]=Sm1[i-1]*(m-1)%mod;
	for(int k=0,r=1;k<=n;k++,r=-r) for(int i=0;i<n&&i*k+k<=n;i++) (ans+=r*calc(k,i*k)*inv[n-i*k]%mod+mod)%=mod;
	printf("%lld\n",(n*Sm[n]%mod-m*ans%mod+mod)%mod);
	return 0;
}

B. Spanning tree

Considering the matrix tree theorem, the actual solution is \ (\ sum (edge weight product of spanning tree) \)

Then all your spanning trees are made up of red, green and blue colors. You should limit the selection number of some edges

It's not easy to do it directly according to the restrictions. You can consider calculating the number of spanning trees in all cases

It is equivalent to a total of \ (\ frac{n*(n+1)}{2} \) different variables, so you can enumerate the edge weights of green and blue edges

Then find a matrix tree for each, so you can get the \ (\ frac{n*(n+1)}{2} \) equation, so you can solve the Gauss elimination solution

Then add the answer according to the number of selected edges

Code

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define mod 1000000007
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m,g,b,t,ans;
struct E{int x,y,z;}edge[100010];
int a[50][50];
inline int qpow(int x,int k){
	int res=1,base=x;
	while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
	return res;
}
inline void build(int G,int B){
	memset(a,0,sizeof(a));
	for(int i=1,x,y,z;i<=m;i++){
		x=edge[i].x,y=edge[i].y,z=edge[i].z;
		if(z==1) a[x][x]+=1,a[y][y]+=1,a[x][y]-=1,a[y][x]-=1;
		if(z==2) a[x][x]+=G,a[y][y]+=G,a[x][y]-=G,a[y][x]-=G;
		if(z==3) a[x][x]+=B,a[y][y]+=B,a[x][y]-=B,a[y][x]-=B;
	}
}
inline int solve(){
	int res=1;
	for(int i=2;i<=n;i++) for(int j=i+1,t;j<=n;j++) while(a[j][i]){
		t=a[i][i]/a[j][i];
		for(int k=i;k<=n;k++) a[i][k]=(a[i][k]-t*a[j][k])%mod;
		swap(a[i],a[j]);
		res=-res;
	}
	for(int i=2;i<=n;i++) res=res*a[i][i]%mod;
	return (res+mod)%mod;
}
int mp[1010][1010],lim;
inline void gauss(int n){
	for(int i=1,p,INV;i<=n;i++){
		if(!mp[i][i]) for(int j=i+1;j<=n;j++) if(mp[j][i]){swap(mp[i],mp[j]);break;}
		INV=qpow(mp[i][i],mod-2);
		for(int j=1;j<=n+1;j++) mp[i][j]=mp[i][j]*INV%mod;
		for(int j=1;j<=n;j++){
			if(i==j||mp[j][i]==0) continue;
			INV=mp[j][i]*qpow(mp[i][i],mod-2)%mod;
			for(int k=1;k<=n+1;k++) mp[j][k]=(mp[j][k]-INV*mp[i][k]+mod)%mod;
		}
	}
}
namespace RG{
	signed main(){
		for(int i=1;i<=m;i++) edge[i].x=read(),edge[i].y=read(),edge[i].z=read();
		for(int i=0,p;i<n;i++){
			build(i,0);lim++;p=0;
			for(int k=0;k<n;k++) mp[lim][++p]=qpow(i,k)%mod;
			mp[lim][n+1]=solve();
		}
		gauss(lim);
		for(int k=0,p=0;k<n;k++){p++;if(k<=g) (ans=ans+mp[p][lim+1])%=mod;}
		printf("%lld\n",ans);
		return 0;
	}
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	n=read(),m=read(),g=read(),b=read();if(!b) return RG::main();
	for(int i=1;i<=m;i++) edge[i].x=read(),edge[i].y=read(),edge[i].z=read();
	for(int i=0;i<n;i++) for(int j=0,p;i+j<n;j++){
		build(i,j);lim++;p=0;
		for(int k=0;k<n;k++) for(int l=0;l+k<n;l++) mp[lim][++p]=qpow(i,k)*qpow(j,l)%mod;
		mp[lim][n*(n+1)/2+1]=solve();
	}
	gauss(lim);
	for(int k=0,p=0;k<n;k++) for(int l=0;l+k<n;l++){p++;if(k<=g&&l<=b) (ans=ans+mp[p][lim+1]+mod)%=mod;}
	printf("%lld\n",ans);
	return 0;
}

C. Shortest path

If it's a tree, it's good to do. You can add some divide and conquer directly \ (ntt \)

Now what is given is a base ring tree

So first find the ring according to the routine of the base ring tree, and then do one-sided divide and conquer for each point on the ring to calculate the answer in the subtree

Then consider the contribution between the points on the ring, find one side to break the ring, and find that if it is separated from the middle, the contribution of the left and right parts will not go to that side

So you can divide and conquer, calculate the internal answers of the left and right blocks, take the middle as the division and conquer center each time, and then add an offset

Considering the between the left and right blocks, separate the left and right blocks into \ (4 \) small blocks, labeled \ (1,2,3,4 \) from left to right

Then the contribution of \ (2,3 \) does not cross the ring of \ (1,4 \), and the contribution of these two parts can be obtained by the above divide and conquer method

The contribution of the remaining \ (1,3 \) and \ (2,4 \) is a sub problem, which can also divide and conquer recursion

Finally, the number of all path lengths is counted

Code

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define mod 998244353
#define i2 499122177
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,k,len,L,INV,ans;
int dis[262200],dep[100010],pre[100010];
int r[262200],w[262200];
int siz[100010],mx[100010],rt,S;
int head[100010],ver[200010],to[200010],tot;
int s[100010],num;
vector<int>f[100010];
bool vis[100010],ic[100010];
inline void add(int x,int y){ver[++tot]=y;to[tot]=head[x];head[x]=tot;}
inline int qpow(int x,int k){
	int res=1,base=x%mod;
	while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
	return res;
}
bool findcycle(int x,int fa){
	dep[x]=dep[fa]+1;
	for(int i=head[x];i;i=to[i]){
		int y=ver[i];
		if(y==fa) continue;
		if(!dep[y]){
			pre[y]=x;
			if(findcycle(y,x)) return true;
		}else if(dep[y]<dep[x]){
			int p=x;
			while(p!=y){s[++num]=p;ic[p]=1;p=pre[p];}
			s[++num]=y;ic[y]=1;
			return true;
		}
	}
	return false;
}
inline void ntt(vector<int> &a){
	for(int i=0;i<len;i++) if(i<r[i]) swap(a[i],a[r[i]]);
	for(int d=1,t=len>>1;d<len;d<<=1,t>>=1) for(int i=0;i<len;i+=(d<<1)) for(int j=0;j<d;j++){
		int tmp=w[t*j]*a[i+j+d]%mod;
		a[i+j+d]=(a[i+j]-tmp+mod)%mod;
		a[i+j]=(a[i+j]+tmp)%mod;
	}
}
inline vector<int> polymul(vector<int> f,vector<int> g){
	int l1=f.size(),l2=g.size();for(len=1,L=0;len<=l1+l2;len<<=1,L++);
	for(int i=0;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
	w[0]=1,w[1]=qpow(3,(mod-1)/len);for(int i=2;i<len;i++) w[i]=w[i-1]*w[1]%mod;
	f.resize(len);g.resize(len);
	ntt(f);ntt(g);
	for(int i=0;i<len;i++) f[i]=f[i]*g[i]%mod;
	w[0]=1,w[1]=qpow(w[1],mod-2);for(int i=2;i<len;i++) w[i]=w[i-1]*w[1]%mod;
	ntt(f);INV=qpow(len,mod-2);
	for(int i=0;i<len;i++) f[i]=f[i]*INV%mod;
	return f;
}
inline void polyadd(vector<int> &f,vector<int> g){
	if(f.size()<g.size()) f.resize(g.size());
	for(int i=0;i<g.size();i++) f[i]+=g[i];
}
void getrt(int x,int fa){
	siz[x]=1,mx[x]=0;
	for(int i=head[x];i;i=to[i]){
		int y=ver[i];
		if(y==fa||vis[y]) continue;
		getrt(y,x);
		siz[x]+=siz[y];mx[x]=max(mx[x],siz[y]);
	}
	mx[x]=max(mx[x],S-siz[x]);
	if(mx[x]<mx[rt]) rt=x;
}
void dfs(int x,int fa,int dep,vector<int> &f){
	if(dep>=f.size()) f.resize(dep+1);f[dep]++;siz[x]=1;
	for(int i=head[x];i;i=to[i]){
		int y=ver[i];
		if(y==fa||vis[y]) continue;
		dfs(y,x,dep+1,f);
		siz[x]+=siz[y];
	}
}
void solve(int x){
	vis[x]=1;vector<int> F;
	dfs(x,0,0,F);
	F=polymul(F,F);
	for(int i=0;i<F.size();i++) (dis[i]+=F[i])%=mod;
	for(int i=head[x];i;i=to[i]){
		int y=ver[i];vector<int> G;
		if(vis[y]) continue;
		dfs(y,x,1,G);
		G=polymul(G,G);
		for(int i=0;i<G.size();i++) (dis[i]+=-G[i]+mod)%=mod;
	}
	for(int i=head[x];i;i=to[i]){
		int y=ver[i];
		if(vis[y]) continue;
		S=siz[y];mx[rt=0]=inf;
		getrt(y,0);solve(rt);
	}
}
inline void calcs(int l1,int r1,int l2,int r2,int dist){//l<-mid->r
	int m1=0,m2=0;
	for(int i=l1;i<=r1;i++) m1=max(m1,r1-i+(int)f[i].size());
	for(int i=l2;i<=r2;i++) m2=max(m2,i-l2+(int)f[i].size());
	vector<int> a,b;a.resize(m1);b.resize(m2);
	for(int i=l1;i<=r1;i++) for(int j=0;j<f[i].size();j++) (a[r1-i+j]+=f[i][j])%=mod;
	for(int i=l2;i<=r2;i++) for(int j=0;j<f[i].size();j++) (b[i-l2+j]+=f[i][j])%=mod;
	a=polymul(a,b);
	for(int i=0;i<a.size();i++) (dis[i+dist]+=a[i])%=mod;
}
void solve1(int l,int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	solve1(l,mid);solve1(mid+1,r);
	calcs(l,mid,mid+1,r,1);
}
void solve2(int l1,int r1,int l2,int r2,int dis){
	if(l1==r1) return calcs(l1,r1,l2,r2,dis),void();
	int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1;
	calcs(mid1+1,r1,l2,mid2,dis);
	solve2(l1,mid1,l2,mid2,dis+r1-mid1);
	solve2(mid1+1,r1,mid2+1,r2,dis+mid1-l1+1);
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	n=read(),k=read();bool fg=0;
	for(int i=1,x,y;i<=n;i++){
		x=read(),y=read();
		if(x==y){fg=1;continue;}
		add(x,y),add(y,x);
	}
	if(!fg) findcycle(1,0);else s[++num]=1;
	for(int i=1;i<=num;i++) vis[s[i]]=1;
	for(int i=1,x;i<=num;i++){
		x=s[i];vis[x]=0;
		dfs(x,0,0,f[i]);
		S=siz[x],mx[rt=0]=inf;
		getrt(x,0);solve(rt);
	}
	for(int i=1;i<=n;i++) dis[i]=dis[i]*i2%mod;
	if(num>1){
		solve1(1,num/2);solve1(num/2+1,num);
		if(num&1){
			solve2(1,num/2,num/2+1,num-1,1);
			solve2(num/2+2,num,1,num/2,1);
		}else{
			solve2(1,num/2,num/2+1,num,1);
			solve2(num/2+2,num,1,num/2-1,1);
		}
	}
	for(int i=1;i<=n;i++) ans=(ans+dis[i]*qpow(i,k)%mod)%mod;
	printf("%lld\n",ans*qpow(n*(n-1)/2,mod-2)%mod);
	return 0;
}