考场上真的尽力了，但两张草稿纸只换来一个 \(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;
}