Question

蓝桥杯那道波动数列你给出的代码超时，还能优化一下吗

http://power.baidu.com/question/1383484532040488540.html?entry=qb_browse_default

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励30（财富值+成长值）

Answer 1

肯定超时啊，最后答案 都要mod 100000007，每一次cnt++，至少要把所有情况都搜到，你执行100000007次cnt++都会超时啊

Answer 2

你在哪个平台的，应该没超时啊

追问

就是蓝桥杯的测试平台，你再提交一次试试，应该是超时的，只能通过前两组测试数据

追答

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int Mod=100000007;
int dp[1005][1005];
int main()
{
    int n,s,a,b;
    scanf("%d%d%d%d",&n,&s,&a,&b);
    dp[1][0]=1;//不妨设首项为0
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            //计算每一次+a或者-b对数列之和sum的贡献
            dp[i+1][(j+(n-i)*a)%n]=(dp[i+1][(j+(n-i)*a)%n]+dp[i][j])%Mod;
            dp[i+1][(j+i*b)%n]=(dp[i+1][(j+i*b)%n]+dp[i][j])%Mod;
            //等价于dp[i+1][(j-(n-i)*b)%n]+=dp[i][j];
        }
    }
    s=(s+1000000000LL*n)%n;//保证s非负且不改变s mod n的值
    printf("%d\n",dp[n][s%n]);
    //若sum=s(mod n)则可以改变首项使得数列满足条件
    return 0;
}