分析
设第一个数为$ x $，则第二个数为$ x+d_1 $，第三个数为$ x+d_1+d_2 $ …。这里的$d_1$，$d_2$表示$a$或者$-b$，所以这个数列为：
$x$, $x + d_1$, $x + d_1 + d_2$, $x + d_1 + d_2 + d_3$, …, $x + d_1 + d_2 + … + d_{n-1}$，又因为数列之和为s，所以转化成：
$ n * x + (n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 + … + d_{n-1} = s $，再在一步转化：
$\frac{s - [(n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 + …+ d_{n-1}]}{n} = x $
因为x是任意整数，所以又转化成：
$ s $与$ (n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 + …+ d_{n-1} $ 模$n$的余数相同。
到这里就转化成了组合问题。
下面就可以用闫氏dp分析法了。
1.状态表示：
f[i][j]表示要选i个a或者-b且余数为j的所有集合的数量。
2.状态计算：第i个可以选a或者-b。第
i个选a：$(n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 +…+ 2 * d_{n-2}+ a$ 模 $x = j$。则：$(n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 +…+ 2 * d_{n-2}$ 模 $x = j - a$。
系数和下标之和为
n，所以第i项的的系数为n-i。所以：
f[i][j] = f[i - 1][j - (n - i) * a]第i个选b：同理：
f[i][j] = f[i - 1][j + (n - i) * b]
时间复杂度 $O(n^2)$
状态数量 * 状态转移时操作数 = (n - 1) * (n - 1) * 2
C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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()
{
scanf("%d%d%d%d", &n, &s, &a, &b);
f[0][0] = 1;
for (int i = 1; i < n; i++)
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;
printf("%d", f[n - 1][get_mod(s, n)]);
return 0;
}
Java代码
import java.util.Scanner;
public class Main {
static int N = 1010;
static int MOD = 100000007;
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n, s, a, b;
n = scan.nextInt();
s = scan.nextInt();
a = scan.nextInt();
b = scan.nextInt();
f[0][0] = 1;
for (int i = 1; i < n; i++)
for (int j = 0; j < n; j++)
f[i][j] = (f[i - 1][getMod(j - (n - i) * a, n)] + f[i - 1][getMod(j + (n - i) * b, n)]) % MOD;
System.out.println(f[n - 1][getMod(s, n)]);
}
public static int getMod(int a, int b) {
return (a % b + b) % b;
}
}
又转化成后面是模n的余数相同
请问 f[i-1][(j-i*a)%n] 这里的 j指的是什么呢？ 而且他为什么是从0~n-1呢
f[i][j]中的j指的是：只从前i个数选（a或-b）且这i个数的和与n取余数等于j的集合；至于为什么j是从0~(n-1)，emma % b的值就是0~(b-1)，因为要么是b的倍数，要么余1，要么余2，要么余3…一直到b-1嗯嗯 这个j理解了 感谢 不过 j就是前i个数的和模n 那这里的f[i-1][(j-ia)%n] （j-ia） 为什么还要再取余呢 （我好想陷入了某种误区 但是我出不来 555）
放松一会，昨天看地宫我想不明白，睡一觉就好了，我的水平不行，看不懂你的问题唉....
哦哦好滴 其实我就是想不太明白 （j-i*a）为什么还要再取下模， 我想着那个j不是都模过一遍n了嘛 那我也睡一觉 明天再想想
果然睡一觉就好了 我现在想明白了 谢谢姐妹
hhh不客气姐妹…
盲猜佬不是姐妹
在这里我说一下我对于这个代码的理解，因为s-[(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+…+dn−1]=nx，设(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+…+dn−1=y，有s=nx+y,则对等式两边取模有,s mod(n) =[nx+y]mod(n)=y mod(n), 故统计y%n的不同方案有多少，而当第i个选择a时，余数j=y%n=j-(n-i)a,类比b也可得到。而初始化边界条件dp[0][0]代表选0个a或者b且余数也为0，就代表只有唯一的方案。
懂了为啥转换的了
s mod(n) =[nx+y]mod(n)=y mod(n), 这里mod(n)为啥减去了nx-y呢不会影响最终结果吗
这个状态转换就是(a+b)%n = c转换成a%n = c-b。这完全不对嘛，啊啊啊要死啦
我也是，这个转换根本不对，不知道为啥这样还能Ac，真无语了
为什么题目表示为f[n-1]不是f[n]啊
一共有n项，第一项是未知的，所以我们需要进行+a或者-b的操作只有后面的n-1项
我想知道他是怎么推出来j+(n-1)*b与前i-1项的和模n余数相同的
我也想知道
同余式中同余号两端加减同样的数依旧同余
orz
Orz
为什么输出f[n - 1][get_mod(s, n)]，而不是f[n][get_mod(s, n)]
因为我们第一项是未知的，不是假设x了嘛，然后把x单独提出来，转化成了n-1项他们的和取模n的余数和S取模n的余数相等的方案数，然后再去求i项的组合成和取模为j方案数，然后把n-1和s取模的余数代入得出答案，所以第一项相当于参变分离了被
### 哪里错了
######## 原来加强数据了(改完后过了)
为什么明明是f[i][j] = f[i - 1][j - (n - i) * a]，却要写成f[i - 1][getMod(j - (n - i) * a, n)]；为啥要用这个函数
后面是取模运算滴，并且保证余数一定是正数
(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+…+2∗dn−2(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+…+2∗dn−2 模 x=j−a
为什么 (a+b+c)%mod =x %mod会等价于(a+b)%mod=(x-c)%mod
tql
6
写的太好啦，借鉴学习呀！
在循环的时候如果取正余数加为什么不会加重呢？
这里面所有的取余操作都是取正余，只要都用的同一套标准就不用担心重复吧。因为本身 s与(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+…+dn−1 模n的余数相同 这个式子也是用取正余来计算的（s可能小于0）。你就直接当原来求余数的方法不存在就行呗~
我有个困惑：为什么一定要转换成正余数，在循环里添加个判断条件(j>=(n-1)*a%p)会错呢？
s%n = (n-1)d1 +(n-2)d2+…+dn-1，不是要求余数相同吗？，全部转换成正余数后不就任务负余数等于正余数了嘛
要转化成正余数是因为要给他保证是数学意义上的取模，你加这个条件之后，少了太多的情况了
我觉得是为了保证数组不越界，就算是取余运算，s为负数的时候也是取余运算，那个余数条件成立的话应该也不影响结果，单纯只是为了不越界。
tqltql
第二层循环j为啥是枚举到n-1呢？
j是对n取余的余数 ，余数不能超过n
懂了谢谢
大佬们还是不太懂这个j-a*(n-i)的含义
上一行推出了(n-1)d1+(n-2)d2 + … + dn-1，可以得出通项为：
因为我们为了方便理解把含义等价了（d1换成dn-1），所以就要用j减去这个(n-i)*di
好的 谢谢大佬