106272024-04-07 00:08:28111Tömbök előállításacpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2072 KiB
2Elfogadva3ms2376 KiB
3Elfogadva3ms2472 KiB
subtask210/10
4Elfogadva2ms2432 KiB
5Elfogadva3ms2824 KiB
6Elfogadva3ms3124 KiB
subtask310/10
7Elfogadva3ms3332 KiB
8Elfogadva3ms3548 KiB
9Elfogadva3ms3660 KiB
10Elfogadva3ms3940 KiB
11Elfogadva3ms3896 KiB
12Elfogadva3ms3912 KiB
13Elfogadva3ms3796 KiB
subtask47/7
14Elfogadva3ms3956 KiB
15Elfogadva3ms3912 KiB
16Elfogadva3ms3964 KiB
17Elfogadva3ms3960 KiB
18Elfogadva3ms3996 KiB
19Elfogadva3ms4248 KiB
20Elfogadva3ms4296 KiB
subtask58/8
21Elfogadva57ms4296 KiB
22Elfogadva28ms4300 KiB
23Elfogadva37ms4300 KiB
24Elfogadva25ms4264 KiB
25Elfogadva14ms4388 KiB
26Elfogadva8ms4348 KiB
27Elfogadva43ms4400 KiB
28Elfogadva12ms4400 KiB
29Elfogadva57ms4360 KiB
30Elfogadva57ms4352 KiB
subtask625/25
31Elfogadva14ms4356 KiB
32Elfogadva14ms4352 KiB
33Elfogadva6ms4504 KiB
34Elfogadva7ms4464 KiB
35Elfogadva4ms4460 KiB
36Elfogadva6ms4516 KiB
37Elfogadva3ms4364 KiB
38Elfogadva3ms4412 KiB
39Elfogadva9ms4304 KiB
40Elfogadva8ms4624 KiB
subtask740/40
41Elfogadva358ms4604 KiB
42Elfogadva1.151s4612 KiB
43Elfogadva1.31s4824 KiB
44Elfogadva1.442s4820 KiB
45Elfogadva1.287s4784 KiB
46Elfogadva342ms4776 KiB
47Elfogadva555ms4784 KiB
48Elfogadva10ms4932 KiB
49Elfogadva888ms4892 KiB
50Elfogadva418ms4884 KiB