集合解题报告

集合

对于集合(S)，记(min S)表示(S)中最小的元素，并定义(F(S)=A^{min S})，设([n])表示集合({1,2,dots,n})

请求出(E(F(S)|Ssubseteq[n],|S|=k))，对(M =998244353)取模

(1le kle n<M,1le kle 10^7,1le A <M,1le Tle 5)

考场上并不会推...

考虑钦定最小值，那么答案为

[frac{sum_{i=1}^nA^iinom{n-i}{k-1}}{inom{n}{k}} ]

显然这个复杂度需要搞到(O(k))

设

[f(k)=sum_{i=1}^nA^iinom{n-i}{k-1} ]

如果(A_i=1)，那么答案为(1)

否则

[frac{A^i-1}{A-1}=sum_{j=0}^{i-1}A^j ]

那么

[egin{aligned} f(k)&=sum_{i=1}^nA^iinom{n-i}{k-1}\ &=sum_{i=1}^ninom{n-i}{k-1}((sum_{j=1}^{n-1}A^j)(A-1)+1)\ &=(A-1)sum_{j=0}^{n-1}A^jsum_{i=j+1}^ninom{n-i}{k-1}+sum_{i=1}^ninom{n-i}{k-1}\ &=(A-1)sum_{j=0}^{n-1}A^jinom{n-j}{k}+inom{n}{k}\ &=(A-1)sum_{i=1}^{n-1}A_jinom{n-j}{k}+Ainom{n}{k}\ &=(A-1)f(k+1)+Ainom{n}{k}\ &=sum_{i=k}^nA(A-1)^{i-k}inom{n}{i}\ &=A(A-1)^{-k}sum_{i=k}^n(A-1)^iinom{n}{i}\ &=A(A-1)^{-k}(A^n-sum_{i=0}^{k-1}(A-1)^iinom{n}{i}) end{aligned} ]

最后两步用了补集转换和二项式定理把复杂度搞成(O(k))，中间有一步用了求组合数一列的东西。

Code:

#include <cstdio>
#include <cctype>
const int N=1e7+1;
const int mod=998244353;
template <class T>
void read(T &x)
{
	x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
#define mul(a,b) (1ll*(a)*(b)%mod)
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
int fac[N],inv[N];
int main()
{
	freopen("set.in","r",stdin);
	freopen("set.out","w",stdout);
	fac[0]=1;for(int i=1;i<N;i++) fac[i]=mul(fac[i-1],i);
	inv[N-1]=qp(fac[N-1],mod-2);
	for(int i=N-2;~i;i--) inv[i]=mul(inv[i+1],i+1);
	int T;read(T);
	while(T--)
	{
		int n,k,a,ans=0;
		read(n),read(k),read(a);
		if(a==1) {puts("1");continue;}
		for(int f1=1,f2=1,i=0;i<k;i++)
		{
			ans=add(ans,mul(f1,mul(f2,inv[i])));
			f1=mul(f1,a-1);
			f2=mul(f2,n-i);
		}
		ans=add(qp(a,n),mod-ans);
		int d=inv[k];
		for(int i=n;i>n-k;i--) d=mul(d,i);
		ans=mul(ans,qp(d,mod-2));
		printf("%lld
",mul(a,mul(qp(qp(a-1,k),mod-2),ans)));
	}
	return 0;
}

2019.3.21

集合 解题报告

集合

集合解题报告