bzoj4402: Claris的剑

首先,对于本质相同的构造,我们只计算字典序最小的序列

假设序列中最大的元素为top

我们很容易发现这样的序列一定是1,2,..,1,2,3,2,3,...,2,3,4,3,4.........,top-1,top(原谅我的语言表达……)

我们很容易发现这样的序列从第二个数开始一定是2,若干个(1,2),3,若干个(2,3),....,top,若干个(top-1,top)

我们很容易发现,这样的序列中有且仅有top-2个元素在一个连续的长度大于2的上升序列中,且不在两个端点上(也就是满足a[i]=a[i-1]+1且a[i+1]=a[i]+1)

并且不可能存在连续的长度大于2的下降序列(也就是没有位置满足a[i]=a[i-1]-1且a[i]=a[i+1]-1)

(这两句话说的窝好累TAT)(看不懂的就看划掉的2句话吧TAT)

那么我们就可以组合学乱搞了

详见代码(那个fm是(m-2)!,是常数优化用的,无视它就好,c(n,m)就是求组合数的)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define N 2000006
#define P 1000000007 using namespace std;
int pow2(int x,int y){
int ret=1;
while (y){
if (y&1) ret=(ll)ret*x%P;
x=(ll)x*x%P;
y=y>>1;
}
return ret;
} int fact[N],fm;
int c(int n,int m){
if (n<m) return 0;
return (ll)fact[n]*fm%P*pow2(fact[n-m],P-2)%P;
}
int n,m; int main(){
scanf("%d%d",&n,&m);
if (m<2||n<2){printf("%d\n",max(m,0));return 0;}
for (int i=fact[0]=1;i<=n/2+m/2+3;++i) fact[i]=(ll)fact[i-1]*i%P;
int ans=2,now[2]={1,0};
fm=pow2(fact[m-2],P-2);
for (int i=3;i<=n;++i){
(now[i&1]+=now[1^i&1])%=P;
if ((i-m-1)%2==0) (now[1^m&1]-=c((i-m-1)/2+m-2,m-2)-P)%=P;
(ans+=(now[0]+now[1])%P)%=P;
}
printf("%d\n",ans);
return 0;
}

  

上一篇:好吧,CSS3 3D transform变换,不过如此!


下一篇:Python学习案例之Web版语音合成播报