赛博朋克（多重背包问题）
题目背景
以下为介绍，但不是打广告
《赛博朋克 2077 ：往日之影》作为一款备受期待的资料片，为玩家带来了全新的游戏体验和故事情节。在这个资料片中，玩家将继续扮演 V ，一个在赛博朋克世界中寻求解药的赏金猎人。这次， V 被卷入了狗镇和新美国之间的明争暗斗，为了寻找解药，V 必须深入敌后，与敌人展开一场惊心动魄的斗争。
在“往日之影”任务中， V 将与多年潜伏于狗镇的所罗门·李德等其他特工合作，共同对抗狗镇的领导者库尔特·汉森。这些角色各具特色，为游戏增添了更多的故事性和角色互动。同时，他们还需寻找在坠机事件后失踪的总统贴身特工百灵鸟（宋昭美），这也为游戏的剧情增加了更多悬念。
资料片的任务设计针对本体游戏中一些玩家提出的批评进行了改进，比如任务形式单一、叙事松散等问题。从玩家进入狗镇看到空天一号坠毁的场景开始，整个资料片的任务设计都致力于营造紧张刺激的谍战氛围，提供了一系列贴合主题的精彩任务。这些任务不仅让玩家沉浸在游戏的世界观中，还通过多样化的任务形式，增强了游戏的可玩性。
此外，《赛博朋克 2077 ：往日之影》还为游戏的世界观增添了更多深度和色彩。在这个充满科技与黑暗的赛博朋克世界中，玩家将更深入地了解各个势力之间的纷争和利益纠葛，以及隐藏在这个世界中的种种秘密。这些新的故事元素不仅丰富了游戏的背景设定，还为玩家提供了更多的探索空间。
总的来说，《赛博朋克 2077 ：往日之影》是一款令人期待的资料片，它不仅为玩家带来了新的剧情和角色，还通过更加紧凑和多样化的任务设计，增强了游戏的可玩性和故事性。这个资料片将为《赛博朋克 2077 》的世界观增添更多深度和色彩，为玩家带来一个全新的游戏体验。
题目描述
小 L 最近正在很认真的玩这款游戏，他即将就要通关了，但某个剧情（直到大厦崩塌）卡住了：百灵鸟（宋昭美）被黑墙（黑墙的里面是强大的 AI ，黑墙的外边是人们正常交流的网络）所控制（其实当时小 L 选择在潜入并准备解决汉森的时候，此时百灵鸟要求 V 走到核心反应器拿出神经矩阵来对付汉森然后计划打算跟 V 一起摆脱联情局进而来治疗百灵鸟和 V 的病（ V 在之前跟德克斯特合作，偷取
R
e
l
i
c
Relic
Relic 芯片，导致 V 的脑子里面还有个人—— Jony ，V 时长会梦到 Jony 的生前发生的事），但小 L 选择背叛百灵鸟，使得百灵鸟不小心被暗网所控制，哈哈哈哈，百灵鸟后来说你背叛了我，我不会原谅你，这句话说了好多遍），主人公 V 受李德的命令，跟随百灵鸟的踪迹去拯救百灵鸟，跟随着她进入了百灵鸟之前所在的实验室，但这实验室非常恐怖……
7-1
7-2
在这实验室中，小 L 最怕的机器人，它的口头禅：“竹篮打水，白费力气”。（在这特定的情况下是真的很恐怖，说了这句话就会被它抓到（如图 7-1， 7-2 ），吓尿了！！！）
此刻，小 L 准备要摧毁 N N N 处房间（其实六处，但这里出题就改成很多）的防火墙，为了关闭它而更快的让百灵鸟解脱，并且此时还有机器人在巡逻（被发现就直接结束），而且 V 在每个房间用于摧毁防火墙的 R A M RAM RAM（也就是一种单位） 数量和占用不同，而且 R A M RAM RAM 摧毁防火墙的时间各不相同，我们这边就设第 i i i 处房间的防火墙，V 有 S i S_i Si 种 R A M RAM RAM ，每种 R A M RAM RAM 摧毁防火墙需要 T i T_i Ti 个时间。
7-3
7-4
以上是地图（如图 7-3， 7-4 ）（来源于 B站 ）
现在，小 L 希望 V 摧毁防火墙的策略能够至少达到 M M M 种，请问， V 需要花多少时间？
小 L 知道你编程很好，因此邀请你来解决这个问题。
注意：这里的小 L 是玩家， V 是游戏主人公。
输入格式
输入第一行，两个整数 N N N ， M M M 。
输入第二行， N N N 个整数，表示每个房间 V 拥有的 R A M RAM RAM 的种类数 S i S_i Si 。
输入第三行， N N N 个整数，表示每种 R A M RAM RAM 摧毁每个防火墙的需要的时间的 T i T_i Ti 。
输出格式
第一行，输出一个整数， V 摧毁防火墙的策略能够至少达到 M M M 种。
第二行，输出 M M M 的乘法逆元（对 1 , 000 , 000 , 007 1,000,000,007 1,000,000,007 的取模）。
样例 #1
样例输入 #1
2 5
3 3
1 1
样例输出 #1
5
400000003
样例 #2
样例输入 #2
2 7
3 3
1 1
样例输出 #2
6
166666668
提示说明
测试点有点小多呢
样例解释
样例一：每一个房间 V 有 3 3 3 种 R A M RAM RAM ，每种 R A M RAM RAM 摧毁每个防火墙需要的时间均为 1 1 1 ，那么第一个房间用 3 3 3 种 R A M RAM RAM ，第二个房间用 2 2 2 种 R A M RAM RAM ， 3 × 2 ≥ 5 3 \times 2 \ge 5 3×2≥5，共花费 3 + 2 = 5 3+2=5 3+2=5 时间。
样例一图解（介绍其中的一种涂法，涂法不唯一）：
样例二：每一个房间 V 有 3 3 3 种 R A M RAM RAM ，每种 R A M RAM RAM 摧毁每个防火墙需要的时间均为 1 1 1 ，那么第一个房间用 3 3 3 种 R A M RAM RAM ，第二个房间用 3 3 3 种 R A M RAM RAM ， 3 × 3 ≥ 7 3 \times 3 \ge 7 3×3≥7，共花费 3 + 3 = 6 3+3=6 3+3=6 时间。
样例二图解（介绍其中的一种涂法，涂法不唯一）：
上述图片黑色为选中
数据范围
0 ≤ M ≤ 1 0 17 0\leq M \leq 10^{17} 0≤M≤1017， 0 ≤ N ≤ c f ′ ( x ) 0\leq N\leq cf'(x) 0≤N≤cf′(x)， 0 ≤ S i 0 \leq S_i 0≤Si， T i ≤ 1 0 3 T_i \leq 10^3 Ti≤103，且保证题目有解。
上述的 c f ′ ( x ) cf'(x) cf′(x) 你想知道，小 L 希望你帮他求解如下小问题：
已知函数 f ( x ) = g ( x ) g ( x ) f(x)=g(x)^{g(x)} f(x)=g(x)g(x)，其中 g ( x ) = 1 x − l n x g(x)=\frac{1}{x}-lnx g(x)=x1−lnx， 求 c f ′ ( x ) cf'(x) cf′(x) 在 x = 1 x=1 x=1 处的值。其中 c = − 100 c=−100 c=−100。
声明
好了，我感觉题目就这样出吧，6月份不想出了。
希望后面的我们团队——就我们没实力越来越棒，加油！
// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//队列
// #include <queue>//堆/优先队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
const ll N=1e6+10;
ll s[N],t[N];
ll dp[N];
//快速幂
ll qmi(ll a,ll b,ll p)
{
//当b = 0,p = 1时
//①不 % p ,结果是 1
//② % p ,结果是 0(正确答案)
ll ans=1%p;//注意:5 0 1
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;//右移 1 位
}
return ans;
}
int main()
{
ll n,m;
cin>>n>>m;
for(ll i=1;i<=n;i++)
cin>>s[i];
ll sum=0;
for(ll i=1;i<=n;i++)
{
cin>>t[i];
sum+=s[i]*t[i];//总耗时
}
dp[0]=1;
for(ll i=1;i<=n;i++)
for(ll j=sum;j>=0;j--)
for(ll k=1;k<=s[i]&&k*t[i]<=j;k++)
dp[j]=max(dp[j],dp[j-k*t[i]]*k);
ll res=0;
while(res<=sum&&dp[res]<m) res++;
//res * x ≡ 1 (mod p)//乘法逆元
//res^{p-1} ≡ 1 (mod p)//费马定理
//res * res^{p-2} ≡ 1 (mod p)
//(res*x)模 p 余 1
//x = res^{p-2} (mod p);
//res = x
ll ans=qmi(res,p-2,p);
cout<<res<<endl;//M策略的数量
cout<<ans<<endl;//M的乘法逆元
return 0;
}