2015 whu校赛f题big data(dp + 小技巧)

时间:2021-12-15 16:58:59

题意是给定五个数n(n <= 100),a,b,l,r 另外有函数序列f(x),其中f(x + 1) = f(x) + a或f(x)+ b,f(0) = 0,问有多少个这样的函数序列f(1)到f(n)使得函数序列的和在l和r之间

解题思路如下:

2015 whu校赛f题big data(dp + 小技巧)

图片有一处错误,要减去的是a*(n + 1) * n而不是 (b - a)* (n + 1) * n,此外,要注意x/c时向上取整和向下取整的问题。

这道题做做停停一个月了今天终于找时间ac了,有点感人呐

代码如下:

#include<cstdio>  
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
using namespace std;
#define LL long long

const LL maxn = 100 + 5;
const LL INF = 0x3f3f3f3f;
LL d[(maxn + 1) * maxn / 2];
//freopen("input.txt", "r", stdin);


void solve(int n) {
memset(d, 0, sizeof(d)); d[0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = (i + 1) * i / 2; j >= i; j--)
if(d[j] + d[j - i] > 1000000000000000000) d[j] = (d[j] + d[j - i]) % 1000000007;
else d[j] = d[j] + d[j - i];
}
}

int main() {
int n, a, b, L, R;
while(scanf("%d", &n) == 1) {
scanf("%d%d%d%d", &a, &b, &L, &R);
if(b != a) {
if(b < a) swap(a, b);
float xl = ceil( (float)(L - a*n*(n+1)/2) / (float)(b - a) ), xr = floor( (float)(R - a*n*(n+1)/2) / (float)(b - a) );
//ceil函数向上取整,floor函数向下取整
solve(n);
LL ans = 0;
if(xl < 0) xl = 0; if(xr > n*(n+1)/2) xr = n*(n+1)/2;
for(int i = xl; i <= xr; i++)
if(ans + d[i] > 1000000000000000000) ans = (ans + d[i]) % 1000000007;
else ans += d[i];
//for(int i = xl; i <= xr; i++) printf("%lld\n", d[i]);
printf("%d\n", ans % 1000000007);
//printf("%lld", d[0]);
}
else {
int xl = (L - a*n*(n+1)/2), xr = (R - a*n*(n+1)/2);
LL ans = 1;
if(0 <= xr && 0 >= xl){
for(int i = 1; i <= n; i++)
ans = (ans * 2) % 1000000007;
printf("%d\n", ans);
}
else printf("0\n");
}
}
return 0;
}