NFLSOJ222 雨

题目大意

下雨了，下了若干场雨。每场雨的降水量为整数个单位，而且每场雨的降水量单调不降。

已知第一场雨的降水量在区间大于等于 (x) 且小于等于 (y) ，总降水量为 (n) ，求降水量可能数。模 (10^9+7) 。

数据范围：(1leq xleq yleq nleq 3 imes 10^5)。

本题题解

首先可以转化为，第一个数只有 (geq x) 的限制。也就是：( ext{ans} = ext{calc}(x) - ext{calc}(y + 1))，那么我们只需要实现这个 ( ext{calc}) 函数，即求：有多少组不同的不下降序列，最小值不小于 (x)，和为 (n)。

考虑两种 DP。

第一种 DP，设 (f(i,j)) 表示考虑到数值 (i)，当前序列里元素总和为 (j) 的方案数。朴素的转移，是枚举 (i) 这种数值取了 (k) 个，则 (f(i - 1,j - k imes i) o f(i, j))。但由于 (k) 是没有限制的，所以我们用完全背包的方法做（从小到大枚举 (j)，(f(j - i) o f(j))）。时间复杂度 (mathcal{O}(n^2))。这种状态设计的妙处在于忽略了序列长度这一因素（因为本题对序列长度并没有要求），它的本质就是一个背包。

第二种 DP，设 (g(i,j)) 表示考虑了序列里前 (i) 个数，总和为 (j) 的方案数。转移有两种，要么把所有数都 (+1)，要么在序列的最前面添加一个最小值 (x)。即：(g(i, j) o g(i, j + i)) 或 (g(i,j) o g(i + 1, j + x))。这也是经典的划分数问题的 DP 做法。它的时间复杂度也是 (mathcal{O}(n^2)) 的。

现在我们将这两种 (mathcal{O}(n^2)) 的 DP 结合起来。

设 (B = sqrt{n})。

对于序列里小于 (B) 的元素，我们用第一种 DP，时间复杂度是 (mathcal{O}(Bn))。

对于序列里大于等于 (B) 的元素，我们用第二种 DP，时间复杂度是 (mathcal{O}(frac{n^2}{B}))。

最后将两个 DP 的结果做卷积（当然，我们只需要知道卷积的第 (n) 项，所以直接 (mathcal{O}(n)) 计算即可，不需要 FFT）,即可得到答案。

综上，我们在 (mathcal{O}(nsqrt{n})) 的时间复杂度内解决了本题。

参考代码

// problem: nflsoj222
#include <bits/stdc++.h>
using namespace std;

#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 3e5;
const int MAXB = 550;
const int MOD = 1e9 + 7;
inline int mod1(int x) { return x < MOD ? x : x - MOD; }
inline int mod2(int x) { return x < 0 ? x + MOD : x; }
inline void add(int &x, int y) { x = mod1(x + y); }
inline void sub(int &x, int y) { x = mod2(x - y); }

int f[MAXN + 5], g[MAXN + 5], dp[2][MAXN + 5];
int calc(int x, int sum, int B) {
	if (B < x) B = x;
	
	for (int i = 0; i <= sum; ++i) {
		f[i] = 0;
		g[i] = 0;
		dp[0][i] = 0;
	}
	
	f[0] = 1;
	for (int i = x; i < B; ++i) {
		// cerr << i << endl;
		for (int j = 0; j <= sum - i; ++j) {
			add(f[j + i], f[j]); // 完全背包 
		}
	}
	
	dp[0][0] = 1;
	for (int i = 0; i <= sum / B; ++i) {
		int cur = (i & 1);
		int nxt = (cur ^ 1);
		for (int j = 0; j <= sum; ++j)
			dp[nxt][j] = 0;
		for (int j = 0; j <= sum; ++j) if (dp[cur][j]) {
			add(g[j], dp[cur][j]);
			
			if (j + B <= sum)
				add(dp[nxt][j + B], dp[cur][j]);
			
			if (i != 0 && j + i <= sum)
				add(dp[cur][j + i], dp[cur][j]);
		}
	}
	
	int res = 0;
	for (int i = 0; i <= sum; ++i) {
		add(res, (ll)f[i] * g[sum - i] % MOD);
	}
	return res;
}
int main() {
	int l, r, sum, B;
	cin >> l >> r >> sum;
	
	B = sqrt(sum) * 2;
	B = min(B, sum);
	
	cout << mod2(calc(l, sum, B) - calc(r + 1, sum, B)) << endl;
	return 0;
}