[51Nod 1778] 小Q的集合

Description

小Q有一個集合 S ，它的元素個數 |S|=n | S | = n 。

對于 S 的任意一個子集合 T ，定義 f(T)=|T|k f ( T ) = | T | k ，定義 T 關于 S 的補集為 S−T 。

小Q想知道，如果他等機率地選擇一個 S 的子集 T ，那麼 f(T)−f(S−T) f ( T ) − f ( S − T ) 的方差是多少。

由于這個方內插補點可能很大，不妨設其為 v ，你隻需要給出 (v⋅2n)modm ( v ⋅ 2 n ) mod m 的值即可。

n<=101000000,m,k<=1e6 n <= 10 1000000 , m , k <= 1 e 6 且m為質數

Solution

容易發現平均值是0

那麼式子就是

∑i=0nCin(ik−(n−i)k) ∑ i = 0 n C n i ( i k − ( n − i ) k )

按模m分組

=∑d=0⌊nm⌋∑i=0m−1Cdm+in((i+d∗m)k−(d∗m+n mod m−i)k) = ∑ d = 0 ⌊ n m ⌋ ∑ i = 0 m − 1 C n d m + i ( ( i + d ∗ m ) k − ( d ∗ m + n   m o d   m − i ) k )

模意義下d可以直接去掉

最後多出來的先不管他

根據盧卡斯定理，有

=∑d=0⌊nm⌋Cd⌊nm⌋∑i=0m−1Cin mod m(ik−(n mod m−i)k) = ∑ d = 0 ⌊ n m ⌋ C ⌊ n m ⌋ d ∑ i = 0 m − 1 C n   m o d   m i ( i k − ( n   m o d   m − i ) k )

此時我們發現i>n mod m的部分是沒用的，交換主體之後左邊可以直接表示成2的次幂

=2⌊nm⌋∑i=0n mod m(ik−(n mod m−i)k) = 2 ⌊ n m ⌋ ∑ i = 0 n   m o d   m ( i k − ( n   m o d   m − i ) k )

有費馬小定理，質數對m-1取模

=2⌊nm⌋ mod (m−1)∑i=0n mod m(ik−(n mod m−i)k) = 2 ⌊ n m ⌋   m o d   ( m − 1 ) ∑ i = 0 n   m o d   m ( i k − ( n   m o d   m − i ) k )

這就可以直接計算了

複雜度 O(NlogN) O ( N log ⁡ N )

利用線篩預處理次幂可以優化到O(N)

我懶惰了。。

Code

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 1000005
using namespace std;
LL n,n1,k,m,js[N],ny[N],s1[N];
char ch[N];
LL ksm(LL k,LL n)
{
    LL s=;
    for(;n;k=k*k%m,n>>=) if(n&) s=s*k%m;
    return s;
}
LL C(LL n,LL p)
{
    if(n<p) return ;
    return js[n]*ny[p]%m*ny[n-p]%m;
}
LL sqr(LL x)
{
    x%=m;
    return x*x%m;
}
int main()
{
    scanf("%s",ch+);
    cin>>k>>m;
    int le=strlen(ch+);
    LL x=;
    fo(i,,le) 
    {
        n=(n*(LL)+ch[i]-'0')%m;
        x=x*(LL)+ch[i]-'0';
        n1=(n1*10+x/m)%(m-);
        x=x%m;
    }
    LL ans=;
    js[]=;
    fo(i,,n) s1[i]=ksm(i,k);
    fo(i,,m) js[i]=js[i-]*(LL)i%m;
    ny[m-]=ksm(js[m-],m-);
    fod(i,m-,) ny[i]=ny[i+]*(LL)(i+)%m;
    fo(i,,n) 
    {
        (ans+=C(n,i)*sqr(s1[i]-s1[n-i]+m))%=m;
    }
    ans=ans*ksm(,n1)%m;
    printf("%lld\n",ans);
}