标签归档:生成函数

[hdu6397][多校第八场]Character Encoding

Link

求$[x^k] (x^0+x^1+x^2+…+x^{n-1})^m$

Solution

生成函数

$\begin{aligned}
&(x^0+x^1+x^2+…+x^{n-1})^m\
=&(x^n-1)^m(x-1)^{-m}\
\end{aligned}$
设$k=\lambda_1n+\lambda_2$

[x^{\lambda_1n}] (x^n-1)^m=\binom m{\lambda_1}(-1)^{\lambda_1}\\
[x^{\lambda_2}] (x-1)^{-m}=\binom {-m}{\lambda_2}(-1)^{\lambda_2}\\
\binom {-m}{\lambda_2}=\frac{(-m)(-m-1)…(-m-\lambda_2+1)}{\lambda_2!}\\
\begin{aligned}&(-m)(-m-1)…(-m-\lambda_2+1)\\
=&(-1)^{\lambda_2}m(m+1)…(m+\lambda_2-1)\end{aligned}

因此

\binom {-m}{\lambda_2}=(-1)^{\lambda_2}\binom {m+\lambda_2-1}{\lambda_2}

然后就能算了。

void Work() {
    int n,m,k;fin>>n>>m>>k;
    int Ans=0;
    for(int lam1=0;lam1*n<=k;++lam1) {
        int lam2=k-lam1*n;
        Ans=Add(Ans,Mul(Mul(C(m,lam1),lam1&1?P-1:1),C(m+lam2-1,lam2)));
    }
    fout<<Ans<<'\n';

容斥原理

如果去掉变量$< n$的限制,那方案数就是

\binom {k+m-1}{m-1}

考虑容斥。
假设至少有$p$个变量$\ge n$,那么方案数为

\binom mp\binom {k-pn+m-1}{m-1}

意思是让超出的都减去$n$。
然后容斥就好了。