【日常小测】迷宫

题目大意

给定一个$n \times 6(n \le 10^9)$的方格纸,你需要在每一个方格中填上一个$[1,6]$之间的数
要求任意一个数与它↙,←,↖,↗,→,↘这六个方向的数既不能相同,也不能和为7
并且规定左上角必须为$1$,且按照先从上往下逐行再从左往右的顺序,第一个$2$必须要出现在$5$之前,第一个$3$必须要出现在$4$之前
问有多少种合法的填色方案,输出对$1004535809$取模

解题报告

先不考虑最后题解的关于出现顺序的限制。这样的话,显然可以矩阵快速幂
但直接压状态的的话,矩阵大概长成$10^4 \times 10^4$,单次矩阵乘法都无法满足
不过我们仔细观察即可发现,对于其实1,6是等价的,同理2,53,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;
}

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

  1. 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.

  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. 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!

  4. 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

  5. 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!

  6. 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?

  7. 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!!

  8. 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!

  9. 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.

  10. 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!

  11. 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!

  12. 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!

Leave a Reply to sling tv Cancel reply

Your email address will not be published. Required fields are marked *