JZOJ4390. 【GDOI2016模拟3.16】图计数

题解

转化一下题意，
就是有n个物品，分别为1，2，3，…，n，
问放满一个容量为n的背包的方案数。

这是一个无限背包，
一个很经典的做法，
可以对这n个物品进行分类，重量<n−−√$<\sqrt{n}$的为一组，大于的为一组，
很显然，前面n−−√$\sqrt{n}$就是普通的无限背包，
而剩下的物品，
可以知道它的个数不会超过n−−√$\sqrt{n}$个，
所以，两个部分的复杂度都是O(nn−−√$\sqrt{n}$）

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <time.h>
#define ll long long
#define N 200003
#define M 103
using namespace std;
const int mo=999999599;
const int m_=999999598;
int n,m,f[2][N],nn,g[N],p,ans;

ll ksm(ll x,int y)
{
    ll s=1;
    for(;y;y>>=1,x=x*x%mo)
        if(y&1)s=s*x%mo;
    return s;
}

int main()
{
    scanf("%d%d",&n,&m);
    nn=sqrt(n)+1;g[0]=1;

    for(int i=1;i<=nn;i++)
        for(int j=0;j+i<=n;j++)
            g[i+j]=(g[i+j]+g[j])%m_;

    f[p=0][0]=1;ans=g[n];
    for(int i=1;i<=nn;i++)
    {
        p=p^1;memset(f[p],0,sizeof(f[p]));
        for(int j=0;j<=n;j++)
        {
            if(j>=i)f[p][j]=(f[p][j]+f[p][j-i])%m_;
            if(j>nn)f[p][j]=(f[p][j]+f[p^1][j-nn-1])%m_;
            ans=(ans+((ll)g[n-j]*f[p][j])%m_)%m_;
        }
    }

    printf("%lld",ksm(m,ans));

    return 0;
}