AcWing 1214. 波动数列
原题链接
中等
作者:
Fairy2.0
,
2025-01-03 20:37:08
,
所有人可见
,
阅读 3
#include <iostream>
#include <algorithm>
using namespace std;
//数列的第一个是数是可以取任意的数,没有限制
//第一个数的取值影响后面的数
//比如第一个数取x的话
//从第二个数开始到第n个数应该是
//x + d1 , x + d1 + d2 , x + d1 + d2 + d3 ···· , x + d1 + d2 + ··· + dn-1
//取值di(i从1到n-1)的取值只有2中情况(a , -b)
//将这n个数加起来,整理得:
//sun = n*x + (n-1)d1 + (n-2)*d2 + ··· + dn-1
//因为sum 要等于s
//整理得:
//x = (s - ((n-1)d1 + (n-2)*d2 + ··· + dn-1)) / n
//因为x属于整数且没有任何的限制,所以只要有这样子的x就有一个方案
//所以有分子一定要是n的倍数(不然不可能整除)
//即有s % n == ((n-1)d1 + (n-2)*d2 + ··· + dn-1) % n
//这里每一项都要取
//问题就变成了当d1,d2,d3···dn-1 取a或者-b(随机取)和模上n等于s % n的方案数
//组合问题就可以用类似背包的做法
const int mod = 100000007;
const int N = 1010;
//f[i][j] 表示前i个数和模上n后为j的方案数
//ans == f[n - 1][s % n]
//状态转移:
//根据di取的是a还是-b划分
//当di是a时(di是a后和模上n为j,需要求出i-1的和模上n后是多少)
//f[i][j] += f[i - 1][(j - (n - i) * a) % n]
//当di-1是-b时
//f[i][j] += f[i - 1][(j + (n - i) * b) % n]
int f[N][N];
int n;
int s;
int a;
int b;
int get_mod(int a , int b){
//求a % b的正余数
return (a % b + b) % b;
}
int main (){
cin >> n >> s >> a >> b;
//初始化
f[0][0] = 1; //一个数都还没拿,模的值为0的本身就是一个方案
//f[1][get_mod((n-1)*a , n)] = 1;
//f[1][get_mod((n-1)*b , n)] = 1;
for (int i = 1;i < n;i++){ //除去x后还有n-1个数
for (int j = 0;j < n;j++){ //%n后的范围为0到n-1
f[i][j] = f[i - 1][get_mod(j - (n - i) * a , n)] % mod;//di取a
//di取-b
f[i][j] = (f[i][j] + f[i - 1][get_mod(j + (n - i) * b , n)]) % mod;
}
}
cout << f[n - 1][get_mod(s , n)];
return 0;
}