python做网站难么,杭州工程建设网,wordpress图形验证码,医疗网站建设平台价格思路
完全背包#xff1a;预处理出不限制硬币数量的方案数。
dp[0]1;
dfor(i,1,4) dfor(j,c[i],(int)1e5) dp[j]dp[j-c[i]];容斥
不限制数量的方案数 − - − 超出限制的方案数 符合限制的方案数 。考虑第 i i i 种硬币超出数量限制的方案数。强制支付 d i 1 d_i1 di…思路
完全背包预处理出不限制硬币数量的方案数。
dp[0]1;
dfor(i,1,4) dfor(j,c[i],(int)1e5) dp[j]dp[j-c[i]];容斥
不限制数量的方案数 − - − 超出限制的方案数 符合限制的方案数 。考虑第 i i i 种硬币超出数量限制的方案数。强制支付 d i 1 d_i1 di1 个 i i i 种硬币价值为 c i ∗ ( d i 1 ) c_i*(d_i1) ci∗(di1) 此时再支付硬币 i i i 一定是超出限制的。得超出硬币 i i i 限制的价值为 s − c i ∗ ( d i 1 ) s-c_i*(d_i1) s−ci∗(di1) 方案数为 d p [ s − c i ∗ ( d i 1 ) ] dp[s-c_i*(d_i1)] dp[s−ci∗(di1)]。上述得出超出硬币 i i i 价值为 s − c i ∗ ( d i 1 ) s-c_i*(d_i1) s−ci∗(di1) 这只是一种硬币的情况如果不止一种硬币你无法保证价值 s − c i ∗ ( d i 1 ) s-c_i*(d_i1) s−ci∗(di1) 中是否包含了硬币 j j j 的符合限制的价值也就是说 d p [ s − c i ∗ ( d i 1 ) ] dp[s-c_i*(d_i1)] dp[s−ci∗(di1)] 中有硬币 j j j 符合限制的方案数。硬币 i i i 超出限制集合表示为 A i A_i Ai 硬币 j j j 超出限制集合表示为 A j A_j Aj A i ∪ A j A i A j − A i ∩ A j A_i\cup A_jA_iA_j-A_i\cap A_j Ai∪AjAiAj−Ai∩Aj不多说奇加偶减 。不限制集合设为 S S S答案集合 a n s S − ( A i ∪ A j ∪ … ) ansS-(A_i\cup A_j\cup \ldots) ansS−(Ai∪Aj∪…)。
二进制
用每一位表示一种硬币 1 1 1 那一位存在硬币 0 0 0 反之。如 0101 0101 0101 表示第 3 3 3 种硬币和第 1 1 1 种的并集。
dfor(i,1,15)
{re int cnt0,sum0;dfor(j,0,3)if(i(1j)) cnt,sumc[j1]*(d[j1]1);int fcnt1?-1:1;if(ssum) ansf*dp[s-sum];
}Think Twice, Code Once
#includebits/stdc.h
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define re register
#define int long long
#define dfor(i,a,b) for(re int ia;ib;i)
#define dforr(i,a,b) for(re int ia;ib;--i)
#define dforn(i,a,b) for(re int ia;ib;i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) couta,put(32)
#define INF 0x7fffffff
#define tt(x) coutx\n
#define ls i1
#define rs i1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x-x)
using namespace std;
typedef unsigned int ull;
int read(void)
{re int x0,f1;re char cget();while(!is(c)) (fc45?-1:1),cget();while(is(c)) x(x1)(x3)(c^48),cget();return x*f;
}
void write(int x)
{if(x0) x-x,put(45);if(x9) write(x/10);put((x%10)^48);
}
#define writeln(a) write(a),put(10)
#define writesp(a) write(a),put(32)
#define writessp(a) put(32),write(a)
const int N1e510,M3e410,SN1e410,mod998244353;
int n,s,c[5],d[5],dp[N];
signed main()
{dfor(i,1,4) c[i]read();nread();dp[0]1;dfor(i,1,4) dfor(j,c[i],(int)1e5) dp[j]dp[j-c[i]];while(n--){dfor(i,1,4) d[i]read();sread();re int ansdp[s];dfor(i,1,15){re int cnt0,sum0;dfor(j,0,3)if(i(1j)) cnt,sumc[j1]*(d[j1]1);int fcnt1?-1:1;if(ssum) ansf*dp[s-sum];}writeln(ans);}return 0;
}
