P2946 Cow Frisbee Team S 01背包方案数

前言

晕晕晕晕 😦 学 S p r i n g Spring Spring 学废了好几天了

传送门 :

思路

看了本题,好像就是问有几种方案可以组成 某个数 (但是指定是倍数

那么我们就取模就是了 (每次都取模,如果为 0 0 0的话,那么就是倍数)

所以我们只需要变换一下方程即可

f [ i ] [ j ] + = f [ i − 1 ] [ ( ( j − a [ i ] ) % m + m ) % m ] f[i][j]+=f[i-1][((j-a[i])\%m+m)\%m] f[i][j]+=f[i−1][((j−a[i])%m+m)%m]

这样处理是为了防止出现负数

CODE

const int N  = 2e3+10 ,mod = 1e8;
int f[N][N],a[N];
int n,m;

void solve()
{
	cin>>n>>m;
	for(int i=1;i>a[i];
		f[i][a[i]%m] = 1;
	} 
	
	for(int i=1;i