题目描述

blablabla

样例

blablabla

include [HTML_REMOVED]

using namespace std;

const int N = 1010, MOD = 100000007;

int n, s, a, b;
int f[N][N];

int get_mod(int a, int b)//求余数
{
return (a % b + b) % b;
}

int main()
{
cin >> n >> s >> a >> b;

f[0][0] = 1;

for (int i = 1; i < n; i++)//f[i][j]表示要选i个a或者-b且余数为j的所有集合的数量。第i个可以选a或者-b。
    for (int j = 0; j < n; j++)
        f[i][j] = (f[i - 1][get_mod(j - (n - i) * a, n)] + f[i - 1][get_mod(j + (n  - i) * b, n)]) % MOD;

cout << f[n - 1][get_mod(s, n)];

return 0;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla