結果
| 問題 | No.1474 かさまＪ |
| ユーザー |
 penguinman
|
| 提出日時 | 2021-04-09 23:02:50 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 486 ms / 2,500 ms |
| コード長 | 25,795 bytes |
| コンパイル時間 | 3,096 ms |
| コンパイル使用メモリ | 245,256 KB |
| 実行使用メモリ | 285,380 KB |
| 最終ジャッジ日時 | 2024-06-25 06:48:33 |
| 合計ジャッジ時間 | 6,416 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 3 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 281 ms
112,768 KB |
| testcase_06 | AC | 26 ms
24,064 KB |
| testcase_07 | AC | 38 ms
7,040 KB |
| testcase_08 | AC | 17 ms
8,576 KB |
| testcase_09 | AC | 486 ms
162,944 KB |
| testcase_10 | AC | 15 ms
10,496 KB |
| testcase_11 | AC | 4 ms
5,376 KB |
| testcase_12 | AC | 4 ms
5,376 KB |
| testcase_13 | AC | 268 ms
173,744 KB |
| testcase_14 | AC | 193 ms
55,424 KB |
| testcase_15 | AC | 56 ms
27,776 KB |
| testcase_16 | AC | 20 ms
10,404 KB |
| testcase_17 | AC | 157 ms
65,116 KB |
| testcase_18 | AC | 321 ms
234,320 KB |
| testcase_19 | AC | 372 ms
272,136 KB |
| testcase_20 | AC | 389 ms
285,380 KB |
ソースコード
#include<bits/stdc++.h>
//using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i, j, n) for(int i = int(j); i < int(n); i++)
#define REP(i, j, n) for(int i = int(j); i <= int(n); i++)
#define per(i, j, n) for(int i = int(j); int(n) <= i; i--)
#define ALL(a) (a).begin(),(a).end()
#define revALL(a) (a).rbegin(),(a).rend()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define ln "\n"
using std::endl;
using std::cin;
using std::cout;
using ll = long long;
using lint = __int128;
using std::vector;
using std::string;
using std::upper_bound;
using std::lower_bound;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll, ll>;
using vs = vector<int>;
using vss = vector<vs>;
using pss = std::pair<int, int>;
using vl = vector<lint>;
using vll = vector<vl>;
using pll = std::pair<lint, lint>;
//
constexpr ll MOD = 1e9+7, root = 0;
//constexpr ll MOD = 998244353, root = 3;
//constexpr ll MOD = 924844033, root = 5;
//constexpr ll MOD = 1e4, root = 0;
//constexpr ll MOD = 1e5, root = 0;
//constexpr ll MOD = 1e6, root = 0;
//constexpr ll MOD = 1e7, root = 0;
constexpr ll MAX = 1e6+10;
constexpr ll inf = (1ll << 60);
constexpr lint linf = lint(inf) * inf;
//lint output
void lout(lint N, string add){
string S;
if(N < 0){
S += '-';
N = -N;
}
string T;
if(N == 0) T += '0';
while(N){
T += N % 10 + '0';
N /= 10;
}
reverse(ALL(T));
S += T;
cout << S << add;
}
//lint input
lint lin(){
string S; cin >> S;
bool flag = 0;
if(S[0] == '-') flag = 1;
lint ret = 0;
rep(i, flag, S.size()) ret = ret * 10 + S[i] - '0';
if(flag) ret *= -1;
return ret;
}
//reversed priority_queue
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
//modpow
ll modpow(ll X, ll Y, ll mod){
ll ret = 1;
while(Y){
if(Y & 1){
ret *= X;
ret %= mod;
}
X *= X;
X %= mod;
Y >>= 1;
}
return ret % mod;
}
//calc: ax + by = gcd(a, b)
template<typename T>
void extGCD(ll a, ll b, T &x, T &y){
if(b == 0){
x = 1;
y = 0;
return;
}
extGCD(b, a%b, y, x);
/*(a-b)x + by = gcd(a,b)
ax + b(y-x) = gcd(a,b)*/
y -= a / b * x;
}
//calc: ax + by = c
template<typename T>
bool solve_equation(ll a, ll b, ll c, T &x, T &y){
ll d = std::__gcd(a, b);
if(c % d) return false;
extGCD(a, b, x, y);
ll e = a * b / d;
x %= e;
y %= e;
x = (lint)x * (c/d) % e;
y = (lint)y * (c/d) % e;
return true;
}
//segment_tree, 1-indexed
template<typename T>
struct segment_tree{
ll N;
T INF;
vector<T> node;
segment_tree(vector<T> &X, T INF_):INF(INF_){
N = 1;
while(N < X.size()) N <<= 1;
node.resize(2*N, INF);
rep(i, 0, X.size()) node[N+i] = X[i];
per(i, N-1, 0) node[i] = compare(node[i*2], node[i*2+1]);
}
T compare(T A, T B){
return std::max(A, B);
}
//for max_right, min_left
//compare をいじった時にはこちらも変えた方がよい
bool is_lower(T A, T B){
return A < B;
}
//isAdd == true: add
//isAdd == false: update
void update(ll index, T val, bool isAdd){
index += N;
if(isAdd) node[index] += val;
else node[index] = val;
while(index > 0){
index >>= 1;
node[index] = compare(node[index*2], node[index*2+1]);
}
}
T calc(ll left, ll right){
T ret = INF;
left += N;
right += N;
while(left < right){
if(left & 1) ret = compare(node[left++], ret);
if(right & 1) ret = compare(node[--right], ret);
left >>= 1;
right >>= 1;
}
return ret;
}
//[left, inf)
ll min_left(ll left, T val, ll now = 1, ll l = 0, ll r = -1){
if(r < 0) r = N;
if(is_lower(node[now], val) || r<=left) return r;
if(N <= now) return l;
ll vl = min_left(left, val, now*2, l, (l+r)/2);
if(vl == (l+r)/2) return min_left(left, val, now*2+1, (l+r)/2, r);
return vl;
}
//(-inf, right]
//内部では (-inf, right+1)
ll max_right(ll right, T val, ll now = 1, ll l = 0, ll r = -1){
if(r < 0) r = N, right++;
if(is_lower(node[now], val) || right<=l) return l-1;
if(N <= now) return l;
ll vr = max_right(right, val, now*2+1, (l+r)/2, r);
if(vr == (l+r)/2-1) return max_right(right, val, now*2, l, (l+r)/2);
return vr;
}
};
//lazy_segment_tree
template<typename T>
struct lazy_segment_tree{
int N, height;
vector<T> node, lazy;
T valINF, lazyINF;
lazy_segment_tree(vector<T> X, T valINF_, T lazyINF_) : valINF(valINF_), lazyINF(lazyINF_){
N = 1, height = 0;
while(N < X.size()) N <<= 1, height++;
node.resize(2*N, valINF);
lazy.resize(2*N, lazyINF);
rep(i, 0, X.size()) node[i+N] = X[i];
per(i, N-1, 0) node[i] = compare(node[i*2], node[i*2+1]);
}
void add(ll left, ll right, T val){
ll l = left+N, r = right+N;
ll L = l, R = r;
per(i, height, 0){
eval(l >> i);
eval(r >> i);
}
while(l < r){
if(l & 1){
addition(lazy[l], val);
l++;
}
if(r & 1){
r--;
addition(lazy[r], val);
}
l >>= 1;
r >>= 1;
}
while(L){
if(lazy[L]==lazyINF && L<N){
eval(L*2);
eval(L*2+1);
node[L] = compare(node[L*2], node[L*2+1]);
}
if(lazy[R]==lazyINF && R<N){
eval(R*2);
eval(R*2+1);
node[R] = compare(node[R*2], node[R*2+1]);
}
L >>= 1;
R >>= 1;
}
}
T calc(ll left, ll right){
ll l = left+N, r = right+N;
per(i, height, 0){
eval(l >> i);
eval(r >> i);
}
T ret = valINF;
while(l < r){
if(l & 1){
eval(l);
ret = compare(node[l], ret);
l++;
}
if(r & 1){
r--;
eval(r);
ret = compare(node[r], ret);
}
l >>= 1;
r >>= 1;
}
return ret;
}
//[left, inf)
ll min_left(ll left, T val, ll now = 1, ll l = 0, ll r = -1){
if(r < 0) r = N;
eval(now);
if(is_lower(node[now], val) || r<=left) return r;
if(N <= now) return l;
ll vl = min_left(left, val, now*2, l, (l+r)/2);
if(vl == (l+r)/2) return min_left(left, val, now*2+1, (l+r)/2, r);
return vl;
}
//(-inf, right]
//内部では (-inf, right+1)
ll max_right(ll right, T val, ll now = 1, ll l = 0, ll r = -1){
if(r < 0) r = N, right++;
eval(now);
if(is_lower(node[now], val) || right<=l) return l-1;
if(N <= now) return l;
ll vr = max_right(right, val, now*2+1, (l+r)/2, r);
if(vr == (l+r)/2-1) return max_right(right, val, now*2, l, (l+r)/2);
return vr;
}
private:
T compare(T A, T B){
return std::max(A, B);
}
//for max_right, min_left
//compare をいじった時にはこちらも変えた方がよい
bool is_lower(T A, T B){
return A < B;
}
void addition(T &A, T B){
//addition :
A += B;
//update : A = B;
}
void eval(int now){
if(lazy[now] == lazyINF) return;
if(now < N){
addition(lazy[now*2], lazy[now]);
addition(lazy[now*2+1], lazy[now]);
}
addition(node[now], lazy[now]);
lazy[now] = lazyINF;
}
};
//union_find_tree
struct union_find{
ll N;
vi par, siz;
union_find(int n) : N(n){
par.resize(N);
siz.resize(N, 1);
rep(i,0,N) par[i] = i;
}
ll root(ll X){
if(par[X] == X) return X;
return par[X] = root(par[X]);
}
bool same(ll X, ll Y){
return root(X) == root(Y);
}
void unite(ll X, ll Y){
X = root(X);
Y = root(Y);
if(X == Y) return;
if(siz[Y] < siz[X]) std::swap(X, Y);
par[X] = Y;
siz[Y] += siz[X];
siz[X] = 0;
}
ll size(ll X){
return siz[root(X)];
}
};
//binary_indexed_tree
template<typename T>
struct binary_indexed_tree{
int N;
vector<T> bit;
binary_indexed_tree(int n):N(n){
bit.resize(N+1,0);
}
T addition(T a, T b){
return a+b;
}
void add(int x,T a){
x++;
for(x; x<=N; x+=(x&-x)) bit[x] = addition(bit[x], a);
}
T sum(int x){
x++;
T ret=0;
for(x; x>0; x-=(x&-x)) ret = addition(ret, bit[x]);
return ret;
}
ll lower_bound(T X){
if(sum(N)<X) return -1;
ll ret=0, memo=1;
T sum=0;
while(memo*2 <= N) memo *= 2;
while(0 < memo){
if(memo+ret<=N && addition(sum, bit[memo+ret])<X){
sum = addition(sum, bit[memo+ret]);
ret+=memo;
}
memo/=2;
}
return ret;
}
};
//directed_gragh
struct directed_gragh{
ll N, M;
vii edge;
directed_gragh(vii e) : edge(e){
N = edge.size();
rep(i,0,N) M += edge[i].size();
}
vi sort(){
vi ret, cnt(N);
rep(i,0,N){
for(auto p:edge[i]) cnt[p]++;
}
std::queue<ll> que;
rep(i,0,N){
if(cnt[i] == 0) que.push(i);
}
while(!que.empty()){
ll now = que.front(); que.pop();
ret.pb(now);
for(auto next:edge[now]){
cnt[next]--;
if(cnt[next] == 0) que.push(next);
}
}
return ret;
}
vii SCC(){
vii revedge(N), ver;
vi ind(N);
rep(i,0,N){
for(auto p:edge[i]) revedge[p].pb(i);
}
vi num(N, -1), po(N);
vector<bool> seen(N);
ll cnt = 0;
rep(i,0,N){
if(num[i] == -1){
dfs(i, num, cnt);
}
}
rep(i,0,N) po[num[i]] = i;
per(i,N-1,0){
ll X = po[i];
if(!seen[X]){
std::queue<ll> que;
vi v;
que.push(X);
seen[X] = 1;
while(!que.empty()){
ll now = que.front(); que.pop();
v.pb(now);
ind[now] = ver.size();
for(auto p:revedge[now]){
if(!seen[p]){
seen[p] = 1;
que.push(p);
}
}
}
ver.pb(v);
}
}
return ver;
}
void dfs(ll now, vi &num, ll &cnt){
num[now] = 0;
for(auto next:edge[now]){
if(num[next] == -1){
dfs(next, num, cnt);
}
}
num[now] = cnt++;
}
};
//sparse_table
template<typename T>
struct sparse_table{
ll N;
T INF;
vector<T> A;
vi mem;
vector<vector<T>> table;
std::function<T (T, T)> compare;
sparse_table(vector<T> X, T INF_, std::function<T (T, T)> compare_) : A(X), INF(INF_), compare(compare_){
N = A.size();
mem.resize(N+1, -1);
int height = 0;
while((1<<height) <= N+1){
mem[1<<height] = height;
height++;
}
table.resize(N, vector<T>(height, INF));
rep(i,0,N) table[i][0] = A[i];
rep(j,1,height){
rep(i,0,N){
table[i][j] = compare(table[i][j-1], table[std::min(N-1, i+(1ll<<(j-1)))][j-1]);
}
}
REP(i,1,N){
mem[i] = std::max(mem[i-1], mem[i]);
}
}
//[l, r)
T calc(ll l, ll r){
ll width = r-l;
return compare(table[l][mem[width]], table[r-(1<<mem[width])][mem[width]]);
}
};
//tree
struct tree{
int N, root;
vii dp;
vi par;
vi dist;
vi subtree;
vii edge;
tree(vii E, ll root_) : edge(E), root(root_){
N=edge.size();
dp.resize(N);
par.resize(N);
dist.resize(N,-1);
for(int i=0;i<N;i++) dp[i].resize(20);
dist[0]=dp[0][0]=0;
std::queue<int> que;
que.push(0);
while(!que.empty()){
int now=que.front(); que.pop();
for(int i=0;i<edge[now].size();i++){
int next=edge[now][i];
if(dist[next]==-1){
dist[next]=dist[now]+1;
que.push(next);
par[next]=now;
dp[next][0]=now;
}
}
}
for(int i=1;i<20;i++){
for(int j=0;j<N;j++) dp[j][i]=dp[dp[j][i-1]][i-1];
}
}
int LCA(int X,int Y){
if(dist[X]<dist[Y]) std::swap(X,Y);
{
int Z=dist[X]-dist[Y];
int i=0;
while(Z){
if(Z&1) X=dp[X][i];
i++;
Z>>=1;
}
}
if(X==Y) return X;
for(int i=19;i>=0;i--){
if(dp[X][i]!=dp[Y][i]){
X=dp[X][i];
Y=dp[Y][i];
}
}
return dp[X][0];
}
void Subtree(){
subtree.resize(N,-1);
dfs(0);
}
void dfs(ll now){
subtree[now]=1;
for(auto next:edge[now]){
if(subtree[next]==-1){
dfs(next);
subtree[now]+=subtree[next];
}
}
}
};
//max_flow
template<typename T>
struct max_flow{
struct Edge{
int to;
T cap;
int rev;
};
int N;
vector<vector<Edge>> edge;
vector<int> dist,itr;
max_flow(vii e,vii w){
N=e.size();
edge.resize(N);
rep(i,0,N){
rep(j,0,e[i].size()){
edge[i].pb((Edge){(int)e[i][j],(T)w[i][j],(int)edge[e[i][j]].size()});
edge[e[i][j]].pb((Edge){i,0,(int)edge[i].size()-1});
}
}
}
void add_edge(int from,int to,T cap){
edge[from].pb((Edge){to,cap,(int)edge[to].size()});
edge[to].pb((Edge){from,0,(int)edge[from].size()-1});
}
void bfs(int s){
dist.assign(N,-1);
std::queue<int> que;
dist[s]=0;
que.push(s);
while(!que.empty()){
int now=que.front(); que.pop();
for(auto p:edge[now]){
int next=p.to;
if(p.cap>0&&dist[next]<0){
dist[next]=dist[now]+1;
que.push(next);
}
}
}
}
T dfs(int now,int t,T f){
if(now==t) return f;
for(;itr[now]<edge[now].size();itr[now]++){
Edge& p=edge[now][itr[now]];
if(p.cap>0&&dist[now]<dist[p.to]){
T mem=dfs(p.to,t,std::min(f,p.cap));
if(mem>0){
p.cap-=mem;
edge[p.to][p.rev].cap+=mem;
return mem;
}
}
}
return 0;
}
T Query(int s,int t){
T ret=0;
while(1){
bfs(s);
if(dist[t]<0) break;
itr.assign(N,0);
while(1){
int mem=dfs(s,t,(1<<30));
if(mem<=0) break;
ret+=mem;
}
}
return ret;
}
};
//min_cost_flow
struct min_cost_flow{
struct Edge{
int to,cap,rev;
ll cost;
};
int N;
vector<vector<Edge>> edge;
vector<ll> dist,h;
void add_edge(int from,int to,int cap,ll cost){
edge[from].pb((Edge){to,cap,(int)edge[to].size(),cost});
edge[to].pb((Edge){from,0,(int)edge[from].size()-1,-cost});
}
min_cost_flow(vii e,vii m,vii w){
N=e.size();
edge.resize(N);
rep(i,0,N){
rep(j,0,e[i].size()){
add_edge(i,e[i][j],m[i][j],w[i][j]);
}
}
}
void potential(){
h.assign(N,0);
vector<vector<int>> edge2(N);
vii weight(N);
vector<int> cnt(N);
rep(i,0,N){
for(auto e:edge[i]){
if(e.cap>0&&e.cost<0){
edge2[i].pb(e.to);
weight[i].pb(-e.cost);
cnt[e.to]++;
}
}
}
std::queue<ll> que;
rep(i,0,N){
if(cnt[i]==0) que.push(i);
}
vector<int> ver;
while(!que.empty()){
int now=que.front(); que.pop();
ver.pb(now);
for(auto next:edge2[now]){
cnt[next]--;
if(cnt[next]==0) que.push(next);
}
}
per(i,N-1,0){
rep(j,0,edge2[ver[i]].size()){
int next=edge2[ver[i]][j];
h[ver[i]]=std::max(h[ver[i]],h[next]+weight[ver[i]][j]);
}
}
}
ll Query(int s,int t,int f){
ll ret=0;
potential();
while(f){
vi dist(N,inf);
vector<int> memv(N),meme(N);
dist[s]=0;
prique<std::pair<ll,int>> que;
que.push(mp(0,s));
while(!que.empty()){
auto now=que.top().second;
if(dist[now]<que.top().first){
que.pop();
continue;
}
que.pop();
rep(i,0,edge[now].size()){
auto e=edge[now][i];
auto next=e.to;
if(e.cap>0&&dist[next]>dist[now]+h[now]-h[next]+e.cost){
dist[next]=dist[now]+h[now]-h[next]+e.cost;
memv[next]=now;
meme[next]=i;
que.push(mp(dist[next],next));
}
}
}
if(dist[t]==inf) return -1;
int now=t,max=f;
while(now!=s){
auto& e=edge[memv[now]][meme[now]];
max=std::min(max,e.cap);
now=memv[now];
}
f-=max;
now=t;
while(now!=s){
auto& e=edge[memv[now]][meme[now]];
e.cap-=max;
auto& e2=edge[e.to][e.rev];
e2.cap+=max;
now=memv[now];
}
rep(i,0,N) h[i]+=dist[i];
ret+=h[t]*max;
}
return ret;
}
};
//fft
struct Fast_Fourier_Transform{
void dft(vector<std::complex<double>> &func,int inverse){
int siz=func.size();
if(siz==1) return;
vector<std::complex<double>> left,right;
rep(i,0,siz/2){
left.pb(func[i*2]);
right.pb(func[i*2+1]);
}
dft(left,inverse);
dft(right,inverse);
std::complex<double> now=1,zeta=std::polar(1.0,inverse*2.0*acos(-1)/siz);
rep(i,0,siz){
func[i]=left[i%(siz/2)]+now*right[i%(siz/2)];
now*=zeta;
}
}
template<typename T>
vector<double> multiply(vector<T> f,vector<T> g){
vector<std::complex<double>> nf,ng;
int siz=1;
while(siz<f.size()+g.size()) siz<<=1;
nf.resize(siz);
ng.resize(siz);
rep(i,0,f.size()) nf[i]=f[i];
rep(i,0,g.size()) ng[i]=g[i];
dft(nf,1);
dft(ng,1);
rep(i,0,siz) nf[i]*=ng[i];
dft(nf,-1);
vector<double> ret(siz);
rep(i,0,siz) ret[i]=nf[i].real()/siz;
return ret;
}
};
//ntt
struct Numver_Theoretic_Transform{
vii mem;
Numver_Theoretic_Transform(void){
mem.resize(25,vi(2));
rep(i,0,25){
mem[i][1]=modpow(root,MOD-1-(MOD-1)/(1<<i),MOD);
mem[i][0]=modpow(root,(MOD-1)/(1<<i),MOD);
}
}
void dft(vi &func,bool inverse,ll cnt){
int siz=func.size();
if(siz==1) return;
vi left,right;
rep(i,0,siz/2){
left.pb(func[i*2]);
right.pb(func[i*2+1]);
}
dft(left,inverse,cnt-1);
dft(right,inverse,cnt-1);
ll now=1;
ll zeta=mem[cnt][inverse];
rep(i,0,siz){
func[i]=(left[i%(siz/2)]+now*right[i%(siz/2)])%MOD;
now*=zeta;
now%=MOD;
}
}
vi multiply(vi f,vi g){
ll cnt=0;
vi nf,ng;
int siz=1;
while(siz<f.size()+g.size()){
cnt++;
siz<<=1;
}
nf.resize(siz);
ng.resize(siz);
rep(i,0,f.size()) nf[i]=f[i];
rep(i,0,g.size()) ng[i]=g[i];
dft(nf,0,cnt);
dft(ng,0,cnt);
rep(i,0,siz){
nf[i]*=ng[i];
nf[i]%=MOD;
}
dft(nf,1,cnt);
vi ret(siz);
ll div=modpow(siz,MOD-2,MOD);
rep(i,0,siz) ret[i]=nf[i]*div%MOD;
return ret;
}
};
//trie
struct Trie{
int let;
char lower;
vector<int> cnt;
vector<vector<int>> next;
Trie(int element,char low):let(element),lower(low){
cnt.resize(1);
next.pb(vector<int>(let,-1));
}
void insert(string S){
int now=0;
for(auto s:S){
int X=s-lower;
if(next[now][X]==-1){
next[now][X]=cnt.size();
cnt.pb(0);
next.pb(vector<int>(lower,-1));
}
now=next[now][X];
}
cnt[now]++;
}
int get(string S){
int now=0;
for(auto s:S){
int X=s-lower;
if(next[now][X]==-1) return 0;
now=next[now][X];
}
return cnt[now];
}
};
//tangent_compare
template<typename T>
struct tancomp{
int place(std::pair<T,T> p){
if(p.first<=0&&p.second<0) return 0;
if(p.first>0&&p.second<=0) return 1;
if(p.first==0&&p.second==0) return 2;
if(p.first>=0&&p.second>0) return 3;
return 4;
}
bool operator()(const std::pair<T,T> &l,const std::pair<T,T> &r){
if(place(l)!=place(r)) return place(l)<place(r);
//l.second/l.first<r.second/r.first
return l.second*r.first<l.first*r.second;
}
};
//declination_sort (偏角ソート)
template<typename T>
vector<std::pair<T,T>> Declination_sort(ll N,vector<T> X,vector<T> Y){
vector<std::pair<T,T>> ret(N);
rep(i,0,N){
ret[i]=(mp(X[i],Y[i]));
}
sort(ALL(ret),tancomp<T>());
return ret;
}
//xor の基底 (base)
vi get_bases(vi A,ll max_digit){
int now=0;
int N=A.size();
per(i,max_digit,0){
rep(j,now,N){
if(A[j]&(1ll<<i)){
std::swap(A[j],A[now]);
break;
}
}
if(now<N&&A[now]&(1ll<<i)){
rep(j,0,N){
if(j!=now&&A[j]&(1ll<<i)) A[j]^=A[now];
}
now++;
}
}
vi bases;
rep(i,0,now) bases.pb(A[i]);
return bases;
}
//binom_init, binom
vi fac,finv,inv;
void binom_init() {
fac.resize(MAX);
finv.resize(MAX);
inv.resize(MAX);
fac[0] = fac[1] = 1;
inv[1] = 1;
finv[0] = finv[1] = 1;
rep(i, 2, MAX){
fac[i] = fac[i-1]*i%MOD;
inv[i] = MOD-MOD/i*inv[MOD%i]%MOD;
finv[i] = finv[i-1]*inv[i]%MOD;
}
}
ll binom(ll n, ll r){
if(n<r || n<0 || r<0) return 0;
return fac[n]*finv[r]%MOD*finv[n-r]%MOD;
}
//compression
void comp(vi &A){
std::map<ll,ll> memo;
rep(i,0,A.size()) memo[A[i]]=0;
ll cnt=0;
for(auto &p:memo) p.second=cnt++;
rep(i,0,A.size()) A[i]=memo[A[i]];
}
//decrease the value of map
void dec(std::map<ll,ll> &mem,ll X){
mem[X]--;
if(mem[X]==0) mem.erase(X);
}
//main
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::random_device rnd;
std::mt19937 mt(rnd());
ll N, A, B, L; cin >> N >> A >> B >> L;
vector<vii> dp(N+1, vii(N+1, vi(B+1)));
vi S(N);
rep(i,0,N) cin >> S[i];
dp[0][0][0] = 1;
rep(i,0,N){
REP(j,0,i){
ll sum = 0;
REP(k,0,B){
dp[i+1][j][k] += dp[i][j][k];
dp[i+1][j][k] %= MOD;
sum += dp[i][j][k];
if(S[i] < k) sum -= dp[i][j][k-S[i]-1];
sum %= MOD;
if(sum < 0) sum += MOD;
dp[i+1][j+1][k] += sum;
dp[i+1][j+1][k] %= MOD;
}
}
}
ll ans = 0;
REP(i,0,N){
ll a = A-L*i+B;
if(a < 0) continue;
vii dp2(N+1, vi(a+1));
dp2[0][0] = 1;
REP(j,1,N){
vi sum = dp2[j-1];
REP(k,1,a) sum[k] = (sum[k]+sum[k-1])%MOD;
REP(k,0,a){
if(j <= i){
//L 個以上取らなければ
dp2[j][k] = sum[k];
}
else{
//L 個未満でなければ
dp2[j][k] = sum[k];
if(L <= k) dp2[j][k] -= sum[k-L];
dp2[j][k] %= MOD;
if(dp2[j][k] < 0) dp2[j][k] += MOD;
}
}
}
REP(j,0,B){
if(0 <= A-L*i+j) ans += dp[N][i][j]*dp2[N][A-L*i+j];
ans %= MOD;
}
}
cout << ans << ln;
}