[RC-04] 01 背包

题目描述

P7223 [RC-04] 01 背包 – 洛谷

有一个容积为 正无穷 的背包,你要往里面放物品。

你有 \(n\) 个物品,第 \(i\) 个体积为 \(a_i\)

你有一个幸运数字 \(p\),若放入的物品体积和为 \(k\),你会得到 \(p^k\) 的收益。特别地,\(0^0=1\)

求所有 \(2^n\) 种放入物品的方案的收益和。答案很大,因此请输出它对 \(998244353\) 取模的值。

输入格式

第一行两个整数 \(n,p\)

接下来一行 \(n\) 个正整数 \(a_1\sim a_n\),描述这 \(n\) 个物品的体积。

输出格式

输出一个整数,为所有 \(2^n\) 种方案的收益和对 \(998244353\) 取模的值。

样例 #1

样例输入 #1

2 2
1 4

样例输出 #1

51

提示

【样例解释】

答案为 \(2^0+2^1+2^4+2^5=51\)

【数据范围】

对于所有数据,\(1\le n\le 10^6\)\(0\le p,a_i<998244353\)

详细数据范围如下表:

测试点编号 \(n\) \(p\) \(\sum_{i=1}^na_i\) 每测试点分数
\(1\) \(=0\) \(2\)
\(2\sim 5\) \(\le 22\) \(6\)
\(6\sim 9\) \(\le 1000\) \(\le 1000\) \(6\)
\(10\sim 14\) \(\le 100000\) \(\le 100000\) \(5\)
\(15\) \(25\)

解析

递归枚举所有方案

所有的方案个数为 \(nums\le2^{1000000}\)

理想情况下,最多只能拿到测试点编号2~5的分数

注意要对MOD使用finnal关键字

java中final 与效率_fa1d1的博客

import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n;
    static int p;
    static int[] w;
    static long ans = 0;
    static final int MOD = 998244353;//一定要用final关键字!!!
    public static void main(String[] args) {
        n = sc.nextInt();
        p = sc.nextInt();
        w = new int[n];
        for (int i = 0; i < n; ++i) {
            w[i] = sc.nextInt();
        }
        dfs(0,0);
        System.out.println(ans);
    }
    static void dfs(int len, long sum) {
        if (len == n) {
            ans = (ans + pow(p, sum)) % MOD;
            return;
        }
        dfs(len + 1, sum);//如果不选择当前物品
        dfs(len + 1, sum + w[len]);//如果选择当前物品
    }
    static long pow(long x, long n) {//尽量使用位运算优化
        long ans = 1;
        for (; n != 0; n >>= 1, x = x * x % MOD) {
            if ((n & 1) == 1) ans = ans * x % MOD;
        }
        return ans;
    }
}

数学推导

\(X\)个物品的总收益记为\(ans_x\),前\(X-1\)个物品的总收益记为\(ans_{x-1}\)

以下关注\(ans_x\)的性质

设每种方案的总体积为\(k_i\),其中 \(i\epsilon[1,2^x]\)

\(ans_x=\sum_{i=1}^{2^x}p^{k_i}\)

对于所有方案都增加\(V\)体积

则总收益变为\(\sum_{i=1}^{2^x}p^{k_i+V}=p^{k_i+V}\times\sum_{i=1}^{2^x}p^{k_i}=p^{k_i+V}\times ans_x\)

所以,若每种方案的体积都增加\(V\),相当于乘以\(p^{k_i+V}\)

考虑第\(X\)个物品的 \(ans_x\)

每种物品仅有两种情况

  1. 不选该物品,由于任意一种方案的物品总体积不变,则对\(ans_{x-1}\)无影响
  2. 选择该物品,对任意一种方案的物品总体积增加\(V_x\),则\(ans_{x-1}\times p^{V_x}\)

\(ans_x\)为这两种情况的价值的和

\(ans_x=ans_{x-1}+ans_{x-1}\times p^{V_x}=ans_{x-1}\times(1+p^{V_x})\)

\[\therefore \dfrac{ans_x}{ans_{x-1}}=1+p^{V_x} \]

根据累乘法得:\(\dfrac{ans_x}{ans_0}=\)

\(ans_0\)表示当前无任何物品,即\(V=0\)

\(\therefore ans_0=p^V=p^0=1\)

\(\therefore ans_x=\prod_1^x(1+p^{V_x})\)

import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static final long MOD = 998244353;
    static int n;
    static long ans = 1l, p;
    static int[] V;

    static long powMod(long a, int b) {
        long ret = 1;
        for (; b != 0; b >>= 1, a = a * a % MOD)
            if ((b & 1) == 1) ret = ret * a % MOD;
        return ret;
    }

    public static void main(String[] args) {
        n = sc.nextInt();
        p = sc.nextLong();
        V = new int[n];
        for (int i = 0; i < n; ++i) V[i] = sc.nextInt();
        for (int v : V) ans = ans * (1l + powMod(p, v)) % MOD;
        System.out.println(ans);
    }
}

原文地址:http://www.cnblogs.com/Cattle-Horse/p/16884120.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性