BZOJ 3516 国王奇遇记加强版(乱推)

题意

求\(\sum_{k=1}^{n}k^mm^k (n\leq1e9,m\leq1e3)\)

思路

在<<具体数学>>中有一个方法用来求和，称为摄动法。

我们考虑用摄动法来求这个和式，看能不能得到比较好的复杂度。

首先令\(f(i)=\sum_{k=1}^nk^im^{k}\)。

然后开始表演

\[\begin{align*}
(m-1)f(i)&=\sum_{k=1}^nk^im^{k+1}-\sum_{k=1}^nk^im^k \\
&=\sum_{k=1}^{n+1}(k-1)^im^k-\sum_{k=1}^nk^im^k\\
&=n^im^{n+1}+\sum_{k=1}^nm^k\sum_{j=0}^{i-1}C_i^j(-1)^{i-j}k^j\\
&=n^im^{n+1}+\sum_{j=0}^{i-1}C_i^j(-1)^{i-j}\sum_{k=1}^nk^jm^k\\
&=n^im^{n+1}+\sum_{j=0}^{i-1}C_i^j(-1)^{i-j}f(j)
\end{align*}
\]

于是我们很神奇的得到了一个\(O(m^2)\)的递推式。

对于解决此题已经足够了。

另外对于这个和式有多项式插值法可以\(O(m)\)解决。

具体例题bzoj4126。

代码

# include<bits/stdc++.h>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-8

# define MOD 1000000007

# define INF 1e16

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(register int i=a; i<=n; ++i)

# define FDR(i,a,n) for(register int i=a; i>=n; --i)

# define bug puts("H");

# define lch p<<1,l,mid

# define rch p<<1|1,mid+1,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline char nc(){

    static char buf[1000000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

inline int Scan(){

    char ch=nc();int sum=0, f=1;

    if (ch=='-') f=-1, ch=nc();

    while(!(ch>='0'&&ch<='9'))ch=nc();

    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();

    return sum*f;

}

const int N=1005;

//Code begin....

LL C[N][N], ANS[N], INV, COM, P;

LL pow_mod(LL a, LL n, LL mod){

    LL ret=1, tmp=a%mod;

    while (n) {

        if (n&1) ret=ret*tmp%MOD;

        tmp=tmp*tmp%MOD;

        n>>=1;

    }

    return ret;

}

LL inv(LL a, LL mod){return pow_mod(a,mod-2,mod);}

void init(){

    FOR(i,0,1000) {

        C[i][0]=C[i][i]=1;

        FOR(j,1,i-1) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;

    }

}

int main ()

{

    int n, m;

    init();

    scanf("%d%d",&n,&m);

    if (m==1) {printf("%lld\n",(LL)n*(n+1)/2%MOD); return 0;}

    INV=inv(m-1,MOD); COM=pow_mod(m,n+1,MOD);

    ANS[0]=(COM-m)*INV%MOD; P=1;

    if (ANS[0]<0) ANS[0]+=MOD;

    FOR(i,1,m) {

        P=P*n%MOD;

        LL sum=P*COM%MOD;

        FOR(j,0,i-1) {

            if ((i+j)&1) sum-=C[i][j]*ANS[j]%MOD;

            else sum+=C[i][j]*ANS[j]%MOD;

        }

        sum%=MOD;

        if (sum<0) sum+=MOD;

        ANS[i]=sum*INV%MOD;

    }

    printf("%lld\n",ANS[m]);

    return 0;

}

巴特西

BZOJ 3516 国王奇遇记加强版(乱推)

题意

思路

代码

最新文章

热门文章