网络营销案例分析1000字,在线排名优化,wordpress无法开启多站点,代理网页是干什么的正题
题目链接:https://www.luogu.com.cn/problem/P6803 题目大意
给出一棵nnn个点的树#xff0c;把它复制出D1D1D1层#xff0c;编号为[0,D][0,D][0,D]#xff0c;然后每一层随机一个点向下一层随机一个点连边。
然后从第000层的111号点出发#xff0c;两个人轮流操作…正题
题目链接:https://www.luogu.com.cn/problem/P6803 题目大意
给出一棵nnn个点的树把它复制出D1D1D1层编号为[0,D][0,D][0,D]然后每一层随机一个点向下一层随机一个点连边。
然后从第000层的111号点出发两个人轮流操作走向一个之前没有走过的点求有多少种连边方案使得先手必胜。
1≤n≤105,1≤D≤10181\leq n\leq 10^5,1\leq D\leq 10^{18}1≤n≤105,1≤D≤1018 解题思路
我们先只考虑连到下一层的那个点是必胜还是必败的。
显然连接的下一层的点如果是必胜的那么局面不会有任何改变。而如果连接的是必败的点那么原本必败的情况就会变成必胜的情况。
考虑对于每个点算出Gx,0/1G_{x,0/1}Gx,0/1表示从xxx出发的情况如果连接的下层点必败这一层有多少种连边情况会先手必胜/先手必败。
这个东西虽然比较麻烦但是可以通过换根dpdpdp求出。
然后把所有点的求个和得到S0,0/1S_{0,0/1}S0,0/1表示下一层连接先手必败的点这一层得到胜/负的方案。
同样的通过每一个点为根时树的胜负情况得到S1,0/1S_{1,0/1}S1,0/1表示下一层连接先手必胜的点局面不会改变这一层得到胜/负的方案。
这样做DDD层我们就可以直接矩阵乘法了。
时间复杂度O(nlogD)O(n\log D)O(nlogD) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
using namespace std;
const ll N1e510,S2,P1e97;
struct Matrix{ll a[S][S];
}s,ans,c;
Matrix operator*(const Matrix a,const Matrix b){memset(c.a,0,sizeof(c.a));for(ll i0;iS;i)for(ll j0;jS;j)for(ll k0;kS;k)(c.a[i][j]a.a[i][k]*b.a[k][j]%P)%P;return c;
}
struct node{ll to,next;
}a[N1];
ll n,d,tot,ls[N],g[N][2];
bool f[N];vectorll q[N];
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){ll p0;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);f[x]|!f[y];if(!f[y])p(p?-1:y);g[x][1]g[y][0];g[x][0]g[y][1];}if(p-1)g[x][1]g[x][0];else if(p0)g[x][1]g[x][0]-g[p][1];if(p-1)g[x][0]0;else if(p0)g[x][0]g[p][1];g[x][1];return;
}
void solve(ll x,ll fa,ll p,ll s0,ll s1){if(!p)q[x].push_back(fa);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;if(!f[y]q[x].size()3)q[x].push_back(y);s0g[y][1];s1g[y][0];}if(!q[x].size())p0;else if(q[x].size()1)pq[x][0];else p-1;int pg0g[x][0],pg1g[x][1];g[x][0]s0,g[x][1]s1;if(p-1)g[x][1]g[x][0],g[x][0]0;else if(p0)g[x][1]g[x][0]-g[p][1],g[x][0]g[p][1];g[x][1];ll _f(p?1:0);ans.a[0][_f];s.a[0][0]g[x][0];s.a[0][1]g[x][1];s.a[1][0](!_f)*n;s.a[1][1]_f*n;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;if(!q[x].size())p0;else if(q[x].size()1){if(q[x][0]y)p0;else pq[x][0];}else if(q[x].size()2){if(q[x][0]y)pq[x][1];else if(q[x][1]y)pq[x][0];else p-1;}else p-1;g[x][0]s0-g[y][1];g[x][1]s1-g[y][0];if(p-1)g[x][1]g[x][0],g[x][0]0;else if(p0)g[x][1]g[x][0]-g[p][1],g[x][0]g[p][1];g[x][1];solve(y,x,p?1:0,g[x][1],g[x][0]);}g[x][0]pg0;g[x][1]pg1;return;
}
signed main()
{scanf(%lld%lld,n,d);for(ll i1,x,y;in;i){scanf(%lld%lld,x,y);
// xi1;y(i1)/2;addl(x,y);addl(y,x);}dfs(1,0);ll Ag[1][1];solve(1,0,1,0,0);s.a[0][0]%P;s.a[0][1]%P;s.a[1][0]%P;s.a[1][1]%P;d--;while(d){if(d1)ansans*s;ss*s;d1;}ll answerA*ans.a[0][0]%P;(answerf[1]*n*ans.a[0][1]%P)%P;printf(%lld\n,answer);return 0;
}
