题目大意
给定一个$n \times 6(n \le 10^9)$的方格纸,你需要在每一个方格中填上一个$[1,6]$之间的数
要求任意一个数与它↙,←,↖,↗,→,↘
这六个方向的数既不能相同,也不能和为7
并且规定左上角必须为$1$,且按照先从上往下逐行再从左往右的顺序,第一个$2$必须要出现在$5$之前,第一个$3$必须要出现在$4$之前
问有多少种合法的填色方案,输出对$1004535809$取模
解题报告
先不考虑最后题解的关于出现顺序的限制。这样的话,显然可以矩阵快速幂
但直接压状态的的话,矩阵大概长成$10^4 \times 10^4$,单次矩阵乘法都无法满足
不过我们仔细观察即可发现,对于其实1,6
是等价的,同理2,5
和3,4
于是我们每一个格子的状态就只有三种了,最后有效的状态一行只有96
个
这样就可以直接矩阵快速幂了
现在考虑最后的那个限制,我们可以容斥一下
我们可以先排除掉不包含2,5
这一对的方案数,然后除以二
同理3,4
也一样处理
于是最后就是一个状压DP用矩阵快速幂优化
最后再容斥一下,时间复杂度:$O(96 ^ 3 \log n)$
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; inline int read() { 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); n = read(); DFS(1, -1); 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; }
I think what you posted was very reasonable. However, what
about this? what if you were to write a killer post title?
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
home page and note how they create news headlines to grab
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.
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.
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!
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!
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
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!
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.
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?
My relatives every time say that I am killing my time here at net, but I know I am getting experience daily by
reading thes fastidious content.
This post will assist the internet visitors for setting up new webpage or even a weblog from start to end.
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.
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!!
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?
Hi there would you mind letting me know
which hosting company you’re using? I’ve loaded your blog in 3 completely different browsers and I must
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!
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.
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.
Hi there, i read your blog occasionally and i
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.
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!
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 added I receive 4 emails with the exact same comment.
Is there an easy method you are able to remove me from
that service? Thank you!
Way cool! Some very valid points! I appreciate you
writing this post and the rest of the site
is also really good.
Good information. Lucky me I came across your website
by accident (stumbleupon). I have bookmarked it for later!
Very good article. I’m going through some of these issues
as well..
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!