最朴素的dfs，过4个测试点

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;


const int N = 1005;
const int MOD = 100000007;

int n,s,a,b;

int ans;

int sum;
void dfs(int pos, int x, int sum){
    if(pos == n-1 ) {
        if(sum == s){
            ans += 1;
            ans = ans % MOD;            
        }
        return ;
    }
    dfs(pos+1, x+a, sum+x+a); // a[pos+1] = x+a, sum += sum + a[pos+1]
    dfs(pos+1, x-b, sum+x-b); // 
}

int main(int argc, char** argv) {
    cin >> n >> s >> a >> b;
    int start = (s-a*(n-1)*(n-2))/n;
    int end = (s+b*(n-1)*(n-2))/n + 1;

    for(int i = start; i <= end; i++) {
        dfs(0, i, i); // a[0] = i;sum
    }
    cout << ans;
    return 0;
}

为了优化的dfs-过4个测试点

• 需要发现：
  • 只要满足[(n-1)d1 + (n-1)d2 + … + dn-1] % n == s %n ，其中di都是a或者-b，则是一个满足条件的组合，所以问题变成：有多少种满足上式的组合。
• dfs如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1005;
const int MOD = 100000007;

int n,s,a,b;
int ans;
int sum;

void dfs(int pos, int x){ // pos， 余数 
    if(pos == n) {
        if(x == s % n){
            ans++;
            ans %= MOD;
        }
        return ;
    }
    dfs(pos+1, (x+pos*a) % n);
    dfs(pos+1, ((x-pos*b) % n + n) % n); // 得保证余数是正的 
}

int main(int argc, char** argv) {
    cin >> n >> s >> a >> b;
    dfs(1,0);
    cout << ans;
    return 0;
}

dp

• 1.状态表示：由上述bfs导出，且dfs的参数是dp的维度
  • dfs中的i表示：前i个数，
  • dfs中的j表示：前i个数累积的余数，
  • 由于ans++，是计数，所以dp[i][j]解释为：前i个数的累积余j的个数
• 2.借用集合的思想导出状态转移方程：
  • dp[i][j]由两部分相加而成，(1)第i-1个数是a，(2) 第i-1个数是-b
  • 但是，j - (i-1)*b 可能为负数， 需要用函数 pos_mod改为正数,
  • 所以 dp[i][j] = dp[i-1][pos_mod(j+i*a, n)] + dp[i-1][pos_mod(j-i*b, n) ]
• 3.压轴，dp的初始化(边界)：dp[0][0] = 1
• 4.最后，结果表示： dp[n-1]

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1005;
const int MOD = 100000007;
int n,s,a,b;
int dp[N][N];

int pos_mod(int a, int b){
    return (a % b + b) % b;
}


int main(int argc, char** argv) {
    cin >> n >> s >> a >> b;

    // 1. 初始化 
    dp[0][0] = 1;

    // 2.递推
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = (dp[i-1][pos_mod(j+i*a, n)]  + dp[i-1][pos_mod(j-i*b, n)]) % MOD;
    cout << dp[n-1][pos_mod(s, n)];
    return 0;
}