频道栏目
首页 > 考试 > 其他 > 正文

Crash的文明世界-第二类斯特林数+树形DP

2018-06-23 10:46:42      个评论    来源:Maxwei_wzj的OI世界  
收藏   我要投稿

测试地址:Crash的文明世界
做法:本题需要用到第二类斯特林数+树形DP。
直接算式子的话,没办法拆开用其它方式算贡献,所以肯定要把这个式子拆开。
根据第二类斯特林数的性质,有:
nk=i=0kS(k,i)i!Cni" role="presentation">nk=i=0kS(k,i)?i!?Cni
其中S(k,i)" role="presentation">S(k,i)为第二类斯特林数。
于是我们就能把题目中要求的式子拆成:
S(i)=j=1np=0kS(k,p)p!Cdist(i,j)p" role="presentation">S(i)=j=1np=0kS(k,p)?p!?Cdist(i,j)p
=p=0kS(k,p)p!j=1nCdist(i,j)p" role="presentation">=p=0kS(k,p)?p!?j=1nCdist(i,j)p
于是我们只要求出f(i,p)=j=1nCdist(i,j)p" role="presentation">f(i,p)=j=1nCdist(i,j)p,我们就能O(nk)" role="presentation">O(nk)求出所有的S(i)" role="presentation">S(i)了。
我们发现组合数有一个优美的性质:Cnm=Cn1m1+Cn1m" role="presentation">Cnm=Cn?1m?1+Cn?1m。因为儿子子树中所有的点与当前点的距离,恰好比它们到该儿子的距离多1" role="presentation">1,所以我们可以树形DP求down(i,p)" role="presentation">down(i,p),表示在点i" role="presentation">i子树中的点j" role="presentation">jf(i,p)" role="presentation">f(i,p)的总贡献,这样就可以直接用儿子的信息算出当前点的信息了。而对于其它的点,我们也利用组合数的性质,自上而下求一个up(i,p)" role="presentation">up(i,p)即可。状态转移方程比较复杂,详见代码。
于是,树形DP的复杂度是O(nk)" role="presentation">O(nk)的,而预处理斯特林数是O(k2)" role="presentation">O(k2)的,所以能通过此题。
用long long常数大一些,会过不了,改成用int即可。
以下是本人代码:

#include 
using namespace std;
const int mod=10007;
int n,k,first[50010]={0},tot=0;
int S[160][160]={0},fac[160],down[50010][160]={0},up[50010][160]={0};
struct edge
{
 int v,next;
}e[100010];

void insert(int a,int b)
{
 e[++tot].v=b;
 e[tot].next=first[a];
 first[a]=tot;
}

void init()
{
 int i,now,l,A,B,Q,tmp;

 scanf("%d%d%d",&n,&k,&l);
 scanf("%d%d%d%d",&now,&A,&B,&Q);
 for(i=1;i1)
 {
  for(int i=1;i<=k;i++)
  {
up[v][i]=(up[fa][i]+up[fa][i-1])%mod;
up[v][i]=((up[v][i]+down[fa][i]-down[v][i]-down[v][i-1])%mod+mod)%mod;
up[v][i]=((up[v][i]+down[fa][i-1]-down[v][i-1])%mod+mod)%mod;
if (i>1) up[v][i]=(up[v][i]-down[v][i-2]+mod)%mod;
else up[v][i]=(up[v][i]-1+mod)%mod;
  }
 }
 for(int i=first[v];i;i=e[i].next)
  if (e[i].v!=fa) calc_up(e[i].v,v);
}

void solve()
{
 for(int i=1;i<=n;i++)
 {
  int ans=0;
  for(int j=1;j<=k;j++)
ans=(ans+S[k][j]*fac[j]%mod*(down[i][j]+up[i][j]))%mod;
  printf("%d\n",ans);
 }
}

int main()
{
 init();
 calc_down(1,0);
 calc_up(1,0);
 solve();

 return 0;
}
上一篇:求几个韩信点兵数
下一篇:求1-1/2+2/3-3/5+5/8.。。。。。前20项的和,保留6位小数
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站