Description
今天是hidadz小朋友的生日,她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中,打算坐成一排玩游戏。为了游戏不至于无聊,就座的方案应满足如下条件:
对于任意连续的一段,男孩与女孩的数目之差不超过$k$。
很快,小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现,这样的就座方案其实是很多的,所以大家很快就找到了一种,那么到底有多少种呢?热爱数学的hidadz和她的朋友们开始思考这个问题……
假设参加party的人*有$n$个男孩与$m$个女孩,你是否能解答Susie和hidadz的疑问呢?由于这个数目可能很多,他们只想知道这个数目除以$12345678$的余数。
Solution
题目中要求每一段的男女数目差$\leq k$,可以转化为每一段前缀的每一段后缀的男女数目差$\leq k$
设$dp_{i,j,x,y}$表示目前的前缀中有男生$i$个,女生$j$个,在其所有后缀中男生最多比女生多$x$人,女生最多比男生多$y$人
这样从从短向长枚举前缀就可以检查每一段的男女数量差
$$dp_{i+1,j,x+1,max(0,y-1)}+=dp_{i,j,x,y}$$
$$dp_{i,j+1,max(0,x-1),y+1}+=dp_{i,j,x,y}$$
对$0$取$max$的原因在于:将空串也视为原序列的一个后缀,那么每加入一个人不仅会使上一个前缀的所有后缀长度增加,而且会新增一个空串作为后缀。若此时$x$
或$y$中有负值,则可以取最后的空串使其值更大(值为$0$)
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,m,k,dp[160][160][25][25],ans; const int mod=12345678; inline int read() { int f=1,w=0; char ch=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+ch-'0'; ch=getchar(); } return f*w; } int main() { n=read(); m=read(); k=read(); dp[0][0][0][0]=1; for(int i=0;i<=n;i++) { for(int j=0;j<=m;j++) { for(int x=0;x<=k;x++) { for(int y=0;y<=k;y++) { (dp[i+1][j][x+1][max(0,y-1)]+=dp[i][j][x][y])%=mod; (dp[i][j+1][max(0,x-1)][y+1]+=dp[i][j][x][y])%=mod; } } } } for(int i=0;i<=k;i++) { for(int j=0;j<=k;j++) { (ans+=dp[n][m][i][j])%=mod; } } printf("%lld\n",ans); return 0; }[ZJOI2008]生日聚会