快速傅里叶变换(容斥+dp)

    技术2025-07-14  8

    时间限制: 1 Sec  内存限制: 128 MB

    题目描述

    chen_03在切快速傅里叶变换(FFT)。 一共有n种FFT的题,他做出一道第i种题后能获得ci点的巨佬值。 他一共要打m场模拟赛,由于Rainy7的魔法,每次赛前,他的巨佬值会清零。 chen_03不希望他的巨佬值为0。为了获得一些巨佬值,每场模拟赛前,他都要去切FFT的题。然而他太巨了,Rainy7为了限制他的实力,又施了一个魔法,使得第i种题只有di道,且每道题在切完后会消失。 对于每场模拟赛,chen_03都有一个幸运数字,他想要知道在每场模拟赛前,他有多少种切题方式使他的巨佬值恰好等于s。 由于Rainy7的法力不稳定,每场模拟赛后di会更新,但ci不更新。

    输入

    第一行一个正整数,表示n。 第二行n个正整数以空格隔开,第i个数表示ci。 第三行一个正整数,表示m。 接下来m行,每行n+1个数,以空格隔开。在第r行中,前n个数中第i个数表示第r场模拟赛前的di。最后一个数表示第r场模拟赛的s。

    输出

    输出m行,每行一个正整数,表示 chen_03 每次模拟赛前的切题方案数。

    样例输入 Copy

    3 9 4 4 3 0 0 3 12 1 9 6 69 3 5 0 47

    样例输出 Copy

    1 1 1

    提示

    预处理n种物品不限量对s(<=200000)的方案数dp

    对于每一次的询问,根据容斥原理,s的不限量方案数-选择一种物品的超过限制量的方案数+选择两种物品的超过限制令的方案数-.....

    超过限制的求法:比如第一种物品限制为d[1],那么选择d[i] + 1个第一种物品,其他随意选择即为超过超过限制的方案数dp[s - c[1] * (d[1] + 1)]

     

    /**/ #include <cstdio> #include <cstring> #include <cmath> #include <cctype> #include <iostream> #include <algorithm> #include <map> #include <set> #include <vector> #include <string> #include <stack> #include <queue> typedef long long LL; using namespace std; int n, m, c[7], d[7]; LL dp[200005], ans; void dfs(int x, int num, int sum){ if(sum < 0) return ; if(x == n + 1){ if(num & 1) ans -= dp[sum]; else ans += dp[sum]; return ; } dfs(x + 1, num + 1, sum - (d[x] + 1) * c[x]); dfs(x + 1, num, sum); } int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &c[i]); dp[0] = 1; for (int i = 1; i <= n; i++){ for (int j = c[i]; j <= 200000; j++){ dp[j] += dp[j - c[i]]; } } scanf("%d", &m); for (int i = 1, s; i <= m; i++){ for (int j = 1; j <= n; j++) scanf("%d", &d[j]); scanf("%d", &s); ans = 0; dfs(1, 0, s); printf("%lld\n", ans); } return 0; } /**/

     

    Processed: 0.013, SQL: 9