看起来像个裸矩乘。。
但是题目中有这样一句话：
但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。
以点作为状态的算法很难处理这个条件，我们考虑以边作为状态。
只要在建矩阵的时候判断一下，不要从一条边直接走到它的反向边就可以了。
#include <iostream>
#include <cstring>
#include <cassert>
using namespace std;
typedef long long ll;
const int mod=45989;
struct matrix{
int r,c;
ll a[121][121];
matrix(int r,int c){
this->r=r;
this->c=c;
memset(a,0,sizeof(a));
}
ll * operator[](int p){
return a[p];
}
matrix operator =(const matrix& rhs){
//puts("WTF");
assert(r==rhs.r && c==rhs.c);
memcpy(a,rhs.a,sizeof(a));
return *this;
}
matrix operator *(matrix& rhs){
assert(c==rhs.r);
//puts("WTF");
matrix res(r,rhs.c);
//puts("WTF");
for(int i=0;i<r;i++)
for(int j=0;j<rhs.c;j++)
for(int k=0;k<c;k++)
(res[i][j]+=((a[i][k]*rhs[k][j])%mod))%=mod;
//puts("WTF");
return res;
}
matrix operator *=(matrix& rhs){
return *this=(*this)*rhs;
}
};
matrix power(const matrix& mat,ll b){
//puts("WTF");
matrix ret(mat.r,mat.c);
matrix t(mat.r,mat.c);
t=mat;
//puts("line 48");
for(int i=0;i<mat.r;i++)
ret[i][i]=1;
while(b){
//puts("WTF");
if (b%2)
ret=ret*t;
t=t*t;
b/=2;
}
return ret;
}
struct edge{
int from,to;
};
edge e[121];
int main(){
int n,m,t,a,b;
cin >> n >> m >> t >> a >> b;
a++,b++;
int cur=0;
for(int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
x++,y++;
e[cur++]=(edge){x,y};
e[cur++]=(edge){y,x};
}
matrix mt(cur,cur);
for(int i=0;i<cur;i++){
for(int j=0;j<cur;j++){
if (e[i].to==e[j].from && i!=(j^1))
mt[i][j]++;
}
}
mt=power(mt,t-1);
int ans=0;
for(int i=0;i<cur;i++)
for(int j=0;j<cur;j++)
if (e[i].from==a && e[j].to==b)
(ans+=mt[i][j])%=mod;
cout << ans;
}
2025年2月05日 21:43
Hey there. I found your site by the use of Google whilst looking for a similar subject, your site came up. It looks good. I have bookmarked it in my google bookmarks to visit then. Feel free to visit my website;
2025年2月05日 22:25
thank you for penning it up.
2025年2月05日 22:27
this is the first time that i am hearing
2025年2月05日 22:28
I absolutely love your website..
2025年2月05日 22:30
loving the facts in this web. Thank you
2025年2月05日 22:34
I just read this post, sharing such a great piece of content!
2025年2月05日 22:37
Hi! This is my first comment here so I just wanted to give a quick shout out and say I really enjoy reading through your blog posts. Can you suggest any other blogs/websites/forums that cover the same subjects? Appreciate it!
2025年2月05日 22:42
This blog stands as a
2025年2月05日 22:45
I just read this post, and I’m sharing such a great piece of content!
2025年2月05日 22:50
Please let me know if you’re looking for a author for your site. You have some really good posts and I believe I would be a good asset. If you ever want to take some of the load off, I’d really like to write some content for your blog in exchange for a link back to mine. Please blast me an e-mail if interested. Regards!
2025年2月05日 22:53
Please let me know if you’re looking for a author for your site. You have some really good posts and I believe I would be a good asset. If you ever want to take some of the load off, I’d really like to write some content for your blog in exchange for a link back to mine. Please blast me an e-mail if interested. Regards!
2025年2月05日 22:59
Thanks for a very interesting blog. What else may I get that kind of info written in such a perfect approach? I’ve a undertaking that I am simply now operating on, and I have been at the look out for such info.
2025年2月05日 23:06
I would like to thnkx for the efforts you have put in writing this blog. I’m hoping the same high-grade web site post from you in the upcoming as well. In fact your creative writing abilities has encouraged me to get my own website now. Really the blogging is spreading its wings fast. Your write up is a great example of it.
2025年2月05日 23:07
This post is one of the most meaningful pieces of information for me. And I'm animated reading your article. But it's a good thing; the website is perfect, and the pieces are great. Thanks for the tone of tangible and possible help.
2025年2月05日 23:07
loving the facts in this web site, you have carried out excellent job at the content . This appears simply ideal. All these tinny information are made with lot of heritage expertise. I really like it loads. This changed into a beneficial post and that i assume it is rather smooth to peer from the other remarks as is an informative post and it is very useful and informed. Therefore, i would like to thank you for the endeavors which you have made in writing this article. All of the content material is actually well-researched. Thank you
2025年2月05日 23:07
Thank you for sharing such nice information with us. I like your post, and everything you share with us is up to date and quite informative. I would like to bookmark the page so I can come back again to read your posts, as you have done a wonderful job.
2025年2月05日 23:07
I think this is an informative post and it is very beneficial and knowledgeable. Therefore, I would like to thank you for the endeavors that you have made in writing this article. All the content is absolutely well-researched. Thanks...
2025年2月05日 23:08
thank you for penning ng this specified post. This weblog is simple to seize subscribers and appeal to the reader. I am feeling proud to be your subscriber; your publish is so excellent. Keep it up.
2025年2月05日 23:09
I think this is an informative post and it is very beneficial and knowledgeable. Therefore, I would like to thank you for the endeavors that you have made in writing this article. All the content is absolutely well-researched. Thanks...
2025年2月05日 23:09
Hey there! I’m at work surfing around your blog from my new iphone! Just wanted to say I love reading through your blog and look forward to all your posts! Keep up the excellent work!
2025年2月05日 23:09
I would like to thnkx for the efforts you have put in writing this blog. I’m hoping the same high-grade web site post from you in the upcoming as well. In fact your creative writing abilities has encouraged me to get my own website now. Really the blogging is spreading its wings fast. Your write up is a great example of it.
2025年2月05日 23:09
We are truly thankful for your blog entry. You will discover a great deal of methodologies in the wake of going to your post. I was precisely scanning for. A debt of gratitude is in order for such post and please keep it up.
2025年2月05日 23:10
We are truly thankful for your blog entry. You will discover a great deal of methodologies in the wake of going to your post. I was precisely scanning for. A debt of gratitude is in order for such post and please keep it up.