脚本宝典收集整理的这篇文章主要介绍了【BZOJ3157 国王奇遇记】+【BZOJ3516 国王奇遇记加强版 】题解,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
由于BZOJ已挂,这里是黑暗爆炸和hydro的备份
黑暗爆炸:
hydro:
Katharon 国有着悠久的历史,每个慕名而来的游客都渴望能在 Katharon 国发现一些奇怪的宝藏。而作为国王的 Kanari 君也梦想着有一天发现自己国家的宝藏,从而成为世界上最富有的人。 Kanari 国王和 katherine 皇后凭着 14 年真挚的感情,数十年如一日甜蜜地生活在一起。前几天恰逢劳动节放假, Kanari 国王便和 Katherine 皇后一同前往电影院观看了最新出版的电影《致青春》。看完之后两人对青春又有了更深刻的认识。然而在返程的路上,他们突然在路边的小树林里发现了一块奇怪的石板,上面印着一行小字:“如果你能破解下面表达式的结果,你就可以拥有 Katharon 国最珍贵的财产。”这时 Kanari 国王和 Katherine 皇后再也顾不上秀恩爱了,只好拿出草纸拼命计算这个表达式的结果。可是两人能力有限,现在,他们找到擅长数学的你,想请你来帮助他们完成这个愿望,如果你能回答正确,他们愿意把 Katharon 国最珍贵的财产分给你一半哦。这个表达式就是:
∑i=1nim×misum_{i=1}^n i^m times m^i i=1∑nim×mi
题目就是求:
由于 (m) 很小,(n) 很大,所以考虑dp。
设 (dp_i) 表示:
假设我们要求 ((m-1)dp_i)。
则:
带入 (dp) 的定义:
把前面的 (m) 弄进去:
把 (m^{j+1}) 变成 (m^j):
把 (sum_{j=2}^{n+1}) 变成 (sum_{j=1}^n),也就是我们要减去一项 (j=1) 再加上一项 (j=n+1)
化简:
后面的合并:
其中 ((j-1)^m) 可以用二项式定理化简。
强行把 (k=i) 的情况提出来:
化简:
调整一下顺序:
明显,(sum_{j=1}^nm^jj^k) 就是 (dp) 的定义,所以
而这个式子是 ((m-1)dp_i),所以 (dp_i) 为:
(O(m^2)) dp,初始化注意一下即可。
// PRoblem: L - 国王奇遇记
// Contest: Virtual Judge - 2021.12.12校内作业
// URL: https://vjudge.net/contest/472915#problem/L
// Memory LimIT: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cPEditor.org)
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define mo 1000000007
#define N 1020
int n, m, i, j, k;
int jc[N], f[N], p_1[N];
int kuai(int a, int b)
{
int ans=1;
while(b)
{
if(b&1) ans=(ans*a)%mo;
b>>=1;
a=(a*a)%mo;
}
return ans;
}
int C(int m, int n)
{
return jc[m]*kuai(jc[n]*jc[m-n]%mo, mo-2)%mo;
}
signed main()
{
// freopen("tiaoshi.in","r",stdin);
// freopen("tiaoshi.out","w",stdout);
for(i=jc[0]=1; i<=1010; ++i)
jc[i]=jc[i-1]*i%mo;
for(i=0; i<=1010; ++i) p_1[i]=(i%2==1 ? -1 : 1);
n=read(); m=read();
if(m==1) return printf("%lld", (1+n)*n/2%mo), 0;
f[0]=(kuai(m, n+1)-m)*kuai(m-1, mo-2)%mo;
for(i=1; i<=m; ++i)
{
f[i]=kuai(n, i)*kuai(m, n+1)%mo;
for(k=0; k<=i-1; ++k)
f[i]=(f[i]+C(i, k)*f[k]%mo*p_1[i-k])%mo;
f[i]=f[i]*kuai(m-1, mo-2)%mo;
}
printf("%lld", (f[m]%mo+mo)%mo);
return 0;
}
以上是脚本宝典为你收集整理的【BZOJ3157 国王奇遇记】+【BZOJ3516 国王奇遇记加强版 】题解全部内容,希望文章能够帮你解决【BZOJ3157 国王奇遇记】+【BZOJ3516 国王奇遇记加强版 】题解所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。