106272024-04-07 00:08:28111Tömbök előállításacpp17Accepted 100/1001.442s4932 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define MOD 1000000007

using vec=array<int,1000>;

int M;

vec operator*(vec a,vec b){
	vec r{};
	for(int i=0;i<M;i++){
		for(int j=0;j<M;j++){
			r[i]+=a[j]*b[(i-j+M)%M];
			r[i]%=MOD;
		}
	}
	return r;
}

vec vec_pow(vec x,int p){
	vec r{};
	r[0]=1;
	while(p){
		if(p&1){
			r=r*x;
		}
		x=x*x;
		p>>=1;
	}
	return r;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,L,R,K;
	cin>>N>>M>>L>>R>>K;
	vec v{};
	for(int i=0;i<M;i++){
		int s=L%M>i?L/M:L/M-1;
		int e=R%M<i?R/M-1:R/M;
		v[i]=e-s;
	}
	v=vec_pow(v,N);
	cout<<v[K]<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2072 KiB
2Accepted3ms2376 KiB
3Accepted3ms2472 KiB
subtask210/10
4Accepted2ms2432 KiB
5Accepted3ms2824 KiB
6Accepted3ms3124 KiB
subtask310/10
7Accepted3ms3332 KiB
8Accepted3ms3548 KiB
9Accepted3ms3660 KiB
10Accepted3ms3940 KiB
11Accepted3ms3896 KiB
12Accepted3ms3912 KiB
13Accepted3ms3796 KiB
subtask47/7
14Accepted3ms3956 KiB
15Accepted3ms3912 KiB
16Accepted3ms3964 KiB
17Accepted3ms3960 KiB
18Accepted3ms3996 KiB
19Accepted3ms4248 KiB
20Accepted3ms4296 KiB
subtask58/8
21Accepted57ms4296 KiB
22Accepted28ms4300 KiB
23Accepted37ms4300 KiB
24Accepted25ms4264 KiB
25Accepted14ms4388 KiB
26Accepted8ms4348 KiB
27Accepted43ms4400 KiB
28Accepted12ms4400 KiB
29Accepted57ms4360 KiB
30Accepted57ms4352 KiB
subtask625/25
31Accepted14ms4356 KiB
32Accepted14ms4352 KiB
33Accepted6ms4504 KiB
34Accepted7ms4464 KiB
35Accepted4ms4460 KiB
36Accepted6ms4516 KiB
37Accepted3ms4364 KiB
38Accepted3ms4412 KiB
39Accepted9ms4304 KiB
40Accepted8ms4624 KiB
subtask740/40
41Accepted358ms4604 KiB
42Accepted1.151s4612 KiB
43Accepted1.31s4824 KiB
44Accepted1.442s4820 KiB
45Accepted1.287s4784 KiB
46Accepted342ms4776 KiB
47Accepted555ms4784 KiB
48Accepted10ms4932 KiB
49Accepted888ms4892 KiB
50Accepted418ms4884 KiB