题意

给定一张边带权的无向图，求生成树的权值和是 k 的倍数的生成树个数模 p 的值。

\(n\leq 100,k\leq 100,p\mod k=1\)

Sol

看见整除然后 \(p\mod k=1\) ，那么可以套个单位根反演。

我们要求的东西就是:

\(\sum_{E}[k|(\sum_{e\in E}val_e)]\)

单位根反演一套:

\(\frac{1}{k}\sum_{E} \sum_{i=0}^{k-1} w_k^{(\sum_{e\in E}val_e)i}\)

然后又是常规操作:

\(\frac{1}{k}\sum_{i=0}^{k-1}\sum_{E} w_k^{(\sum_{e\in E}val_e)i}\)

\(\frac{1}{k}\sum_{i=0}^{k-1}\sum_{E} \prod_{e\in E} (w_k^{i})^{val_e}\)

把一条边的边权看作 \((w_k^{i})^{val_e}\) 矩阵树定理求一下就做完了。

code:

#include<bits/stdc++.h>

#define Set(a,b) memset(a,b,sizeof(a))

using namespace std;

int mod;

template <typename T> inline void init(T&x){

	x=0;char ch=getchar();bool t=0;

	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;

	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);

	if(t) x=-x;return;

}

typedef long long ll;

template <typename T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;return;}

template <typename T>inline void Dec(T&x,int y){x-=y;if(x <  0) x+=mod;return;}

template <typename T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}

int Sum(int x,int y){x+=y;if(x>=mod) return x-mod;return x;}

int Dif(int x,int y){x-=y;if(x < 0 ) return x+mod;return x;}

const int N=101;

int n,m,k,p,g;

struct edge{

	int u,v,c;

}E[N*N];

namespace Matrix_Tree{

	int a[N][N];

	inline void Build(int w){

		Set(a,0);

		for(int i=1;i<=m;++i) {

			int u=E[i].u,v=E[i].v,c=E[i].c;

			int val=fpow(w,c);

			Dec(a[u][v],val),Dec(a[v][u],val);

			Inc(a[u][u],val),Inc(a[v][v],val);

		}return;

	}

	inline int Gauss(int n){

		int f=0;

		for(int i=1;i<=n;++i) {

			int p=i;

			for(int j=i;j<=n;++j) {if(a[i][j]) {p=j;break;}}

			if(p!=i) f^=1,swap(a[p],a[i]);

			int inv=fpow(a[i][i],mod-2);

			for(int j=i+1;j<=n;++j){

				if(!a[j][i]) continue;

				int t=Dif(0,(ll)a[j][i]*inv%mod);

				for(int k=i;k<=n;++k) Inc(a[j][k],(ll)a[i][k]*t%mod);

			}

		}

		int ret=1;

		for(int i=1;i<=n;++i) ret=(ll)ret*a[i][i]%mod;

		if(f) ret=Dif(0,ret);return ret;

	}

}

inline void Getroot(int mod){

	int x=mod-1;static int pri[50],cnt=0;

	for(int i=2;i*i<=x;++i) if(x%i==0) {pri[++cnt]=i,x/=i;while(x%i==0) x/=i;}

	for(g=2;;++g){bool fl=1;

		for(int i=1;i<=cnt;++i) if(fpow(g,(mod-1)/pri[i])==1) {fl=0;break;}

		if(fl)return;

	}

}

int main()

{

	init(n),init(m),init(k),init(p);

	mod=p;Getroot(mod);int u,v,c;

	for(int i=1;i<=m;++i){init(u),init(v),init(c);E[i]=(edge){u,v,c};}

	int W=fpow(g,(mod-1)/k);

	int w=1,ans=0;

	for(int i=0;i<k;++i,w=(ll)w*W%mod) {

		Matrix_Tree::Build(w);

		Inc(ans,Matrix_Tree::Gauss(n-1));

	}

	ans=(ll)ans*fpow(k,mod-2)%mod;

	cout<<ans<<endl;

	return 0;

}

巴特西

【牛客Wannafly挑战赛23】F 计数

题意

Sol

最新文章

热门文章