爱惜阿姆退役选手来嘴炮一波百度笔试换位子那题吧
dp[i][j]表示前i个位子最后一个空了j个位置的方案数。
现在我们固定最后一段的区间，开始dp。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>
#define eps 0.0000000001
#define maxn 1000009
#define inf 0x3f3f3f3f
#define mod 123456789
#define ll long long
using namespace std;
int n,m;
ll dp[2][maxn],ans=0;
int main()
{
freopen("d:\\in.txt","r",stdin);
scanf("%d%d",&n,&m);
int cur=1;
dp[1][0]=1;
for(int i=1;i<=n;i++)
{
int cu=cur^1;
for(int j=0;j<m;j++)
{
if(j+1<m)
dp[cu][j+1]=(dp[cu][j+1]+dp[cur][j])%mod;
dp[cu][0]=(dp[cu][0]+dp[cur][j])%mod;
}
int y=n-i;
if(y<m)
ans=(ans+dp[cur][0]*(y+1)%mod)%mod;
memset(dp[cur],0,sizeof(dp[cur]));
cur^=1;
}
printf("%lld\n",ans);
return 0;
}
但是这样会超时，只过了0.64，我们仔细看看dp的状态转移.只是向后移动一位， 因此我们可以用队列来维护dp的值，每次只要弹出最后的值就可以了，复杂度只有 位置个数。
