补幺梨

传说中，早在公元前 $\text{114514}$ 年，有个神秘的国家，叫做补幺国。他们当时就已在用一种叫做“补幺梨”的货币，其因形状长得像梨子而得名。
补幺人通过“补幺梨”货币来进行交易。具体地，“补幺梨”有 n 种面值，分别为 $a_1,a_2,\cdots,a_n$ 。
补幺人认为，在他们的视野里，m 是“补幺梨”基本面值的上限。因此，他们为了尽可能让这些基本的面值能覆盖所有面额，这 ${n}$ 种面值是在 ${[1,m]}$ 内等概率随机的。
补幺国王掌管大权，每种”补幺梨“他都有 $\infty$ 枚。但是，即便他拥有再多的硬币，他还是很惊叹竟然有这些”补幺梨“凑不出的面额！

古人的智商自然是有限的，因此他们只能意识到问题，但不能解决问题。

作为十万年后的我们，古人借助时光机向我们发出求助。你需要帮他们计算出最大的不能被表示的面额。

本场比赛大样例：https://uploadfiles.nowcoder.com/files/20211016/%E5%A4%A7%E6%A0%B7%E4%BE%8B.zip

第一行，输入三个数 ${n,m,seed}$ ，表示“补幺梨”的面值种数，基本货币的金额上限，以及随机种子。

对于 $a_1,a_2,\cdots,a_n$ ，“补幺人”通过下述 c++ 程序的 mt19937 随机数得到（需 c++11）：

int main() {   scanf("%d%d%d", &n, &m, &seed);   mt19937 rng(seed);   auto get = [&]() {     uniform_int_distribution<int> qwq(2, m);     return qwq(rng);   };   for (int i = 1; i <= n; i++) {     a[i] = get();   } }

注意，样例仅作为参考。该数据范围不会出现在最终测试数据中。

#include<bits/stdc++.h> using namespace std; const int N=10000005; typedef long long LL; int n,m,seed,a[N],M; LL dis[N],ans; bool vs[N]; priority_queue<pair<LL,int> > q; int main() { scanf("%d%d%d", &n, &m, &seed);M=m;mt19937 rng(seed); auto get = [&]() {uniform_int_distribution<int> qwq(2, m);return qwq(rng);}; for(int i=1;i<=n;i++) a[i]=get(),M=min(M,a[i]); q.push(make_pair(0,0)); for(int i=1;i<M;i++) dis[i]=1e18; while(q.size()) { int x=q.top().second;q.pop(); if(vs[x]) continue;vs[x]=1; for(int i=1,y=(x+a[i])%M;i<=n;y=(x+a[++i])%M) if(dis[y]>dis[x]+a[i]) dis[y]=dis[x]+a[i],q.push(make_pair(-dis[y],y)); } for(int i=1;i<M;i++) ans=max(ans,dis[i]-M); printf("%lld",ans);return 0; }

详情