首先离散化一下，然后令f[i][j][k]表示做到第i个学校，最后一个数落在j号区间，这个区间里有k个不同的数的方案数。（实际上如果两个学校的数量是一样的，那么对后面的方案是没有影响的，所以记录的是k个不一样的数）。 sum[t]=∑f[i-1][j][p] (1<=j<=t) f[i][j][k]=f[i-1][j][k]+f[i-1][j][k-1]*(len[j]-k+1)/k f[i][j][1]=f[i-1][j][1]+sum[j-1]*len[j] sum数组可以提前累加预处理出，注意预处理一下逆元即可。 还有就是注意sum的初始化！
#include<cmath> #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mo 1000000007 #define N 1010 #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; struct section{int l,r;} q[N],seq[N]; int a[N],dp[N][N],f[N][N],sum[N],len[N],inv[N]; int n,i,j,k,num,tot,res; int qry_l(int x) { int l = 1,r = num,res; while (l <= r) { int mid = (l + r) >> 1; if (x <= seq[mid].l) res = mid,r = mid - 1; else l = mid + 1; } return res; } int qry_r(int x) { int l = 1,r = num,res; while (l <= r) { int mid = (l + r) >> 1; if (seq[mid].r < x) res = mid,l = mid + 1; else r = mid - 1; } return res; } int q_p(int x,int a) {int res=1;while(a){if(a&1)res=(1ll*res*x)%mo;x=(1ll*x*x)%mo;a>>=1;}return res;} int main() { fo(i,1,1000) inv[i] = q_p(i,mo-2); scanf("%d",&n); fo(i,1,n) {scanf("%d%d",&q[i].l,&q[i].r); q[i].r++; a[++tot] = q[i].l; a[++tot] = q[i].r;} sort(a+1,a+tot+1); fo(i,1,tot-1) if (a[i]!=a[i+1]) { num++; seq[num].l = a[i]; seq[num].r = a[i+1]-1; len[num] = a[i+1]-a[i]; } fo(i,1,n) q[i].l = qry_l(q[i].l) , q[i].r = qry_r(q[i].r); fo(i,1,n) { fo(j,1,num) dp[i][j] = dp[i-1][j]; fo(j,q[i].l,q[i].r) dp[i][j]++; } fo(i,0,num) sum[i] = 1; fo(i,1,n) { fo(j,q[i].l,q[i].r) { fd(k,dp[i][j],2) f[j][k] = (f[j][k] + (1ll*f[j][k-1]*(len[j]-k+1)%mo)*inv[k]%mo)%mo; f[j][1] = (f[j][1] + 1ll*sum[j-1]*len[j]%mo)%mo; } sum[0] = 1; fo(j,1,num) { sum[j] = sum[j-1]; fo(k,1,dp[i][j]) sum[j] = (sum[j] + f[j][k]) % mo; } } printf("%d\n",sum[num]-1); return 0; }