admin 管理员组

文章数量: 887021

计数

小O有一个n个点，m条边的边带权无向图。小O希望从这m条边中，选出一些边，使得这些边能构成这n个点的生成树。但他还有个幸运数字k。因此他希望最终选出来的这些边的权值和是k的倍数。他想知道最终有多少种可能的方案选出合法的生成树。答案可能很大，幸好小O还有一个幸运质数p。你只需要输出答案对p取模即可。
输入描述:
第一行四个个整数n, m, k, p。
接下来m行，每行三个整数u,v,c，代表这条边连接u,v两点，边权为c。点标号为1到n。
数据保证1 ≤ n,k ≤ 100, 0 ≤ m ≤ 10000, 1 ≤ u,v ≤ n, 0 ≤ c < k。p是质数且p mod k = 1，且p ≤ 109。

输出描述:
一行一个整数代表方案数对p取模的值。
示例1
输入
5 10 4 60661
4 2 2
2 1 1
4 3 3
1 5 0
2 5 0
2 1 1
2 3 3
3 4 3
4 1 1
3 5 0
输出
14

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=110;
struct node
{ll x,y,w;
}e[N*N];
ll n,m,k,P,g,x[N],y[N];
vector<ll> p;
ll power(ll x,ll b)
{ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans;
}
void Prime()
{ll x=P-1;for(ll i=2;i*i<=x;i++)if(x%i==0){p.push_back(i);while(x%i==0)x/=i;}if(x>1)p.push_back(x);
}
bool check(ll x)
{for(ll i=0;i<p.size();i++)if(power(x,(P-1)/p[i])==1)return 0;return 1;
}
namespace Matrix
{ll a[N][N];ll det(ll v){memset(a,0,sizeof(a));ll ans=1;for(ll i=1;i<=m;i++){ll x=e[i].x,y=e[i].y,w=power(v,e[i].w); (a[x][y]+=P-w)%=P;(a[y][x]+=P-w)%=P;(a[x][x]+=w)%=P;(a[y][y]+=w)%=P;}ll f=0;for(ll i=1;i<n;i++){for(ll j=i;j<n;j++)if(a[j][i]){if(i==j)break;swap(a[i],a[j]);f^=1;break;}ans=ans*a[i][i]%P;ll inv=power(a[i][i],P-2);for(ll j=i;j<n;j++)a[i][j]=a[i][j]*inv%P;for(ll j=i+1;j<n;j++){ll rate=P-a[j][i];for(ll k=i;k<n;k++)(a[j][k]+=rate*a[i][k])%=P;}}return f?(P-ans):ans;}
}
signed main()
{scanf("%lld%lld%lld%lld",&n,&m,&k,&P);Prime();g=1;while(!check(g)) g++;for(ll i=1;i<=m;i++) scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].w);for(ll i=1;i<=k;i++){x[i]=power(g,(P-1)/k*(i-1));y[i]=Matrix::det(x[i]);}ll ans=0;for(ll i=1;i<=k;i++){ll tmp=1;for(ll j=1;j<=k;j++)if(i!=j)tmp=tmp*(P-x[j])%P*power(x[i]-x[j],P-2)%P;(ans+=tmp*y[i]%P)%=P;}printf("%lld\n",(ans+P)%P);return 0;
}

本文标签： 计数

版权声明：本文标题：计数 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1688131973h183044.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。