【bzoj 2159】Crash 的文明世界

2023-10-20 12:50
文章标签 世界 bzoj crash 文明 2159

本文主要是介绍【bzoj 2159】Crash 的文明世界,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

Crash小朋友最近迷上了一款游戏——文明5(Civilization V)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。现在Crash已经拥有了一个N个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此Crash只修建了N-1条道路连接这些城市,不过可以保证任意两个城市都有路径相通。在游戏中,Crash需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的:$S(i)=\sum _{j=1}^Ndist(i,j)^k$。其中S(i)表示第i 个城市的指标值,dist(i, j)表示第i个城市到第j个城市需要经过的道路条数的最小值,k为一个常数且为正整数。因此Crash交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数 mod 10007 的值。

Input

输入的第一行包括两个正整数N和k。下面有N-1行,每行两个正整数u、v (1 ≤ u, v ≤ N),表示第u个城市和第v个城市之间有道路相连。这些道路保证能符合题目的要求。

Output

输出共N行,每行一个正整数,第i行的正整数表示第i个城市的指标值 mod 10007 的值。

 

用结论来化简式子:$x^n=\sum _{i=1}^n S(n,i)\cdot F(x,i)$

$S(n,i)$为第二类斯特林数,$F(x,i)=\frac{x!}{(x-i)!}$

可得:$$\begin{align*} ans(i)&=\sum _{j=1}^ndist(i,j)^m\\ &=\sum_{j=1}^{n}\sum_{k=1}^{m}S(m,k)\cdot F(dist(i,j),k)\\ &=\sum_{k=1}^{m}S(m,k)\sum_{j=1}^{n} F(dist(i,j),k)\\ &=\sum_{k=1}^{m}S(m,k)\cdot k!\cdot \sum_{j=1}^{n} C(dist(i,j),k) \end{align*}$$

根据组合数递推公式:$C(n,m)=C(n-1,m)+C(n-1,m-1)$ 就可以很方便的对后面的部分进行树形dp了。

具体地,令 $up(x,i)$ 为不在 $x$ 的子树中的部分的贡献,令 $dn(x,i)$$x$ 的子树的贡献。特别的,$dn(x,0)=1$

详见代码。

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 using namespace std;
 6 const int N=5e4+5;
 7 const int M=155;
 8 const int mod=1e4+7;
 9 int n,m,u,v,cnt,ans,tmp;
10 int first[N],fac[M],s[M][M];
11 int up[N][M],dn[N][M];
12 struct edge{int to,next;}e[N*2];
13 int read()
14 {
15     int x=0,f=1;char c=getchar();
16     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
17     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
18     return x*f;
19 }
20 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
21 void Mod(int& a,int b){a+=b;if(a>=mod)a-=mod;}
22 void dfs1(int x,int fa)
23 {
24     dn[x][0]=1;
25     for(int i=first[x];i;i=e[i].next)
26     {
27         int to=e[i].to;
28         if(to==fa)continue;
29         dfs1(to,x);
30         Mod(dn[x][0],dn[to][0]);
31         for(int j=1;j<=m;j++)
32             Mod(dn[x][j],(dn[to][j]+dn[to][j-1])%mod);
33     }
34 }
35 void dfs2(int x,int fa)
36 {
37     if(fa!=-1)
38     {
39         up[x][0]=n-dn[x][0];
40         for(int i=1;i<=m;i++)
41         {
42             Mod(up[x][i],(up[fa][i]+up[fa][i-1])%mod);
43             Mod(up[x][i],(dn[fa][i]+dn[fa][i-1])%mod);
44             Mod(up[x][i],(2*mod-dn[x][i]-dn[x][i-1])%mod);
45             Mod(up[x][i],(mod-dn[x][i-1])%mod);
46             if(i!=1)Mod(up[x][i],(mod-dn[x][i-2])%mod);
47         }
48     }
49     for(int i=first[x];i;i=e[i].next)
50         if(e[i].to!=fa)dfs2(e[i].to,x);
51 }
52 int main()
53 {
54     int L,now,A,B,Q;
55     n=read();m=read();L=read();
56     now=read();A=read();B=read();Q=read();
57     for(int i=1;i<n;i++)
58     {
59         now=(now*A+B)%Q;
60         tmp=i<L?i:L;
61         u=i-now%tmp;v=i+1;
62         ins(u,v);ins(v,u);
63     }
64 //    n=read();m=read();
65 //    for(int i=1;i<n;i++)
66 //    {
67 //        u=read();v=read();
68 //        ins(u,v);ins(v,u);
69 //    }
70     fac[0]=s[0][0]=1;
71     for(int i=1;i<=m;i++)
72     {
73         fac[i]=fac[i-1]*i%mod;
74         for(int j=1;j<=i;j++)
75             s[i][j]=(s[i-1][j]*j+s[i-1][j-1])%mod;
76     }
77     dfs1(1,-1);dfs2(1,-1);
78     for(int i=1;i<=n;i++)
79     {
80         ans=0;
81         for(int j=1;j<=m;j++)
82             Mod(ans,s[m][j]*fac[j]%mod*(up[i][j]+dn[i][j])%mod);
83         printf("%d\n",ans);
84     }
85     return 0;
86 }
View Code

 

转载于:https://www.cnblogs.com/zsnuo/p/8926030.html

这篇关于【bzoj 2159】Crash 的文明世界的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/247198

相关文章

揭秘世界上那些同时横跨两大洲的国家

我们在《世界人口过亿的一级行政区分布》盘点全球是那些人口过亿的一级行政区。 现在我们介绍五个横跨两州的国家,并整理七大洲和这些国家的KML矢量数据分析分享给大家,如果你需要这些数据,请在文末查看领取方式。 世界上横跨两大洲的国家 地球被分为七个大洲分别是亚洲、欧洲、北美洲、南美洲、非洲、大洋洲和南极洲。 七大洲示意图 其中,南极洲是无人居住的大陆,而其他六个大洲则孕育了众多国家和

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

简单的Q-learning|小明的一维世界(3)

简单的Q-learning|小明的一维世界(1) 简单的Q-learning|小明的一维世界(2) 一维的加速度世界 这个世界,小明只能控制自己的加速度,并且只能对加速度进行如下三种操作:增加1、减少1、或者不变。所以行动空间为: { u 1 = − 1 , u 2 = 0 , u 3 = 1 } \{u_1=-1, u_2=0, u_3=1\} {u1​=−1,u2​=0,u3​=1}

简单的Q-learning|小明的一维世界(2)

上篇介绍了小明的一维世界模型 、Q-learning的状态空间、行动空间、奖励函数、Q-table、Q table更新公式、以及从Q值导出策略的公式等。最后给出最简单的一维位置世界的Q-learning例子,从给出其状态空间、行动空间、以及稠密与稀疏两种奖励函数的设置方式。下面将继续深入,GO! 一维的速度世界 这个世界,小明只能控制自己的速度,并且只能对速度进行如下三种操作:增加1、减

【Linux】萌新看过来!一篇文章带你走进Linux世界

🚀个人主页:奋斗的小羊 🚀所属专栏:Linux 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 前言💥1、初识Linux💥1.1 什么是操作系统?💥1.2 各种操作系统对比💥1.3 现代Linux应用💥1.4 Linux常用版本 💥2、Linux 和 Windows 目录结构对比💥2.1 文件系统组织方式💥2.2

Elasticsearch:无状态世界中的数据安全

作者:来自 Elastic Henning Andersen 在最近的博客文章中,我们宣布了支持 Elastic Cloud Serverless 产品的无状态架构。通过将持久性保证和复制卸载到对象存储(例如 Amazon S3),我们获得了许多优势和简化。 从历史上看,Elasticsearch 依靠本地磁盘持久性来确保数据安全并处理陈旧或孤立的节点。在本博客中,我们将讨论无状态的数据持

【AI大模型应用开发】2.1 Function Calling连接外部世界 - 入门与实战(1)

Function Calling是大模型连接外部世界的通道,目前出现的插件(Plugins )、OpenAI的Actions、各个大模型平台中出现的tools工具集,其实都是Function Calling的范畴。时下大火的OpenAI的GPTs,原理就是使用了Function Calling,例如联网检索、code interpreter。 本文带大家了解下Function calling,看

005:VTK世界坐标系中的相机和物体

VTK医学图像处理---世界坐标系中的相机和物体 左侧是成像结果                                                    右侧是世界坐标系中的相机与被观察物体 目录 VTK医学图像处理---世界坐标系中的相机和物体 简介 1 在三维空间中添加坐标系 2 世界坐标系中的相机 3 世界坐标系中vtkImageData的参数 总结:

深入RabbitMQ世界:探索3种队列、4种交换机、7大工作模式及常见概念

文章目录 文章导图RabbitMQ架构及相关概念四大核心概念名词解读 七大工作模式及四大交换机类型0、前置了解-默认交换机DirectExchange1、简单模式(Simple Queue)-默认DirectExchange2、 工作队列模式(Work Queues)-默认DirectExchange3、发布/订阅模式(Publish/Subscribe)-FanoutExchange4、路

攻防世界 unseping

unseping 攻防世界web新手练习 -unseping_攻防世界web新手题unseping-CSDN博客 这道题对我来说还是有点难,什么oct绕过命令执行第一次遇到捏,所以基本是跟着别人的wp写的,一点点记录吧 先对源码进行分析 <?phphighlight_file(__FILE__);//定义了一个ease类class ease{private $method;privat