这句话感觉都能成定理了:
xor问题逐位考虑……
这道题就是这样,然后和bzoj3143和相似
但这道题多了自环,于是我们设f[i]表示当前位由i走到n的后为1的数学期望
显然f[n]=0,可得f[i]=sigma((1/d[i])*f[j])(如果边权这位为0)+sigma((1/d[i])*(1-f[j]))(边权这位为1)
然后高斯消元即可
type node=record
po,len,next:longint;
end; var w:array[..] of node;
b,d,p:array[..] of longint;
a:array[..,..] of extended;
n,m,x,y,z,len,t,i,j,k:longint;
c,ans:extended; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure swap(var a,b:extended);
var c:extended;
begin
c:=a;
a:=b;
b:=c;
end; procedure add(x,y,z:longint);
begin
inc(len);
w[len].po:=y;
w[len].len:=z;
w[len].next:=p[x];
p[x]:=len;
end; procedure work;
var i,j,k,p:longint;
begin
for i:= to n- do
begin
p:=i;
for k:=i+ to n- do
if abs(a[k,i])>abs(a[p,i]) then p:=k;
if p<>i then
begin
for j:=i to n+ do
swap(a[p,j],a[i,j]);
end;
for k:=i+ to n- do
if abs(a[k,i])> then
begin
for j:=n+ downto i do
a[k,j]:=a[k,j]-a[i,j]*a[k,i]/a[i,i];
end;
end;
a[n,n+]:=;
for i:=n- downto do
begin
for j:=i+ to n- do
a[i,n+]:=a[i,n+]-a[j,n+]*a[i,j];
a[i,n+]:=a[i,n+]/a[i,i];
end;
end; begin
readln(n,m);
for i:= to m do
begin
readln(x,y,z);
if z<> then t:=max(t,trunc(ln(z)/ln()));
inc(d[x]);
inc(d[y]);
if x=y then dec(d[x])
else add(y,x,z);
add(x,y,z);
end;
for i:= to t do
begin
fillchar(a,sizeof(a),);
for j:= to n do
a[j,j]:=;
for k:= to n do
begin
j:=p[k];
while j<> do
begin
y:=w[j].po;
if w[j].len and ( shl i)= then a[k,y]:=a[k,y]-/d[k]
else begin
a[k,y]:=a[k,y]+/d[k];
a[k,n+]:=a[k,n+]+/d[k];
end;
j:=w[j].next;
end;
end;
work;
ans:=ans+ shl i*a[,n+];
end;
writeln(ans::);
end.
bzoj2337的更多相关文章
-
【BZOJ2337】Xor和路径(高斯消元)
[BZOJ2337]Xor和路径(高斯消元) 题面 BZOJ 题解 我应该多学点套路: 对于xor之类的位运算,要想到每一位拆开算贡献 所以,对于每一位拆开来看 好了,既然是按位来算 我们就只需要计算 ...
-
[BZOJ2337][HNOI2011]XOR和路径(概率+高斯消元)
直接不容易算,考虑拆成位处理. 设f[i]表示i到n的期望路径异或和(仅考虑某一位),则$f[y]=\sum\limits_{exist\ x1\to y=0}\frac{f[x1]}{d[x1]}+ ...
-
【BZOJ2337】[HNOI2011]XOR和路径 期望DP+高斯消元
[BZOJ2337][HNOI2011]XOR和路径 Description 题解:异或的期望不好搞?我们考虑按位拆分一下. 我们设f[i]表示到达i后,还要走过的路径在当前位上的异或值得期望是多少( ...
-
BZOJ2337: [HNOI2011]XOR和路径
题解: 异或操作是每一位独立的,所以我们可以考虑每一位分开做. 假设当前正在处理第k位 那令f[i]表示从i到n 为1的概率.因为不是有向无环图(绿豆蛙的归宿),所以我们要用到高斯消元. 若有边i-& ...
-
Bzoj2337:[HNOI2011]XOR和路径
题面 bzoj Sol 设\(f[i]\)表示\(i到n\)的路径权值某一位为\(1\)的期望 枚举每一位,高斯消元即可 不要问我为什么是\(i\ - \ n\)而不可以是\(1\ - \ i\) # ...
-
BZOJ2337: [HNOI2011]XOR和路径(期望 高斯消元)
题意 题目链接 Sol 期望的线性性对xor运算是不成立的,但是我们可以每位分开算 设\(f[i]\)表示从\(i\)到\(n\)边权为1的概率,统计答案的时候乘一下权值 转移方程为 \[f[i] = ...
-
bzoj千题计划191:bzoj2337: [HNOI2011]XOR和路径
http://www.lydsy.com/JudgeOnline/problem.php?id=2337 概率不能异或 但根据期望的线性,可以计算出每一位为1的概率,再累积他们的期望 枚举每一位i,现 ...
-
bzoj2337 XOR和路径
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2337 首先:因为是异或和,所以可以考虑每一位考虑. 就在每一位上求一下该位是1的概率,乘以1 ...
-
BZOJ2337:[HNOI2011]XOR和路径(高斯消元)
Description 给定一个无向连通图,其节点编号为 1 到 N,其边的权值为非负整数.试求出一条从 1 号节点到 N 号节点的路径,使得该路径上经过的边的权值的“XOR 和”最大.该路径可以重复 ...
随机推荐
-
sublime自动生成头部注释
1.在tool->new snippet-创建一个新的snippet sublime text2 用snippet 创建文件头部信息 Snippets are smart templates t ...
-
解决ora-01652无法通过128(在temp表空间中)扩展temp段的过程
解决ora-01652无法通过128(在temp表空间中)扩展temp段的过程 昨天开发人员跟我说,执行一个sql语句后,大约花了10分钟,好不容易有一个结果,但是报了一个ora-01652错误,查阅 ...
-
.net在当前日期的基础上加一天
比如今天是:2015-11-10 18:57:01,在这个基础上加一天,那么就是2015-11-11 18:57:01,代码如下: DateTime now_dt = DateTime.Now; ). ...
-
zookeeper初识之原理
ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,它包含一个简单的原语集,分布式应用程序可以基于它实现同步服务,配置维护和命名服务等. Zookeeper是hadoop的一个子项目 ...
-
FileInputStream类
FileInputStream和FileOutPutStream类都是用来操作磁盘文件的.如果用户对文件读取需求比较简单,则可以使用FileInputStream类,该类继承InputStream类 ...
-
for 与 foreach 性能
For 与Foreach 性能 差别在不同的场景下会有不同的差异. 对于不同的目标 , 如 T[] 与 IEnumerable<T> 两个的性能就感觉出来了,对于T[] 都快. ...
-
编译:一个 C 程序的艺术之旅(转载)
C 程序为什么要编译才能执行?一个 C 程序在变成可执行文件的过程中,为什么要经过预处理.编译.汇编.链接这四道工序?让我们从这段简单的 C 程序开始. 为什么要编译 这并不是一个简单的问题.我们知道 ...
-
TOGAF架构开发方法(ADM)之迁移规划阶段
TOGAF架构开发方法(ADM)之迁移规划阶段 1.8 迁移规划(Migration Planning) 企业架构开发方法各阶段——迁移规划 1.8.1 目标 本阶段的目标是: 确保实施和迁移规划与企 ...
-
【Valse首发】CNN的近期进展与实用技巧(上)
作者:程程链接:https://zhuanlan.zhihu.com/p/21432547来源:知乎著作权归作者所有.商业转载请联系作者获得授权,非商业转载请注明出处. 深度学习大讲堂致力于推送人工智 ...
-
项目架构开发:数据访问层之UnitOfWork
接上文 项目架构开发:数据访问层之IQuery 本章我们继续IUnitOfWork的开发,从之前的IRepository接口中就可以看出,我们并没有处理单元事务, 数据CUD每次都是立即执行的,这样有 ...