传送门

考场上真的尽力了，但两张草稿纸只换来一个 \(n^3\) DP系列

• 类似本题可以通过把两个不同的做法拼起来以降低复杂度的思路？

首先根本不用枚举轮数，如果只记 \(f_{i, j}\) 为当前选数下限为 \(I\) ，总和为 \(j\) 的方案数，转移枚举这个数选的个数的话，前缀和优化就是 \(n^2\) 的
然后考虑另一个DP
如果令 \(g_{i, j}\) 表示选了 \(i\) 个数，总和为 \(j\) 的方案数，那这个东西如何转移呢？
显然转移必需保证选的数单调，要不然会重
所以考虑转移时插入一个大小为零的数或令之前选过的数全部 \(+1\) ，就保证了高度单调递减
（？）这里我说的对吗 神仙思路，想不到
所以转移是 \(g_{i, j}=g_{i-1, j}+g_{i, j-i}\)
这两个DP都是 \(n^2\) 的，但发现枚举的东西不一样
如果让f只处理限制小于 \(\sqrt n\) 的情况，那剩下的数都大于 \(\sqrt n\) ，最多被分成 \(\sqrt n\) 个，总复杂度就变成了 \(O(n\sqrt n)\)
合并就枚举值域断点合并即可

Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long 
#define fir first
#define sec second 
#define make make_pair
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int x, y, n;
ll p;
inline void md(ll& a, ll b) {a+=b; a=a>=p?a-p:a;}

namespace force{
	ll ans;
	ll dfs(int tot, int lst) {
		//cout<<"dfs "<<tot<<' '<<lst<<endl;
		if (tot>n) return 0;
		if (tot==n) return 1;
		ll tem=0;
		for (int i=lst; i<=n; ++i) 
			tem = (tem+dfs(tot+i, i))%p;
		return tem;
	}
	void solve() {
		for (int i=x; i<=y; ++i) {
			ans = (ans+dfs(i, i))%p;
		}
		printf("%lld\n", ans%p);
		exit(0);
	}
}

namespace task1{
	ll dp[500][500][500], ans;
	void solve() {
		if (y==n) ++ans;
		for (int i=x; i<=y; ++i) dp[1][i][i]=1;
		for (int i=2; i<=n; ++i)
			for (int j=1; j<=n; ++j)
				for (int k=j; k<=n; ++k) {
					for (int h=1; h<=j; ++h)
						dp[i][j][k] = (dp[i][j][k]+dp[i-1][h][k-j])%p;
					if (k==n) ans=(ans+dp[i][j][k])%p;
				}
		printf("%lld\n", ans);
		exit(0);
	}
}

namespace task2{
	ll ans;
	struct pair_hash{inline size_t operator () (pair<int, int> p) const {return hash<int>()(p.fir*13131+p.sec);}};
	unordered_map<pair<int, int>, ll, pair_hash> mp{5000, pair_hash()};
	ll dfs(int tot, int lst) {
		//cout<<"dfs "<<tot<<' '<<lst<<endl;
		if (tot>n) return 0;
		if (tot==n) return 1;
		if (mp.find(make(tot, lst))!=mp.end()) return mp[make(tot, lst)];
		ll tem=0;
		for (int i=lst; i<=n; ++i) 
			tem = (tem+dfs(tot+i, i))%p;
		mp[make(tot, lst)]=tem;
		return tem;
	}
	void solve() {
		for (int i=x; i<=y; ++i)
			ans = (ans+dfs(i, i))%p;
		printf("%lld\n", ans%p);
		exit(0);
	}
}

namespace task3{
	ll f[320][N], sum[N], g[320][N], ans, sum2[N];
	void solve() {
		int lim=sqrt(n);
		for (int i=x; i<=lim; ++i) {
			if (i<=y) f[i][i]=1;
			for (int j=i; j<=n; ++j) {
				f[i][j] = (f[i][j]+sum[j-i])%p;
				sum[j] = (sum[j]+f[i][j])%p;
			}
		}
		g[0][0]=1;
		for (int i=1; i<=lim; ++i)
			for (int j=max(x-lim, 1); i*lim+j<=n; ++j) if (j>=i) {
				cout<<i<<' '<<j<<endl;
				g[i][j] = (g[i][j]+g[i-1][j-max(x-lim, 1)]+g[i][j-i])%p;
				sum2[j+i*lim] = (sum2[j+i*lim]+g[i][j])%p;
			}
		cout<<"sum2: "; for (int i=1; i<=n-lim; ++i) cout<<sum2[i]<<' '; cout<<endl;
		memset(g, 0, sizeof(g));
		g[0][0]=1;
		for (int i=1; i<=lim; ++i)
			for (int j=max(y+1-lim, 1); i*lim+j<=n; ++j) if (j>=i) {
				g[i][j] = (g[i][j]+g[i-1][j-max(y+1-lim, 1)]+g[i][j-i])%p;
				sum2[j+i*lim] = (sum2[j+i*lim]-g[i][j])%p;
			}
		cout<<"sum: "; for (int i=1; i<=n; ++i) cout<<sum[i]<<' '; cout<<endl;
		cout<<"sum2: "; for (int i=1; i<=n; ++i) cout<<sum2[i]<<' '; cout<<endl;
		for (int i=0; i<=n; ++i) 
			ans = (ans+sum[i]*sum2[n-i]%p)%p;
		printf("%lld\n", (ans%p+p)%p);
		exit(0);
	}
}

namespace task{
	ll f[N], g[N], sum[N];
	ll calc(int x) {
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		memset(sum, 0, sizeof(sum));
		int lim=max(x, (int)sqrt(n));
		f[0]=1;
		for (int i=x; i<lim; ++i)
			for (int j=i; j<=n; ++j)
				md(f[j], f[j-i]);
		g[0]=1; sum[0]=1;
		for (int i=1,t; i<=n/lim; ++i) {
			t=i*lim;
			for (int j=i; t+j<=n; ++j) md(g[j], g[j-i]);
			for (int j=0; t+j<=n; ++j) md(sum[t+j], g[j]);
		}
		ll ans=0;
		for (int i=0; i<=n; ++i) md(ans, f[i]*sum[n-i]%p);
		return ans;
	}
	void solve() {
		ll ans=calc(x)-calc(y+1);
		printf("%lld\n", (ans%p+p)%p);
		exit(0);
	}
}

signed main()
{
	x=read(); y=read(); n=read(); p=read();
	//force::solve();
	//task1::solve();
	//task2::solve();
	task::solve();
	
	return 0;
}