爱惜阿姆退役选手来嘴炮一波百度笔试换位子那题吧

#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的值，每次只要弹出最后的值就可以了，复杂度只有
位置个数。