【CODEFORCES】 D. Flowers
2638 단어 동적 기획codeforces
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 modulo 1000000007 (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).
문제풀이: 이 문제는 비교적 간단한 동귀이다. d[i]를 설정하면 i송이 꽃을 먹었을 때의 총 방안수이다. 그러면 d[i]=d[i-1]+d[i-k]를 설정한다.주의해야 할 것은 d[0]=1, d[1]은 k=1에서 2와 같고 다른 때는 d[1]=1이다.이것 이외에 접두사와 구화로mod 출력 결과를 얻었습니다.
mod를 뽑는 것은 정말 기술적인 일이다.
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int t,k,a[100005],b[100005],max1;
long long d[100005],ans,sum[100005];
int main()
{
max1=0;
scanf("%d%d",&t,&k);
for (int i=0;i<t;i++)
{
scanf("%d%d",&a[i],&b[i]);
max1=max(b[i],max1);
}
d[0]=1;
if (k==1) d[1]=2;
else d[1]=1;
for (int i=2;i<k;i++) d[i]=d[i-1];
for (int i=k;i<=max1;i++)
d[i]=(d[i-1]+d[i-k])%1000000007;
sum[0]=d[0];
for (int i=1;i<=max1;i++)
sum[i]=(sum[i-1]+d[i])%1000000007;
for (int i=0;i<t;i++)
printf("%I64d
",((sum[b[i]]+d[a[i]])%1000000007-sum[a[i]]%1000000007+1000000007)%1000000007);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.