Flowers(DP)
3020 단어 dp
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.
But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.
Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo1000000007 (109 + 7).
Input
Input contains several test cases.
The first line contains two integers t and k (1 ≤ t, k ≤ 105), where t represents the number of test cases.
The next t lines contain two integers ai and bi (1 ≤ ai ≤ bi ≤ 105), describing the i-th test.
Output
Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between ai and bi flowers at dinner modulo 1000000007 (109 + 7).
Sample test(s)
input
3 2
1 3
2 3
4 4
output
6
5
5
Note
For K = 2 and length 1 Marmot can eat (R).
For K = 2 and length 2 Marmot can eat (RR) and (WW).
For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).
For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).
제목:
t와 k를 주면 t팀의 문의가 있음을 의미합니다.k는 한 번에 K송이 W꽃만 먹을 수 있음을 의미하며, 이후 t조의 a-b 구간을 제시한다.이 구간 내의 길이 서열이 조건을 충족시키는 방법수를 물어본다.
아이디어:
DP.dp[i]=dp[i-k]+dp[i-1]는 한 번에 K송이 W꽃을 먹거나 R꽃을 한 번에 한 송이 먹는 것을 의미한다.마지막 답안의 뺄셈을 기억하고 + MOD +% MOD를 넣으세요.안 그러면 실수할 거야.
AC:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int MAX = 100005;
ll dp[MAX];
ll sum[MAX];
ll a[MAX], b[MAX];
int main() {
int t, k;
scanf("%d%d", &t, &k);
ll Max = 0;
for (int i = 1; i <= t; ++i) {
scanf("%I64d%I64d", &a[i], &b[i]);
Max = max(Max, b[i]);
}
for (int i = 0; i < k; ++i) {
dp[i] = 1;
sum[i] = sum[i - 1] + dp[i];
}
for (int i = k; i <= Max; ++i) {
dp[i] = (dp[i - k] + dp[i - 1]) % MOD;
sum[i] = (dp[i] % MOD + sum[i - 1] % MOD) % MOD;
}
for (int i = 1; i <= t; ++i) {
printf("%I64d
", (sum[b[i]] - sum[a[i] - 1] + MOD) % MOD);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.