这题是一年前某场我参加过的Education Round codeforces的F题,当时我显然是不会的。
现在看看感觉应该是能做出的。
不扯了写题解:
考虑朴素的DP,在不存在障碍的情况下:f[i][0]=f[i-1][0]+f[i-1][1],f[i][1]=f[i-1][0]+f[i-1][1]+f[i-1][2],f[i][2]=f[i-1][1]+f[i-1][2]。
然后由于N范围不太大而M有1e18,一脸矩乘的样子。
没有障碍物显然可以构造如下矩阵:
0 1 1
1 1 1
1 1 0
然后直接快速幂就行了。
考虑某一行出现障碍物,实际上是将该列的矩阵的值全部变为0
然后可以把每一段离散化建立矩阵,分段矩阵乘法就行了
notice:注意若从前向后计算出每一段的最后矩阵t后,一定是ans=t*ans而不是ans=ans*t!!
时间复杂度:O(nlogn+27nlogM)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e4+7,mod=1e9+7; struct mat{ int a[3][3]; void clear(){memset(a,0,sizeof a);} void init(){clear();a[0][0]=a[1][1]=a[2][2]=1;} void zero(){init();a[0][1]=a[1][0]=a[1][2]=a[2][1]=1;} }; struct node{ll l,r;int a;}a[N]; int n,num; ll m,b[N<<1],c[3][N<<1],sc[3]; mat operator*(mat a,mat b) { mat c;c.clear(); for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%mod; return c; } mat qpow(mat a,ll b) { mat ret;ret.init(); while(b){if(b&1)ret=ret*a;a=a*a,b>>=1;} return ret; } int main() { scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%lld%lld",&a[i].a,&a[i].l,&a[i].r),a[i].a--; b[++num]=a[i].l-1,b[++num]=a[i].r; } b[++num]=1,b[++num]=m; sort(b+1,b+num+1),num=unique(b+1,b+num+1)-b-1; for(int i=1;i<=n;++i) { int L=lower_bound(b+1,b+num+1,a[i].l)-b,R=lower_bound(b+1,b+num+1,a[i].r)-b; c[a[i].a][L]++,c[a[i].a][R+1]--; } mat ans;ans.clear(); ans.a[1][0]=1; for(int i=2;i<=num;i++) { mat t;t.zero(); for(int j=0;j<3;j++) { sc[j]+=c[j][i]; if(sc[j])t.a[j][0]=t.a[j][1]=t.a[j][2]=0; } t=qpow(t,b[i]-b[i-1]); ans=t*ans; } printf("%d",ans.a[1][0]); }