AcWing 1214. 波动数列
原题链接
中等
作者:
ofs
,
2024-04-11 23:36:21
,
所有人可见
,
阅读 2
//0-1背包问题变形
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define end "\n"
#define int long long
using namespace std;
const int N=1010,MOD=100000007;
int f[N][N];
int get_mod(int a,int b) //求a除以b的正余数 对于c++来说,负数除以某数,得到的是负余数,有时候需要正余数
{
return (a%b+b)%b;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,s,a,b;
cin>>n>>s>>a>>b;
//初始化 当一个数都不取的时候,余数一定是0,不存在其他情况,且只有一个方案
f[0][0]=1;
for(int i=1;i<n;i++) //从第一项到第n-1项
for(int j=0;j<n;j++) //余数从0-n-1
{
f[i][j]=(f[i-1][get_mod(j-i*a,n)] +f[i-1][get_mod(j+b*i,n)])%MOD;
}
cout<<f[n-1][get_mod(s,n)]<<endl;//注意第二个下标不能直接写成s%n,因为s可能是负数,所以应该也要求正余数
return 0;
}