HS
菜单
HS的博客
51Nod1778 小Q的集合

题目链接

51Nod

题目描述

小Q有一个集合 $S$ ,它的元素个数 $|S|=n$ 。
对于 $S$ 的任意一个子集合 $T$ ,定义 $f(T)=|T|^k$ ,定义 $T$ 关于 $S$ 的补集为 $S-T$ 。
小Q想知道,如果他等概率地选择一个 $S$ 的子集 $T$ ,那么 $f(T)-f(S-T)$ 的方差是多少。
由于这个方差值可能很大,不妨设其为 $v$ ,你只需要给出 $(v\cdot 2^n)\bmod m$ 的值即可。

输入格式

第一行一个正整数$n$,满足$k \leq n \leq 10^{10^6}$。
第二行一个正整数$k$,满足$1 \leq k \leq 10^6$。
第三行一个正整数$m$,其中m是质数,满足$2 \leq m \leq 10^6$。

输出格式

共一行,答案乘$2^n$模$m$的值。

输入输出样例

输入 #1

10
1
23333

输出 #1

10240

说明/提示

分析

根据经典柿子,有平方的期望等于平方的期望减去期望的平方。

容易发现期望为$0$。

那么我们只需要计算平方的期望即可。

由于乘上了$2^n$,其实就是要求这个柿子

$$
\sum_{i=0}^n\binom{n}{i}(i^k-(n-i)^k)^2
$$

考虑分开枚举$i$。

$$
\sum_{i=0}^{\lfloor\frac{n}{m}\rfloor}\sum_{j=0}^{n\%m}\binom{n}{i* m+j}((i* m+j)^k-(n-(i* m+j))^k)^2
$$

组合数之后的带$m$的项在模$m$的意义下没有用。

$$
\sum_{i=0}^{\lfloor\frac{n}{m}\rfloor}\sum_{j=0}^{n\%m}\binom{n}{i*m+j}(j^k-(n-j)^k)^2
$$

发现只有组合数带$i$很难看,用$Lucas$定理拆开。

$$
\sum_{i=0}^{\lfloor\frac{n}{m}\rfloor}\binom{\lfloor\frac{n}{m}\rfloor}{i}\sum_{j=0}^{n\%m}\binom{n\%m}{j}(j^k-(n-j)^k)^2
$$

发现左右两项独立了,也就是说,我们只要分别求出$\sum_{i=0}^{\lfloor\frac{n}{m}\rfloor}\binom{\lfloor\frac{n}{m}\rfloor}{i}​$和$\sum_{j=0}^{n\%m}\binom{n\%m}{j}(j^k-(n-j)^k)^2​$再相乘就行了。

把左边的柿子化简一下

$$
\sum_{i=0}^{\lfloor\frac{n}{m}\rfloor}\binom{\lfloor\frac{n}{m}\rfloor}{i} =2^{\lfloor\frac{n}{m}\rfloor}
$$

对于指数${\lfloor\frac{n}{m}\rfloor}$可以使用费马小定理模上$m-1$,复杂度就能够承受了。

对于右边的柿子,发现只有$n\%m+1$项,直接暴力即可。

一些对我而言的坑

平方不要漏掉。
预处理从$0$开始。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1000010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int n,ans,K,p,N,pw[maxn],jc[maxn],inv[maxn];
char str[maxn];
void Add(int &x,int y)
{
    x+=y;
    if(x>=p)
        x-=p;
}
int sub(int x,int y)
{
    x-=y;
    return x<0? x+p:x;
}
int mul(int x,int y)
{
    return 1ll*x*y%p;
}
long long fpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1)
            res=mul(res,x);
        x=mul(x,x);
        y>>=1;
    }
    return res;
}
long long C(int n,int m)
{
    return mul(jc[n],mul(inv[m],inv[n-m]));
}
int main()
{
    scanf("%s",str+1);
    read(K,p);
    int len=strlen(str+1);
    long long x=0;
    for(int i=1;i<=len;i++)
    {
        n=(1ll*n*10+str[i]-'0')%p;
        x=x*10+str[i]-'0';
        N=(1ll*N*10+x/p)%(p-1);
        x%=p;
    }
    jc[0]=1;
    for(int i=0;i<=n;i++)
        pw[i]=fpow(i,K);
    for(int i=1;i<=n;i++)
        jc[i]=mul(jc[i-1],i);
    inv[n]=fpow(jc[n],p-2);
    for(int i=n-1;i>=0;i--)
        inv[i]=mul(inv[i+1],i+1);
    for(int i=0;i<=n;i++)
        Add(ans,mul(C(n,i),mul(sub(pw[i],pw[n-i]),sub(pw[i],pw[n-i]))));
    printf("%d\n",mul(fpow(2,N),ans));
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

51Nod1778 小Q的集合
Lucas定理
扫描二维码继续阅读
2020-02-11