jzoj4390 [GDOI2016模拟3.16]图计数 整数拆分

Description

---

Solution

---

脑抽地想到了burnside引理然后以为不可做。

可以转化为n类体积为[1,n]数量无限的物体装进容量为n的背包的方案数
考虑分类。对于≤n−−√$\le \sqrt{n}$的物品只有O(n−−√)$O(\sqrt{n})$种，对于≥n−−√$\ge \sqrt{n}$的物品只会选n−−√$\sqrt{n}$个
那么第一类跑完全背包，第二类考虑dp，f[i][j]=f[i][j−i]+f[i−1][j−n−−√]$f[i][j]=f[i][j-i]+f[i-1][j-\sqrt{n}]$，分别表示全部加一和加一个物品
然后合并一次背包就ok了

其实还可以用整数拆分的东西搞，比如五边形数这种我不会的GD黑科技

Code

---

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))

typedef long long LL;
const int MOD=999999599;
const int N=200005;

LL f1[N],f2[2][N];

LL ksm(LL x,LL dep) {
    LL ret=1;
    while (dep) {
        if (dep&1) ret=ret*x%MOD;
        x=x*x%MOD; dep/=2;
    }
    return ret;
}

int main(void) {
    int n,m; scanf("%d%d",&n,&m);
    int p=sqrt(n)+1,ans=0;
    f1[0]=1; f2[0][0]=1;
    rep(i,1,p) rep(j,0,n-i) f1[j+i]=(f1[j+i]+f1[j])%(MOD-1);
    rep(i,1,p) {
        fill(f2[i&1],0);
        rep(j,1,n) {
            if (j>p) f2[i&1][j]=(f2[i&1][j]+f2[(i-1)&1][j-p-1])%(MOD-1);
            if (j>=i) f2[i&1][j]=(f2[i&1][j]+f2[i&1][j-i])%(MOD-1);
            ans=(ans+f2[i&1][j]*f1[n-j]%(MOD-1))%(MOD-1);
        }
    } ans=(ans+f1[n])%(MOD-1);
    printf("%lld\n", ksm(m,ans));
    return 0;
}