做速卖通的素材有哪些网站,网站建设整体设计思路,做药物分析必须知道的网站,企业3合1网站建设价格正题
题目链接:https://ac.nowcoder.com/acm/contest/161/F 题目大意
给出nnn个点的一张图#xff0c;求它的所有生成树中权值和为kkk的倍数的个数。输出答案对ppp取模 1≤n,k≤100,1≤m≤104,p∈[2,109]∩Pri1\leq n,k\leq 100,1\leq m\leq 10^4,p\in[2,10^9]\cap Pri1≤n,…正题
题目链接:https://ac.nowcoder.com/acm/contest/161/F 题目大意
给出nnn个点的一张图求它的所有生成树中权值和为kkk的倍数的个数。输出答案对ppp取模 1≤n,k≤100,1≤m≤104,p∈[2,109]∩Pri1\leq n,k\leq 100,1\leq m\leq 10^4,p\in[2,10^9]\cap Pri1≤n,k≤100,1≤m≤104,p∈[2,109]∩Pri 数据保证k≡1(modp)k\equiv 1(mod\ p)k≡1(mod p) 解题思路
一个想法是把一条边权看做xwx^wxw的多项式用矩阵树定理乘起来后kkk的倍数的系数和就是答案。 但是这样系数是nknknk个显然搞不定。
类似于CF917D-StrangerTree的做法我们可以带入若干个值然后跑矩阵数之后求出若干个点值。
但是这里是kkk的倍数我们要模拟卷积可以带入kkk个ggg满足gk1g^k1gk1的就可以了。
这里保证了k≡1(modp)k\equiv 1(mod\ p)k≡1(mod p)所以我们求出ppp的原根ggg然后带入gp−1k×i(i∈[0,k−1])g^{\frac{p-1}{k}\times i}(i\in[0,k-1])gkp−1×i(i∈[0,k−1])就可以了。
然后直接拉插求出x0x0x0的点值就好了。
时间复杂度O(n3k)O(n^3k)O(n3k) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
using namespace std;
const ll N110;
struct node{ll x,y,w;
}e[N*N];
ll n,m,k,P,g,x[N],y[N];
vectorll p;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void Prime(){ll xP-1;for(ll i2;i*ix;i)if(x%i0){p.push_back(i);while(x%i0)x/i;}if(x1)p.push_back(x);
}
bool check(ll x){for(ll i0;ip.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 ans1;for(ll i1;im;i){ll xe[i].x,ye[i].y,wpower(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 f0;for(ll i1;in;i){for(ll ji;jn;j)if(a[j][i]){if(ij)break;swap(a[i],a[j]);f^1;break;}ansans*a[i][i]%P;ll invpower(a[i][i],P-2);for(ll ji;jn;j)a[i][j]a[i][j]*inv%P;for(ll ji1;jn;j){ll rateP-a[j][i];for(ll ki;kn;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();g1;while(!check(g))g;for(ll i1;im;i)scanf(%lld%lld%lld,e[i].x,e[i].y,e[i].w);for(ll i1;ik;i){x[i]power(g,(P-1)/k*(i-1));y[i]Matrix::det(x[i]);}ll ans0;for(ll i1;ik;i){ll tmp1;for(ll j1;jk;j)if(i!j)tmptmp*(P-x[j])%P*power(x[i]-x[j],P-2)%P;(anstmp*y[i]%P)%P;}printf(%lld\n,(ansP)%P);return 0;
}
