石家庄营销型网站建设费用,护肤品网站建设的摘要,网站的开发环境怎么写,用什么做视频网站比较好的P1450 [HAOI2008]硬币购物
题意#xff1a;
共有 4 种硬币。面值分别为c1,c2,c3,c4c_1,c_2,c_3,c_4c1,c2,c3,c4。 某人去商店买东西#xff0c;去了 n 次#xff0c;对于每次购买#xff0c;他带了 did_idi枚 i 种硬币#xff0c;想购买 s 的价值的东西。请问…P1450 [HAOI2008]硬币购物
题意
共有 4 种硬币。面值分别为c1,c2,c3,c4c_1,c_2,c_3,c_4c1,c2,c3,c4。 某人去商店买东西去了 n 次对于每次购买他带了 did_idi枚 i 种硬币想购买 s 的价值的东西。请问每次有多少种付款方法。
题解
第一感觉是母函数但写不出来后来看题解时确实可以做NTT多项式求逆母函数麻烦而且跑的很慢不过洛谷可以过这里不做详细讲解可以看看代码 母函数做法的代码 我们这里讲下完全背包容斥的做法 如果题目没有数量的限制可以完全背包做法 现在有了数量限制我们可以用差分来求举个例子 [2,∞)−(3,∞)[2,∞)−[4,∞)[2,3][2,∞)−(3,∞)[2,∞)−[4,∞)[2,3][2,∞)−(3,∞)[2,∞)−[4,∞)[2,3],显然只要我们求出[2,∞)[2,∞)[2,∞)和(3,∞)(3,∞)(3,∞)就可以算出[2,3]。可以认为[x,∞)[x,∞)[x,∞)表示价值大于等于x的方案数可以用完全背包去求。 现在我们用完全背包先预处理出没有钱数限制的所有情况然后减去不合法情况(即某种硬币超出了所给数量)得到的不就是答案 ansf[s]−∑i14f[s−ci∗(di1)]ansf[s]-\sum_{i1}^{4}f[s-c_i*(d_i1)]ansf[s]−∑i14f[s−ci∗(di1)] 现在的任务就是求∑i14f[s−ci∗(di1)]\sum_{i1}^{4}f[s-c_i*(d_i1)]∑i14f[s−ci∗(di1)],可能会认为直接累加不就可以了并不是因为i1234这四部分并不是完全独立的换句话说有可能第一种物品超出限制的同时第二种也超出了如果直接累加必然会造成重复计算。这咋整这个模型很想中学学过的容斥原理 这个式子应该很熟悉 三元容斥
A∪B∪C(A∪B)∪CABC−A∩B−A∩C−B∩CA∩B∩C 扩展一下 奇加偶减 我们设四种硬币分别是ABCDcard(X)表示X集合元素个数 答案f[s]card(A⋃B⋃C⋃D)f[s]card(A\bigcup B\bigcup C\bigcup D)f[s]card(A⋃B⋃C⋃D) f[s]−ansf[s]-ansf[s]−ans anscard(A)card(B)card(C)card(D)−card(A⋂B)−card(A⋂C)−card(A⋂D)−card(B⋂C)−card(B⋂D)−card(C⋂D)card(A⋂B⋂C)card(A⋂B⋂D)card(B⋂C⋂D)−card(A⋂B⋂C⋂D)anscard(A)card(B)card(C)card(D)-card(A\bigcap B)-card(A\bigcap C)-card(A\bigcap D)-card(B\bigcap C)-card(B\bigcap D)-card(C\bigcap D)card(A\bigcap B\bigcap C)card(A\bigcap B\bigcap D)card(B\bigcap C\bigcap D)-card(A\bigcap B\bigcap C\bigcap D)anscard(A)card(B)card(C)card(D)−card(A⋂B)−card(A⋂C)−card(A⋂D)−card(B⋂C)−card(B⋂D)−card(C⋂D)card(A⋂B⋂C)card(A⋂B⋂D)card(B⋂C⋂D)−card(A⋂B⋂C⋂D) 我们刚才说了奇加偶减所以二进制枚举(第i位为0表示这个card()种并没有因为i否则有)直接从0(0000)枚举到15(1111)就可以。 本题难点还是在于将完全背包与容斥结合两个分开看都不算难
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn1e59;
ll ans,f[maxn];
int c[5];//面值
int d[5];//数量
void pre(){f[0]1;for(int i1;i4;i){for(int jc[i];j100001;j){f[j]f[j-c[i]];}}
}
int s;
void cal(){ans0;for(int i1;i(14)-1;i){ll k0,num0;for(int j0;j4;j){if(i(1j))//第j位是1{num;kc[j1]*(d[j1]1); } }ll flag1;if(num%20)flag-1*flag;if(sk)ansflag*f[s-k];}ansf[s]-ans;
}
int main()
{//rd_test();for(int i1;i4;i)cinc[i];pre();int t;read(t);while(t--){ans0;for(int i1;i4;i)cind[i];cins;cal();coutansendl;}//Time_test();
}
