相关链接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2017/03/20170301145817_34363.png
官方题解：http://oi.cyo.ng/wp-content/uploads/2017/03/20170301150237_94661.png
一句话题意
给$n_1$个$A$，$n_2$个$B$，$n_3$个$C$，$n_4$个$D$
问有多少种排列方式，使得相邻两项全部不同
$n_1,n_2,n_3,n_4 \le 10^3$
吐槽
因为做过魔法的碰撞
所以这题卡在$O(n^3)$的复杂度上卡了三个半小时 QwQ
最后暴力还$MLE$了 QwQ
解题报告
假设我们知道了将$A,B$分成$i$段、每一段中相邻两项不同的方案数为$f_i$
知道了将$C,D$分成$i$段、每一段中相邻两项不同的方案数为$g_i$
那么答案显然为$\sum\limits_{i=1}^{n_1+n_2}{f_i \cdot (g_{i-1}+2g_i+g_{i+1})}$
至于中间那一项为什么要乘以2？ 因为多出来那一段我们既可以放段首，也可以放段尾
现在唯一的问题就是如何求出$f_i,g_i$了
考虑仅由$A,B$组成的字符串，一定为以下四种情况之一
[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A
假如我们枚举第一种情况出现了$i$次
那么第二种情况的出现次数$j=i-(a-b)$
那剩下的$k$次，就是第三种和第四种了，不难发现我们乘上$2^k$之后他们就可以视为等价
于是我们先在第一种情况的位置上插入$A$,第二种情况插入$B$，第三、四种情况插入$AB(BA)$
之后我们相当于把剩下的$A,B$两两配对，然后分成$x$组，允许空集
那么这就是插板法的板题了
于是我们就用上述算法处理出$f_i,g_i$即可
时间复杂度：$O(n^2)$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MOD = 1000000007;
const int N = 2009;
int vout,f[N],g[N],C[N][N],PW2[N];
inline int read() {
char c=getchar(); int ret=0,f=1;
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;
}
inline int solve(int a, int b, int c) {
if (a < b) swap(a, b);
if (!a && b) return b == c;
int ret = 0;
for (int i=a-b,j,k;i<=c;++i) {
j = i - a + b; k = c - i - j;
if (j >= 0 && k >= 0 && a >= i + k ) {
(ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD;
}
}
return ret;
}
int main() {
PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD;
C[0][0] = 1; for (int i=1;i<N;i++) {
C[0][i] = 1; for (int j=1;j<=i;j++) {
C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
}
}
int a=read(),b=read(),c=read(),d=read();
if (a + b == 0) f[1] = 1;
else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i);
if (c + d == 0) g[1] = 1;
else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i);
for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD;
printf("%d\n",vout);
return 0;
}
Hello There. I discovered your weblog the use of msn. That is a really smartly written article.
I will be sure to bookmark it and return to learn more of your helpful info.
Thank you for the post. I’ll certainly comeback.
What a material of un-ambiguity and preserveness of valuable experience
concerning unpredicted emotions.
I’m more than happy to discover this web site.
I need to to thank you for ones time due to this fantastic read!!
I definitely loved every part of it and I have
you saved to fav to look at new things on your site.
I have been exploring for a little bit for any high-quality articles
or blog posts in this sort of area . Exploring in Yahoo I finally stumbled upon this site.
Reading this info So i am satisfied to show that I have a very just right
uncanny feeling I came upon just what I needed.
I such a lot no doubt will make certain to don?t put out of your
mind this website and provides it a look regularly.
Excellent post however I was wondering if you could write a litte more on this topic?
I’d be very thankful if you could elaborate a little bit further.
Bless you!
Very nice post. I simply stumbled upon your blog and wanted to say that I’ve truly
enjoyed browsing your weblog posts. After all I’ll be
subscribing on your feed and I hope you write again very
soon!
Hi there! This post couldn’t be written any
better! Reading this post reminds me of my good old room mate!
He always kept talking about this. I will forward this page to
him. Fairly certain he will have a good read.
Thanks for sharing!
I think this is one of the most important info for me.
And i’m glad reading your article. But should remark on few
general things, The web site style is ideal, the
articles is really great : D. Good job, cheers
I think this is among the most significant info for me.
And i’m glad reading your article. But wanna remark
on few general things, The web site style is wonderful, the articles
is really nice : D. Good job, cheers
At this moment I am going away to do my breakfast, later than having my breakfast coming over again to read more news.
I think what you typed made a lot of sense. But, consider
this, suppose you added a little information? I am not
suggesting your information is not good., however what if you added something that makes
people desire more? I mean 【日常小测】计数 – Qizy's Database is kinda plain. You should look at Yahoo’s
home page and watch how they create article titles to get people to click.
You might try adding a video or a related pic or two to get people interested about everything’ve written. Just my
opinion, it would bring your posts a little bit more interesting.
Magnificent site. A lot of useful information here.
I am sending it to some buddies ans additionally sharing in delicious.
And obviously, thanks for your effort!
Fantastic blog! Do you have any tips for aspiring writers?
I’m planning to start my own website soon but I’m a little lost on everything.
Would you propose starting with a free platform like WordPress or go for
a paid option? There are so many options out there that I’m totally
confused .. Any tips? Bless you!
Thanks for sharing your thoughts. I truly appreciate your efforts and I am waiting
for your further write ups thank you once again.
I’m not that much of a internet reader to
be honest but your sites really nice, keep it up!
I’ll go ahead and bookmark your site to come back later. Cheers
I like what you guys tend to be up too. This kind of
clever work and coverage! Keep up the awesome works guys I’ve added you guys to my blogroll.
I visited various websites however the audio
quality for audio songs existing at this site is in fact wonderful.
I really like your writing style, fantastic information, appreciate it for posting :D. “Silence is more musical than any song.” by Christina G. Rossetti.
Wow, wonderful weblog layout! How lengthy have you been running a blog for?
you made blogging glance easy. The entire glance of your web site is wonderful, as neatly
as the content material!
Fantastic beat ! I wish to apprentice whilst you amend your site, how could i subscribe for a weblog web site?
The account aided me a acceptable deal. I were tiny bit acquainted of this your broadcast provided shiny transparent
concept
I like the helpful information you provide for your articles.
I will bookmark your weblog and take a look at once more right here frequently.
I’m slightly certain I’ll be told plenty of new stuff proper right here!
Best of luck for the following!
Hi there it’s me, I am also visiting this web site regularly, this
site is truly pleasant and the viewers are in fact sharing pleasant thoughts.
Valuable information. Lucky me I discovered your site by accident, and I am shocked why this accident
did not took place in advance! I bookmarked it.
It’s enormous that you are getting ideas from this post as well as from our discussion made here.
Asking questions are truly fastidious thing if you are not understanding
anything entirely, but this piece of writing gives good understanding yet.
I am not sure where you’re getting your info, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for magnificent information I was looking
for this information for my mission.
Helpful info. Lucky me I found your site accidentally,
and I’m stunned why this twist of fate didn’t took place in advance!
I bookmarked it.
I’ve been absent for a while, but now I remember why I used to love this blog. Thank you, I?¦ll try and check back more frequently. How frequently you update your web site?