# 【日常小测】迷宫

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1004535809;

int n,tot,vout,sta[100][7],cur[7];
struct Matrix{
int f[100][100];
inline Matrix() {memset(f,0,sizeof(f));}
inline Matrix(int x) {memset(f,0,sizeof(f));for(int i=1;i<=tot;i++)f[i][i]=x;}
inline Matrix(const Matrix &M) {for(int i=1;i<=tot;i++)for(int j=1;j<=tot;j++)f[i][j]=M.f[i][j];}
inline Matrix operator * (const Matrix &M) {
Matrix ret;
for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) for (int k=1;k<=tot;k++)
ret.f[i][k] = (ret.f[i][k] + (LL)f[j][k] * M.f[i][j]) % MOD;
return ret;
}
inline Matrix operator ^ (int t) {
Matrix ret(1),tmp(*this);
for (;t;t>>=1,tmp=tmp*tmp)
if (t&1) ret=ret*tmp;
return ret;
}
inline void out() {
for (int i=1;i<=tot;i++) {
for (int j=1;j<=tot;j++) {
printf("%d ",f[j][i]);
} cout<<endl;
}
}
}ans,trans;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

void DFS(int w, int v) {
if (w == 7) {
memcpy(sta[++tot],cur,sizeof(cur));
} else {
for (int i=1;i<=3;i++) if (i != v)
cur[w] = i, DFS(w+1, i);
}
}

inline int Pow(int w, LL t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}

inline bool check(int a, int b) {
for (int i=1;i<=6;i++) {
if (i > 1 && sta[a][i-1] == sta[b][i]) return 0;
if (i < tot && sta[a][i+1] == sta[b][i]) return 0;
} return 1;
}

int main() {
freopen("board.in","r",stdin);
freopen("board.out","w",stdout);
for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++)
if (check(i, j)) trans.f[j][i] = 1 << 6;
for (int i=1;i<=tot;i++) if (sta[i][1] == 1) ans.f[i][1] = 1 << 5;
trans = trans ^ (n - 1); ans = ans * trans;
for (int i=1;i<=tot;i++) vout = (vout + ans.f[i][1]) % MOD;
vout = (vout - 2ll * Pow(2, n * 6ll - 1)) % MOD;
vout = (LL)vout * Pow(4, MOD-2) % MOD;
vout = (vout + Pow(2, n * 6ll - 1)) % MOD;
printf("%d\n",(vout+MOD)%MOD);
return 0;
}


## 23 thoughts to “【日常小测】迷宫”

1. I think what you posted was very reasonable. However, what
I ain’t suggesting your content isn’t good, but what if you added something that grabbed folk’s attention? I mean 【日常小测】迷宫 – Qizy'
s Database is a little vanilla. You might peek at Yahoo’s
people interested. You might add a video or a related picture or two to get people interested about everything’ve written. In my opinion, it could
bring your blog a little bit more interesting.

2. Its such as you read my mind! You appear to grasp so much approximately this, such as you
wrote the guide in it or something. I feel that you simply can do with a few %
to drive the message house a bit, however instead of that, this is magnificent blog.
An excellent read. I’ll definitely be back.

3. I was recommended this blog by my cousin. I am no longer certain whether or not this post is
written by him as no one else recognize such
targeted about my trouble. You’re incredible!

Thank you!

4. Hi there are using WordPress for your site platform?
I’m new to the blog world but I’m trying to get started and set up my own. Do you need any html coding knowledge to make your own blog?
Any help would be greatly appreciated!

5. I love your blog.. very nice colors & theme.
Did you create this website yourself or did you hire someone to do it for you?
Plz answer back as I’m looking to design my
own blog and would like to find out where u got this from. thank you

6. Wow, wonderful blog layout! How long have you been blogging for?

you make blogging look easy. The overall look of
your web site is great, let alone the content!

7. I think the admin of this web site is genuinely working hard in favor of his website, because here every data is quality based data.

8. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your intelligence on just posting videos
to your site when you could be giving us something enlightening to read?

9. My relatives every time say that I am killing my time here at net, but I know I am getting experience daily by

10. This post will assist the internet visitors for setting up new webpage or even a weblog from start to end.

11. Hello there! Do you use Twitter? I’d like to follow you
if that would be okay. I’m definitely enjoying your blog and look forward to new posts.

12. Hello, i think that i saw you visited my weblog thus i came to
return the desire?.I’m trying to to find things to enhance my website!I assume its adequate to make use of some of your ideas!!

13. Hey! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard
on. Any suggestions?

14. Hi there would you mind letting me know
say this blog loads a lot quicker then most.
Can you recommend a good internet hosting provider at a fair price?
Kudos, I appreciate it!

15. Very fantastic info can be found on web site. “There used to be a real me, but I had it surgically removed.” by Peter Sellers.

16. I all the time used to read post in news papers but now as I am a
user of net so from now I am using net for articles
or reviews, thanks to web.

own a similar one and i was just wondering if you get a lot of spam remarks?
If so how do you prevent it, any plugin or anything you can advise?
I get so much lately it’s driving me crazy so any help is very much appreciated.

18. Amazing! This blog looks just like my old one! It’s on a completely different topic but
it has pretty much the same page layout and design. Excellent choice of colors!

19. After I initially commented I seem to have clicked on the -Notify
me when new comments are added- checkbox and now every time a comment
Is there an easy method you are able to remove me from
that service? Thank you!

20. Way cool! Some very valid points! I appreciate you
writing this post and the rest of the site
is also really good.

21. Good information. Lucky me I came across your website
by accident (stumbleupon). I have bookmarked it for later!

22. Very good article. I’m going through some of these issues
as well..

23. Very nice post. I just stumbled upon your blog and wished to say that I have truly enjoyed surfing around your blog posts. In any case I’ll be subscribing to your rss feed and I hope you write again very soon!