专题总结（计数）

总结 计数 DP

Rabbit Numbering

给出$\{a_1,a_2,...,a_n\}$,求满足$1\leq x_i\leq a_i$且$x_i$互不相同的$(x_1,x_2,...,x_n)$的数量.

• $n\leq50$

排个序，可以$O(n)$统计答案，$ans=\prod_{i=1}^n(a_i-i+1)$。

Rainbow Trees

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

• $n\leq500,k\leq10^9$

$dfs$,$bfs$各一遍，统计答案时除去已统计边的颜色：

• 同一父亲已统计过的儿子的父边。
• 父亲的父亲的所有儿子的父边。
• 父亲的父亲的父边。

const int N=1e3+100,mod=1e9+9;
struct Edge{int to,nxt;}e[N<<1];
int n,k,h[N],cnt,son[N],f[N],num[N],Q[N],hd,tl,d[N],ysn;
ll ans=1;
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il void dfs1(re int u,re int fa)
{
  f[u]=fa;d[u]=d[fa]+1;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      son[u]++;
      dfs1(v,u);
    }
}
il void bfs()
{
  Q[++tl]=1;
  while(hd<tl)
    {
      re int u=Q[++hd],pzy;
      for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==f[u]) continue;
      ans=ans*(k-num[d[v]]-son[f[u]]-(f[f[u]]>0))%mod;num[d[v]]++;
      Q[++tl]=v;pzy=d[v];
    }
      num[pzy]=0;
    }
}
int main()
{
  re int T;scanf("%d",&T);
  while((++ysn)<=T)
    {
      memset(h,-1,sizeof(h));cnt=0;memset(son,0,sizeof(son));memset(num,0,sizeof(num));hd=tl=0;ans=1;
      scanf("%d%d",&n,&k);
      fp(i,1,n-1)
    {
      re int u,v;scanf("%d%d",&u,&v);
      add(u,v);add(v,u);
    }
      dfs1(1,0);
      bfs();
      printf("Case #%d: %lld\n",ysn,ans);
    }
  return 0;
}

MatrixPower

难度极大，而且没题解。

Colorful Sequences

⻓度为$n$元素在$\{1,2,...,k\}$中的数列是好的,当且仅当存在⻓度为$k$的无重子串。给出数列$\{a_1,a_2,...,a_m\}$,求所有好的数列中$a$的出现次数之和。

• $m\leq n\leq 25000,k\leq400$

有时间再做。

[ZJOI2016]小星星

已完成。

Derangement

题解

ConvexScore