注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM581 & TCO2013 Round3A  

2013-06-19 14:51:35|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
=========================
581只是为了表明我做过。。。至于题目是啥我已经忘了
=========================
法法塔是彻底被这套题给虐了的说。。。
后面两题完全不会做啊!!!!(好吧第二题我没做出来充分说明我是,b,但是第三题我无论如何也不可能会做嘛!

A题其实我也想了蛮久。。。不过这个是因为我太,了。。

B题我是没做出来的。
n*n的网格图,在边界上有三个点,网格图内部有障碍,你要添加障碍使得这三个点不连通。
我可是往最小割去想了啊!!!!!
但是却无法处理一个点的情况。。。。
其实关键在于发现——网格图是个平面图啊。。割就可以用最小路来求
有与点在边界。。。
那么割只会有两种可能——
TCO2013 Round3A - hzaskywalker - Yavin(某沙茶的代码库)
绿色是边界,红色是割。
第一种情况,由于割不相交。。我们要对于每个点求出将这个点与其它割开的代价,将代价中较小的两个加起来就是答案。
对于第二种情况——割有交集——那么一定有个点作为交存在,枚举这个店,求出这个点与绿色的三个部分的最短路加起来,就是此时的最小割。
问题解决。

C题实在是太强大了。。oimaster的神题,不是作为在考场上可做的题而存在的。。
oimaster写了很详细的题解。。

题目:
Given positive integersn,m,s,t (1m,t109, nts1018, max(m?1000,1)nm) , calculcate the number of solutions to the inequality x1+x2+?+xms wherex1,x2,,xm are positive integers. In addition, x1,x2,,xn are not greater than t
 
题解:
以上。。
傻乎乎的法法塔照着公式自己推了一遍。。。但是法法塔还是太沙茶了。。照着推都推错了。。
核心是用差分来表示这个容斥的结果
以及组合数是个多项式
以及我们可以将组合数用stirling数变成多项式。。
以及多项式可以用stirling数求出差分
以及——神奇的stirling数的递推
反正我一个都不会。。。
推导可以参考傻逼法法塔抄的东东:

\documentclass{ctexart}
\usepackage{amsmath}

\begin{document}
$m,n,T,S$

$\varDelta^n f(x)=\sum_{i=0}^n\binom{n}{i}(-1)^{(n-i)}f(x+i)$

$ans=\sum_{x_1=1}^t\sum_{x_2=1}^t\ldots \sum_{x_n=1}^t\binom{S-x_1-x_2\ldots-x_n}{m-n}$

$ans=\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{s-k*t}{n}$

$f(x)=\binom{s-x*t}{n}$

$(-1)^n\varDelta^n f(x)=\sum_{i=0}^n\binom{n}{i}(-1)^if(x+i)$

$ans=(-1)^n\varDelta^n f(0)$

$f(x)=\sum_{i=0}^{m}a_ix^i=\sum_{i=0}^{m}b_i\binom{x}{i}$

$ans=b_n$
\\

$f(x)=\binom{s-xt}{m}=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}{m \brack i}(s-xt)^i \\
=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}{m \brack i}\sum_{j=0}^i(-1)^j s^{i-j} t^j x^j\\
=\frac{1}{m!}\sum_{j=0}^{m} x^j \sum_{i=j}^{m}(-1)^{m-i+j}\binom{i}{j}{m \brack i}s^{i-j} t^j$

Hence we get

$a_i=\frac{1}{m!}\sum_{j=i}^{m} (-1)^{m-j+i} \binom{j}{i} {m \brack j} t^i s^{j-i}$

To get $b_i$

$f(x)=\sum_{i=0}^m a_ix^i$

$f(x)=\sum_{i=0}^m a_i \sum_{j=0}^i{i \brace j} \binom{x}{j} j!$

$f(x)=\sum_{j=0}^m j! \sum_{i=j}^m a_i {i \brace j} \binom{x}{j}$

$b_n=\sum_{i=n}^m a_i {i \brace n} n!$ \\

$b_n=\sum_{i=n}^m {i\brace n} \frac{n!}{m!}\sum_{j=i}^{m} (-1)^{m-i+j} \binom{j}{i} {m \brack j} t^i s^{j-i}$

$b_n=\frac{n!}{m!} \sum_{i=n}^m \sum_{j=i}^{m} (-1)^{m-i+j} {i\brace n} \binom{j}{i} {m \brack j} t^i s^{j-i}$

the second kind of stiring number:\\ $g(a,b)=b*g(a-1,b)+(a-1)*g(a-2,b-1)$

the first kind of stiring number:\\ $h(a,b)=a*h(a-1,b)+(a-1)*g(a-2,b-1)$

$ m-n\le 1000 $

\end{document}



 
  评论这张
 
阅读(492)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017