洛谷P1291 [SHOI2002]百事世界杯之旅——期望DP
2024-09-08 09:46:51
题目:https://www.luogu.org/problemnew/show/P1291
水水的经典期望DP;
输出有毒。(其实也很简单啦)
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,fz[],fm[],s1,s2,ans,w,w2;
//double f[35];
ll gcd(ll x,ll y){return x%y?gcd(y,x%y):y;}
ll getlen(ll x)
{
ll ret=;
while(x){ret++; x/=;}
return ret;
}
int main()
{
scanf("%lld",&n);
fz[n]=; fm[n]=;
for(ll i=n-;i>=;i--)
{
ll tfm=(n-i)*fm[i+];
ll tfz=(n-i)*fz[i+] + n*fm[i+];
ll k=gcd(tfz,tfm);
fz[i]=tfz/k; fm[i]=tfm/k;
}
// for(ll i=n-1;i>=0;i--)
// f[i]=f[i+1]+n/(n-i);
// printf("%lf",f[0]);
s1=fz[],s2=fm[];
if(s2==)
{
printf("%lld",s1); return ;
}
ans=s1/s2,s1%=s2;
w=getlen(s2);
if(ans)w2=getlen(ans);
if(!s1)
{
printf("%lld",ans); return ;
}
if(ans)
// while(w2--) printf(" ");//把 w2 减掉了!!!
for(int i=;i<=w2;i++) printf(" ");
printf("%lld\n",s1);
if(ans)printf("%lld",ans);
while(w--)printf("-"); printf("\n");
if(ans) while(w2--) printf(" ");
printf("%lld",s2);
return ;
}
最新文章
- jsp页面无法解析EL表达式
- mysql - 缺失范围和连续范围
- 异步编程 z
- 一个SharePoint定时器 (SPJobDefinition)
- 如何在Win10下设置图片的浏览方式为windows照片查看器
- 项目上线与LOG记录
- Spring IOC 三种注入方式
- C#打包制作安装程序过程全记录
- C#中的virtual &; override
- 补充:学会Twitter Bootstrap不再难
- Code generated using the T4 templates for Database First
- regsvr32 命令小集注册OCX控件,注册控件(包括十几个举例)
- [css]《css揭秘》学习(四)-一个元素实现内圆角边框
- Unity 3D Framework Designing(2)——使用中介者模式解耦ViewModel之间通信
- 【原创】大数据基础之Logstash(4)高可用
- ORACLE 11g 创建数据库时 Enterprise Manager配置失败的解决办法 无法打开ORACLE企业管理器(EM)的解决办法
- IKAnalyzer 添加扩展词库和自定义词
- python3 判断大小端的一种方法
- 序列化人人网框架下的DAO?也就是在Spring下序列化DAO的问题(spring+quartz集群下)
- Flask 使用富文本输入框