求1~n組成一個(gè)抖動(dòng)序列的方案數(shù)

首先這種序列有一些非常妙妙但我發(fā)現(xiàn)不了的性質(zhì)

1.對(duì)于一個(gè)抖動(dòng)序列，如果i和i+1不相鄰，則交換i和i+1，他還是個(gè)抖動(dòng)序列

2.對(duì)于一個(gè)抖動(dòng)序列，我把每個(gè)數(shù)拿n+1減一下（上下翻轉(zhuǎn)），他還是個(gè)抖動(dòng)序列，只不過(guò)波峰和波谷換了一下

3.對(duì)于一個(gè)抖動(dòng)序列，我把它左右翻轉(zhuǎn)，他還是個(gè)抖動(dòng)序列

于是設(shè)f[i][j]是i個(gè)數(shù)中，排名為j的數(shù)在第一個(gè)位置、且它是波峰的方案數(shù)

那么答案就是$2\sum{f[N][i]}$（我把它翻一下不就有所有的第一個(gè)數(shù)作為波谷的情況了嘛）

然后有方程$f[i][j]=f[i][j-1]+f[i-1][j-1]$

考慮兩種情況：

　　1.j和j-1不相鄰，由性質(zhì)1這種情況的f[i][j]就是f[i][j-1]

　　2.j和j-1相鄰，也就是j-1在第二個(gè)位置，這種情況的f[i][j]就是f[i-1][j-1]，就是不看j，然后把剩下的i-1個(gè)數(shù)拎出來(lái)，那j-1的排名還是j-1

合起來(lái)就是上面的方程

1 #pragma GCC optimize(3) 2 #include<bits/stdc++.h> 3 #define pa pair<ll,ll> 4 #define CLR(a,x) memset(a,x,sizeof(a)) 5 using namespace std; 6 typedef long long ll; 7 const int maxn=4205; 8 9 inline char gc(){ 10 return getchar(); 11 static const int maxs=1<<16;static char buf[maxs],*p1=buf,*p2=buf; 12 return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxs,stdin),p1==p2)?EOF:*p1++; 13 } 14 inline ll rd(){ 15 ll x=0;char c=gc();bool neg=0; 16 while(c<'0'||c>'9'){if(c=='-') neg=1;c=gc();} 17 while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=gc(); 18 return neg?(~x+1):x; 19 } 20 21 int N,f[2][maxn],P; 22 23 int main(){ 24 //freopen("","r",stdin); 25 int i,j,k; 26 N=rd(),P=rd(); 27 f[1][1]=1; 28 for(i=2;i<=N;i++){ 29 for(j=1;j<=i;j++){ 30 f[i&1][j]=(f[i&1][j-1]+f[!(i&1)][i-j+1])%P; 31 } 32 } 33 int ans=0; 34 for(i=1;i<=N;i++) 35 ans+=f[N&1][i],ans%=P; 36 printf("%d\n",ans*2%P); 37 return 0; 38 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Ressed/p/9935020.html

總結(jié)

以上是生活随笔為你收集整理的luogu2467/bzoj1925 地精部落 (dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。