题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2467
传说中的矩阵树定理！其实搞一搞排列组合，然后O(1)输出就可以了QAQ
唯一值得一提的，就是高斯消元那里，因为有除，且模数不是质数（不一定有逆元）
所以只能使用类似辗转相除的方法，而不能搞LCM
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 400+9;
const int MOD = 2007;
int G[MAXN][MAXN],n;
inline int read(){
char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar();
return ret;
}
inline int id(int i, int j){
if (i>n) i -= n;
return (--i)*4+j;
}
inline void Add_Edge(int u, int v){
G[u][u]++; G[v][v]++;
G[u][v]--; G[v][u]--;
}
inline void Build_Matrix(){
for (int i=1;i<=n;i++) {
for (int j=1;j<=3;j++) Add_Edge(id(i,j),id(i,j+1));
Add_Edge(id(i,4),id(i+1,1)); Add_Edge(id(i,1),id(i+1,1));
}n *= 4; n--;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) G[i][j] = (G[i][j]%MOD + MOD) % MOD;
}
inline int Gauss(){
int ret = 1;
for (int j=1,w=0;j<=n;j++) {
for (int k=j+1;k<=n;k++) while (G[j][k]) {
int t = G[j][j]?G[j][k] / G[j][j]:1;
for (int i=1;i<=n;i++) G[i][k] = ((G[i][k] - G[i][j]*t) % MOD + MOD) % MOD;
for (int i=1;i<=n;i++) swap(G[i][k], G[i][j]); ret *= -1;
} ret = ret*G[j][j] % MOD;
} return (ret + MOD) % MOD;
}
int main(){
for (int T=read();T;T--) {
n = read(); memset(G,0,sizeof(G));
Build_Matrix();
printf("%d\n",Gauss());
}
return 0;
}
Everything is very open with a really clear description of the
challenges. It was really informative. Your site is useful.
Many thanks for sharing!
Good web site you’ve got here.. It’s hard to find high-quality writing like yours nowadays.
I honestly appreciate individuals like you! Take care!!
My brother suggested I might like this web site. He was entirely right.
This post actually made my day. You can not imagine simply how much time I had spent for this info!
Thanks!
I think this is one of the most significant information for me.
And i’m glad reading your article. But want to remark on some general things, The website style is perfect, the articles
is really excellent : D. Good job, cheers
Heya i’m for the first time here. I came across
this board and I in finding It truly helpful &
it helped me out much. I’m hoping to give something back and aid others like you aided me.
Hello just wanted to give you a brief heads up and let you know a
few of the images aren’t loading correctly. I’m not sure why but I
think its a linking issue. I’ve tried it in two
different internet browsers and both show the same results.
Hurrah, that’s what I was searching for, what a material!
existing here at this blog, thanks admin of this web page.
I go to see day-to-day some blogs and information sites to read content,
however this webpage offers quality based content.
Good day! I know this is kind of off topic but I
was wondering which blog platform are you using for this site?
I’m getting fed up of WordPress because I’ve had
issues with hackers and I’m looking at options for another platform.
I would be awesome if you could point me in the direction of a good platform.
It’s in point of fact a great and useful piece of information. I’m happy that
you just shared this helpful information with us.
Please stay us informed like this. Thank you for sharing.
Excellent beat ! I would like to apprentice while you amend your site, how can i subscribe for a blog web site?
The account aided me a acceptable deal. I have been tiny
bit acquainted of this your broadcast provided bright clear concept
You can certainly see your enthusiasm in the work you write. The world hopes for more passionate writers such as you who are not afraid to say how they believe. All the time follow your heart. “Man is the measure of all things.” by Protagoras.
It’s really a nice and helpful piece of info. I’m satisfied that you shared this
useful info with us. Please stay us up to date like this.
Thank you for sharing.
Wow! In the end I got a web site from where I be able
to in fact obtain valuable information regarding my study and knowledge.
I’m really enjoying the design and layout of your website.
It’s a very easy on the eyes which makes it much more pleasant for me to come here and visit more often.
Did you hire out a designer to create your theme? Outstanding work!
Hmm it appears like your site ate my first comment (it was extremely long) so I
guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog writer but I’m still new to the
whole thing. Do you have any helpful hints for beginner blog writers?
I’d really appreciate it.
Valuable info. Lucky me I discovered your website accidentally, and I am shocked why this coincidence did
not happened earlier! I bookmarked it.
I have to thank you for the efforts you’ve put in writing this blog.
I really hope to view the same high-grade content by you later on as well.
In fact, your creative writing abilities has encouraged me to
get my own, personal blog now 😉
It’s perfect time to make some plans for the future and it is time to
be happy. I have read this post and if I could I desire to suggest you some interesting things or advice.
Maybe you can write next articles referring to this article.
I want to read more things about it!
I loved as much as you will obtain carried out right here. The caricature is tasteful, your authored subject matter stylish. nevertheless, you command get bought an shakiness over that you would like be delivering the following. in poor health unquestionably come further earlier once more as precisely the similar nearly very often within case you protect this increase.