10627 2024. 04. 07 00:08:28 111 Tömbök előállítása cpp17 Elfogadva 100/100 1.442s 4932 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2072 KiB
2 Elfogadva 3ms 2376 KiB
3 Elfogadva 3ms 2472 KiB
subtask2 10/10
4 Elfogadva 2ms 2432 KiB
5 Elfogadva 3ms 2824 KiB
6 Elfogadva 3ms 3124 KiB
subtask3 10/10
7 Elfogadva 3ms 3332 KiB
8 Elfogadva 3ms 3548 KiB
9 Elfogadva 3ms 3660 KiB
10 Elfogadva 3ms 3940 KiB
11 Elfogadva 3ms 3896 KiB
12 Elfogadva 3ms 3912 KiB
13 Elfogadva 3ms 3796 KiB
subtask4 7/7
14 Elfogadva 3ms 3956 KiB
15 Elfogadva 3ms 3912 KiB
16 Elfogadva 3ms 3964 KiB
17 Elfogadva 3ms 3960 KiB
18 Elfogadva 3ms 3996 KiB
19 Elfogadva 3ms 4248 KiB
20 Elfogadva 3ms 4296 KiB
subtask5 8/8
21 Elfogadva 57ms 4296 KiB
22 Elfogadva 28ms 4300 KiB
23 Elfogadva 37ms 4300 KiB
24 Elfogadva 25ms 4264 KiB
25 Elfogadva 14ms 4388 KiB
26 Elfogadva 8ms 4348 KiB
27 Elfogadva 43ms 4400 KiB
28 Elfogadva 12ms 4400 KiB
29 Elfogadva 57ms 4360 KiB
30 Elfogadva 57ms 4352 KiB
subtask6 25/25
31 Elfogadva 14ms 4356 KiB
32 Elfogadva 14ms 4352 KiB
33 Elfogadva 6ms 4504 KiB
34 Elfogadva 7ms 4464 KiB
35 Elfogadva 4ms 4460 KiB
36 Elfogadva 6ms 4516 KiB
37 Elfogadva 3ms 4364 KiB
38 Elfogadva 3ms 4412 KiB
39 Elfogadva 9ms 4304 KiB
40 Elfogadva 8ms 4624 KiB
subtask7 40/40
41 Elfogadva 358ms 4604 KiB
42 Elfogadva 1.151s 4612 KiB
43 Elfogadva 1.31s 4824 KiB
44 Elfogadva 1.442s 4820 KiB
45 Elfogadva 1.287s 4784 KiB
46 Elfogadva 342ms 4776 KiB
47 Elfogadva 555ms 4784 KiB
48 Elfogadva 10ms 4932 KiB
49 Elfogadva 888ms 4892 KiB
50 Elfogadva 418ms 4884 KiB