长久不刷，$dp$有很大退步。
Solution
首先记$f_{i,j}$表示前$f(i)=j$的答案，有以下方程：
$$
f_{i,j}=\sum_{k=1}^{i}f_{k,j-1}\cdot (2^{i-k}-1)\cdot 2^{k\cdot (i-k)}
$$
这个式子是什么意思呢？首先我们考虑划分点$i$和$k$，从$[1,k]$出发延申到$[k+1,i]$中的每条线段都可以要，所以有$2^{k\cdot (i-k)}$条，而由于我们又要新增一条，所以$[k+1,i]\cdots[i,i]$中的所有线段必须至少存在一条，所以有$2^{i-k}-1$种方案。
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
47
48
49
| #pragma GCC optimize("O2,O3,Ofast")
#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || '9' < c) { if(c == '-') flag = 1; c = getchar(); }
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
inline void write(T res)
{
if(res < 0) res = -res, putchar('-');
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char s) { putchar(s); }
template <>
inline void write(const char *s) { while(*s) putchar(*s ++); }
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 505, mod = 1e9 + 7;
int n, m;
int f[N][N], pw[N * N], fac[N];
int main()
{
read(n, m);
pw[0] = 1;
for(int i = 1;i < N * N;i ++) pw[i] = 1ll * 2 * pw[i - 1] % mod;
for(int i = 0;i <= n;i ++) f[i][0] = 1;
for(int k = 1;k <= m;k ++)
{
for(int i = k;i <= n;i ++)
{
for(int j = k - 1;j <= i;j ++)
f[i][k] = (f[i][k] + 1ll * f[j][k - 1] * (pw[i - j] - 1) % mod * pw[j * (i - j)] % mod) % mod;
}
}
write(f[n][m]);
return 0;
}
|