题目描述
求正整数 $n$ 的划分个数
Solution
五边形数定理不太会而且也没有什么运用价值，说白了就算我看懂了我也用不来，所以考虑 dp。
令 $f[i][j]$ 表示前 $i$ 个正整数，之和为 $j$ 的方案数。
转移有 $f[i][j]=f[i-1][j]+f[i][j-i]$ 。保证了有序性。
但是显然这样复杂度是接受不了的，考虑根号分治。
$f[i][j]$ 的 $i$ 只计算到前 $m-1$ 个。
对于 $\ge m$ 的数，我们令有 $i$ 个 $\ge m$ 的数，之和为 $j$ 的方案数，由 $g[i][j]$ 表示。
$g[i][j]=g[i-1][j-m]+g[i][j-i]$。前者表示新增一个大小为 $m$ 的数，后者表示将当前的 $i$ 个数都增加 $1$。由于确保了加入数的大小是从大到小的，所以可以不重不漏的计算完。
计算答案， $ans=\sum\limits_{i=0}^{n}(f[m-1][i]\times\sum\limits_{j=0}^mg[j][n-i])$
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int f[maxn],g[405][maxn];
signed main(void){
int n,mod,ans=0,i,j,k;
read(n);read(mod);
int m=sqrt(n)+1;
f[0]=1;
for (i=1;i<m;i++) {
for (j=i;j<=n;j++)
f[j]+=f[j-i],f[j]%=mod;
}
g[0][0]=1;
for (i=1;i<=m;i++) {
for (j=i;j<=n;j++) {
g[i][j]=g[i][j-i];
if (j>=m) g[i][j]=(g[i][j]+g[i-1][j-m])%mod;
}
}
for (j=0;j<=n;j++) {
int sum=0;
for (i=0;i<=m;i++) sum+=g[i][n-j],sum%=mod;
ans=(ans+f[j]*sum)%mod;
}
printf("%lld",ans);
return 0;
}
|