[关闭]
@ysner 2018-07-31T14:26:59.000000Z 字数 1292 阅读 1859

专题总结(计数)

总结 计数 DP


Rabbit Numbering

给出,求满足互不相同的的数量.

排个序,可以统计答案,

Rainbow Trees

给定个点的树,将树边染成种颜色,使得任意⻓度为的路径树边颜色不同,求方案数。

,各一遍,统计答案时除去已统计边的颜色:

  1. const int N=1e3+100,mod=1e9+9;
  2. struct Edge{int to,nxt;}e[N<<1];
  3. int n,k,h[N],cnt,son[N],f[N],num[N],Q[N],hd,tl,d[N],ysn;
  4. ll ans=1;
  5. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  6. il void dfs1(re int u,re int fa)
  7. {
  8. f[u]=fa;d[u]=d[fa]+1;
  9. for(re int i=h[u];i+1;i=e[i].nxt)
  10. {
  11. re int v=e[i].to;
  12. if(v==fa) continue;
  13. son[u]++;
  14. dfs1(v,u);
  15. }
  16. }
  17. il void bfs()
  18. {
  19. Q[++tl]=1;
  20. while(hd<tl)
  21. {
  22. re int u=Q[++hd],pzy;
  23. for(re int i=h[u];i+1;i=e[i].nxt)
  24. {
  25. re int v=e[i].to;
  26. if(v==f[u]) continue;
  27. ans=ans*(k-num[d[v]]-son[f[u]]-(f[f[u]]>0))%mod;num[d[v]]++;
  28. Q[++tl]=v;pzy=d[v];
  29. }
  30. num[pzy]=0;
  31. }
  32. }
  33. int main()
  34. {
  35. re int T;scanf("%d",&T);
  36. while((++ysn)<=T)
  37. {
  38. memset(h,-1,sizeof(h));cnt=0;memset(son,0,sizeof(son));memset(num,0,sizeof(num));hd=tl=0;ans=1;
  39. scanf("%d%d",&n,&k);
  40. fp(i,1,n-1)
  41. {
  42. re int u,v;scanf("%d%d",&u,&v);
  43. add(u,v);add(v,u);
  44. }
  45. dfs1(1,0);
  46. bfs();
  47. printf("Case #%d: %lld\n",ysn,ans);
  48. }
  49. return 0;
  50. }

MatrixPower

难度极大,而且没题解。

Colorful Sequences

⻓度为元素在中的数列是好的,当且仅当存在⻓度为的无重子串。给出数列,求所有好的数列中的出现次数之和。

有时间再做。

[ZJOI2016]小星星

已完成。

Derangement

题解

ConvexScore

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注