个人电脑做网站服务器网站,网站建设术语 英文,系统优化的方法举例,制作网站收费正题
题目链接:https://www.luogu.org/problemnew/show/P2579 题目大意
一张无向图#xff0c;一个起点一个终点。
有食人鱼#xff0c;在若干个点之间有周期的移动#xff0c;周期为222或333或444个点为循环。
然后要求从起点到终点走kkk步且不碰到食人鱼的方案数。 解…正题
题目链接:https://www.luogu.org/problemnew/show/P2579 题目大意
一张无向图一个起点一个终点。
有食人鱼在若干个点之间有周期的移动周期为222或333或444个点为循环。
然后要求从起点到终点走kkk步且不碰到食人鱼的方案数。 解题思路
因为食人鱼的周期为222或333或444所以显然所有食人鱼的周期为lcm(2,3,4)12lcm(2,3,4)12lcm(2,3,4)12一个循环。 然后kkk很大显然矩阵乘法。
转移矩阵G(k)G(k)G(k)中[i,j][i,j][i,j]表示在第kkk个时刻是否可以从iii移动到jjj。需要考虑连边和食人鱼具体分析。
构建好转移矩阵后G(k)G(k)G(k)我们开始转移我们发现如果不考虑快速幂转移那么 AnsG(1)∗G(2)∗G(3)...∗G(12)∗G(1)∗G(2)...∗G(k%12)AnsG(1)*G(2)*G(3)...*G(12)*G(1)*G(2)...*G(k\%12)AnsG(1)∗G(2)∗G(3)...∗G(12)∗G(1)∗G(2)...∗G(k%12) 中间有⌊k12⌋\lfloor \frac{k}{12}\rfloor⌊12k⌋个G(1)∗G(2)∗G(3)∗...G(12)G(1)*G(2)*G(3)*...G(12)G(1)∗G(2)∗G(3)∗...G(12)
那么我们让GsumG(1)∗G(2)∗G(3)...∗G(12)GsumG(1)*G(2)*G(3)...*G(12)GsumG(1)∗G(2)∗G(3)...∗G(12)
然后十分显然 AnsGsum⌊k12⌋∗∏i1k%12G(i)AnsGsum^{\lfloor \frac{k}{12}\rfloor}*\prod_{i1}^{k\%12}G(i)AnsGsum⌊12k⌋∗i1∏k%12G(i) 然后用AnsAnsAns矩阵计算答案即可。 codecodecode
#includecstdio
#includealgorithm
#includecstring
using namespace std;
const int Size60,T12,XJQ10000;
struct matrix{int a[Size][Size];
}ans,f[T];
int n,m,s,e,k,Nfish;
matrix operator *(matrix a,matrix b)
{matrix c;memset(c.a,0,sizeof(c.a));for(int i0;iSize;i)for(int j0;jSize;j)for(int k0;kSize;k)(c.a[i][j]a.a[i][k]*b.a[k][j]%XJQ)%XJQ;return c;
}
void power(int b)
{matrix Ff[0];for(int i1;iT;i)FF*f[i];while(b){if(b1) ansans*F;FF*F;b1;}
}
int main()
{scanf(%d%d%d%d%d,n,m,s,e,k);for(int i1;im;i){int x,y;scanf(%d%d,x,y);for(int i0;iT;i)f[i].a[x][y]f[i].a[y][x]1;}scanf(%d,Nfish);for(int i1;iNfish;i){int op,x,last;scanf(%d,op);for(int j0;jop;j){scanf(%d,x);for(int kj;kT;kop){int nowk-1;if(now0) nowT-1; for(int i0;in;i)f[now].a[i][x]0;}}}ans.a[0][s]1;power(k/T);for(int i0;ik%T;i)ansans*f[i];printf(%d,ans.a[0][e]);
}
