- 有(n)个球和(D)种颜色。
- 问你有多少种染色方案，使得能选出至少(m)对同色的球。
- (Dle10^5,mle nle10^9)
基础转化
令(cnt_x)表示颜色为(x)的小球个数，那么题意就相当于是：
对于整除有一个基本的转化(lfloorfrac x2 floor=frac{x-x\%2}2)，因此就有：
由于(sum_{i=1}^Dcnt_x=n)，所以最终得到：
也就是有至多(n-2m)种颜色出现奇数次。
二项式反演
设(f_i)表示有至少(i)种颜色出现奇数次，(g_i)表示有恰好(i)种颜色出现奇数次，显然最终答案应该是(sum_{i=0}^{n-2m}g_i)。
(f_i)和(g_i)之间有一个显然的关系式：
根据二项式反演的式子得到：
考虑转化一下这个式子，首先拆开组合数并移项：
构造两个多项式(A(x)=sum_{i=0}^{D}(f_i imes i!)x^i,B(x)=sum_{i=0}^Dfrac{(-1)^{D-i}}{(D-i)!}x^i)（注意(B(x))的系数经过了翻转，以形成一个卷积的形式）
则(A(x)*B(x))的(D+i)次项系数就是(g_i imes i!)。
那么现在的问题就变成了如何求(f_i)。
指数型生成函数
显然，对于一个已知的(cnt)数组，生成它的方案数是(frac{n!}{prod_{i=1}^D(cnt_i!)})。
因此我们构造指数型生成函数(sum_{i=0}^{+infty}frac{x^i}{i!}=e^x)。
而现在我们要有至少(i)种颜色出现奇数次，那么我们就要强制选(i)种颜色出来让它出现奇数次。
考虑这(i)种颜色的生成函数实际上就是(frac{e^x-e^{-x}}2)（(e^x)与(e^{-x})相减刚好能消去偶次项）。
那么得到计算(f_i)的朴素式子就应该是：
对于其中((frac{e^x-e^{-x}}2)^i)一项，我们提出总分母(2^i)，然后暴力二项式定理展开得到：
简单地化简一下：
现在含(e)的项就只有(e^{(D-2(i-j))x})这个简单的式子了。
考虑(e^{ax}=sum_{i=0}^{+infty}frac{a^ix^i}{i!})，所以([x^n]e^{ax}=frac{a^n}{n!})。
即，对于原式可以进一步得到：
整理一下，把它表示成卷积的形式就有：
构造两个多项式(A(x)=sum_{i=0}^{D}frac{(-1)^i imes(D-2i)^n}{i!}x^i,B(x)=sum_{i=0}^Dfrac{x^i}{i!})。
显然(f_i=frac{D!}{(D-i)! imes 2^i} imes [x^i](A(x)*B(x)))。
求出(f_i)之后代回到前面的式子中，再做一次(NTT)求出(g_i)，这道题就做完了。
代码：(O(Dlogn))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define SZ 100000
#define X 998244353
#define I2 499122177
using namespace std;
int n,m,D,Fac[SZ+5],IFac[SZ+5],f[SZ+5],A[SZ<<2],B[SZ<<2];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
namespace Poly//多项式
{
#define PR 3
int P,L,R[SZ<<2];I void NTT(int* s,CI op)//NTT
{
RI i,j,k,x,y,U,S;for(i=0;i^P;++i) i<R[i]&&(x=s[i],s[i]=s[R[i]],s[R[i]]=x);
for(i=1;i^P;i<<=1) for(U=QP(QP(PR,op),(X-1)/(i<<1)),j=0;j^P;j+=i<<1) for(S=1,k=0;
k^i;++k,S=1LL*S*U%X) s[j+k]=((x=s[j+k])+(y=1LL*S*s[i+j+k]%X))%X,s[i+j+k]=(x-y+X)%X;
}
I void Mul(CI n,int* A,int* B)//卷积
{
RI i;P=1,L=0;W(P<=(n<<1)) P<<=1,++L;for(i=0;i^P;++i) R[i]=((R[i>>1]>>1)|((i&1)<<L-1));
for(NTT(A,1),NTT(B,1),i=0;i^P;++i) A[i]=1LL*A[i]*B[i]%X;
RI t=QP(P,X-2);for(NTT(A,X-2),i=0;i<=2*n;++i) A[i]=1LL*A[i]*t%X;
}
}
int main()
{
RI i;if(scanf("%d%d%d",&D,&n,&m),2*m>n) return puts("0"),0;//特判
if(2*m<=n-D) return printf("%d",QP(D,n)),0;//特判
for(Fac[0]=i=1;i<=D;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘
for(IFac[D]=QP(Fac[D],X-2),i=D;i;--i) IFac[i-1]=1LL*IFac[i]*i%X;//预处理阶乘逆元
for(i=0;i<=D;++i) A[i]=1LL*(i&1?X-1:1)*QP((D-2*i+X)%X,n)%X*IFac[i]%X,B[i]=IFac[i];//第一遍卷积
for(Poly::Mul(D,A,B),i=0;i<=D;++i) f[i]=1LL*A[i]*Fac[D]%X*IFac[D-i]%X*QP(I2,i)%X;//求出f[i]
memset(A,0,sizeof(A)),memset(B,0,sizeof(B));//清空数组
for(i=0;i<=D;++i) A[i]=1LL*f[i]*Fac[i]%X,B[D-i]=1LL*(i&1?X-1:1)*IFac[i]%X;//第二遍卷积
RI t=0;for(Poly::Mul(D,A,B),i=0;i<=n-2*m;++i) t=(1LL*A[D+i]*IFac[i]+t)%X;//求出g[i]并统计答案
return printf("%d
",t),0;
}