ACM模版

描述

题解

我想，这个出题人一定是一个很淘气的人……这时限和被模数（姑且这么叫）真的很有趣。

这个题我不是特别会做，找了大牛的题解看了看，感觉十分详细，分享给大家，我就不多说什么了……我要去看母函数了。

mrazer’s blog，该大佬十分幽默，但是也很细心，从他的博客中添加的各种小动态表情（其实也不小了）就可以看出来，像我这么懒得人，根本想不起来搞这些让人愉快的东西……我要向大佬学习~~~当然，最主要还是大佬无懈可击的思路！！！

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXM = 320;
const int MOD = 23333333;

int n, m;
int tmp[MAXN];
int f[2][MAXN];
int g[MAXM][MAXN];
ll f1[MAXN], g1[MAXN];

int main()
{
    scanf("%d", &n);

    f[0][0] = g[0][0] = 1;
    m = (int)ceil(sqrt((double)n));

    int now = 0, pre = 1;
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            tmp[j] = 0;
        }
        int cnt = -1;
        swap(now, pre);
        for (int j = 0; j <= n; ++j)
        {
            ++cnt;
            if (cnt >= i)
            {
                cnt = 0;
            }
            tmp[cnt] += f[pre][j];
            tmp[cnt] %= MOD;
            f[now][j] = tmp[cnt];
            if (j >= i * i)
            {
                tmp[cnt] = (tmp[cnt] - f[pre][j - i * i] + MOD) % MOD;
            }
        }
    }

    for (int i = 0; i <= m; ++i)
    {
        for (int j = 0; j <= n; ++j)
        {
            if (i && i + j <= n)
            {
                g[i][i + j] += g[i][j];
                g[i][i + j] %= MOD;
            }
            if (j + m + 1 <= n)
            {
                g[i + 1][j + m + 1] += g[i][j];
                g[i + 1][j + m + 1] %= MOD;
            }
        }
    }
    ++g1[0];
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            g1[i] += g[j][i];
            g1[i] %= MOD;
        }
    }
    for (int i = 0; i <= n; ++i)
    {
        f1[i] = f[now][i];
    }

    ll ans = 0;
    for (int i = 0; i <= n; ++i)
    {
        ans += (f1[i] * g1[n - i] % MOD);
        ans %= MOD;
    }

    printf("%lld\n", ans);

    return 0;
}