思路是对每一个连续段进行矩快转移，dp_i 记录到 i 时的方案数，方案数不为 0 即为可以到达。

是假了还是写挂了啊/ll

AC54,WA3,TLE*14

#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
struct mat{
	ull a[25][25];
	mat(){memset(a,0,sizeof(a));}
	mat operator*(const mat &x)const{
		mat res;
		for(int i=0;i<=20;i++)
		{
			for(int k=0;k<=20;k++)
			{
				ull l=a[i][k];
				for(int j=0;j<=20;j++)
				{
					res.a[i][j]=(res.a[i][j]+l*x.a[k][j]);
				}
			}
		}
		return res;
	}
}s,dp1,dp2;
mat qpow(mat x,ll k)
{
	mat res;
	for(int i=0;i<=20;i++)res.a[i][i]=1;
	while(k>0)
	{
		if(k&1)res=res*x;
		x=x*x;
		k>>=1;
	}
	return res;
}
ll n,m,a,b,l[200005],r[200005];

int main()
{
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>a>>b;
    s.a[1][20]=1;
    for(int i=1;i<=20;i++)dp1.a[i+1][i]=dp2.a[i+1][i]=1;
    for(int i=20-a+1;i>=20-b+1;i--)dp1.a[i][20]=1;
    r[0]=1;
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
        if(r[i]-l[i]+1>=21||l[i]==1)
        {
            cout<<"No";
            return 0;
        }
        if(l[i]-r[i-1]-1>0)s=s*qpow(dp1,l[i]-r[i-1]-1);
        if(r[i]-l[i]+1>0)s=s*qpow(dp2,r[i]-l[i]+1);
    }
    if(n+1-r[m]-1>0)s=s*qpow(dp1,n+1-r[m]-1);
    if(s.a[1][20])cout<<"Yes";
    else cout<<"No";
    return 0;
}