ModuloNine

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains two integers n and m.

The ith of the following m lines contains two integers $l_i$ and $r_i$ .

* $1 \leq n, m \leq 10^3$
* $1 \leq l_i \leq r_i \leq n$
* There are at most 100 test cases.

C++(clang++11) 解法, 执行用时: 316ms, 内存消耗: 7672K, 提交时间: 2021-01-14 18:15:18

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1020,mod=1e9+7,i6=166666668;
int n,m;
ll f[maxn][maxn];
int mxl[maxn];

void solve(){
    for(int lf=0;~scanf("%d%d",&n,&m);){
        for(int i=0;i<=n;mxl[i]=0,++i)
            for(int j=0;j<=i;++j)
                f[i][j]=0;
        for(int i=1,x,y;i<=m;++i){
            scanf("%d%d",&x,&y);
            mxl[y]=max(mxl[y],x);
        }
        f[0][0]=1;lf=0;
        ll in6=i6,_3=1ll;
        for(int i=1;i<=n;++i,_3=_3*6%mod,in6=in6*i6%mod){
            for(int j=0;j<i;++j){
                f[i][j]=f[j][lf]*_3*2%mod;
                (f[i][i]+=f[i][j])%=mod;
            }
            for(int j=i;j>lf;--j)(f[i][j-1]+=f[i][j])%=mod;
            for(int j=lf;j<=i;++j)f[i][j]=f[i][j]*in6%mod;
            lf=max(lf,mxl[i]);
        }
        ll ans=0;
        for(int i=lf;i<=n;++i)(ans+=f[i][lf])%=mod;
        ans=ans*_3%mod;
        printf("%lld\n",ans);
    }
}
int main(){
    solve();

    return 0;
}

详情