2021.12.06 P1450 [HAOI2008]硬币购物（组合数学+抽屉原理+DP）

2021.12.06 P1450 [HAOI2008]硬币购物（组合数学+抽屉原理+DP）

https://www.luogu.com.cn/problem/P1450

题意：

共有 44 种硬币。面值分别为 \(c_1,c_2,c_3,c_4\)。

某人去商店买东西，去了 \(n\) 次，对于每次购买，他带了 \(d_i\) 枚 \(i\) 种硬币，想购买 \(s\) 的价值的东西。请问每次有多少种付款方法。

分析：

设有且仅有一种硬币，价值为 \(c\) ，有 \(d\) 枚。现在想买价值为 \(s\) 的东西，在不限硬币个数的情况下的方案数为 \(f_s\) ，超出 \(d\) 枚的方案分别是取 \(d+1\) 枚、取 \(d+2\) 枚、取 \(d+3\) 枚……如果现在强制取 \(d+1\) 枚，那么再往上添一毛钱都不行！因为我们最少就取了 \(d+1\) 枚价值为 \(c\) 的硬币。

\(d+1\) 枚硬币的价值为 \(c*(d+1)\) ，还剩下的价值为 \(s-c*(d+1)\) ，剩下的无论怎么取一定会超过 \(d\) 枚硬币的方案数为 \(f_{s-c*(d+1)}\) 。因为选取价值为 \(c*(d+1)\) 硬币的方案数为 \(1\) ，即选取 \(d+1\) 枚硬币，根据乘法原理得，选取超过 \(d\) 枚硬币大的方案数为

\(ans=1*f_{s-c*(d+1)}=f_{s-c*(d+1)}\) ，

则满足条件的方案数为 \(f_s-ans\) 。

设我们有两种硬币，价值分别为 \(c_i\) 、 \(c_j\) ，分别有 \(d_i\) 枚、 \(d_j\) 枚。现在依旧想买价值为 \(s\) 的东西，超出 \(d_i\) 的方案数为 \(f_{s-c_i*(d_i+1)}\) ，超出 \(d_j\) 的方案数为 \(f_{s-c_j*(d_j+1)}\) 。但是存在即超出 \(d_i\) 又超出 \(d_j\) ，这种情况的方案数为 \(f_{s-c_i*(d_i+1)-c_j*(d_j+1)}\) 。根据容斥原理得，超出的总方案数为

\(tot=f_{s-c_i*(d_i+1)}+f_{s-c_j*(d_j+1)}-f_{s-c_i*(d_i+1)-c_j*(d_j+1)}\) ，

则满足条件的方案数为 \(f_s-tot\) 。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

#define int long long

const int N=1e5+10;

int n,c[5],num[5],s,f[N];

signed main(){

	IOS;

	for(int i=1;i<=4;i++)cin>>c[i];

	f[0]=1;

	for(int i=1;i<=4;i++)for(int j=c[i];j<=N-10;j++)f[j]+=f[j-c[i]];

	cin>>n;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=4;j++)cin>>num[j];cin>>s;

		int ans=f[s];

		for(int k=15;k>0;k--){

			int flag=0,ki=k,tot=0,aim=0;

			while(ki){

				++aim;

				if(ki&1)tot+=(num[aim]+1)*c[aim],flag^=1;

				ki>>=1;

			}

			if(tot>s)continue;

			if(flag)ans-=f[s-tot];

			else ans+=f[s-tot];

		}

		cout<<ans<<endl;

	}

	return 0;

}

2021.12.06 P1450 [HAOI2008]硬币购物（组合数学+抽屉原理+DP）的相关教程结束。