$23333$这是一道$zz$的分配律的题……思路其余的大佬都讲的差不多了,那么我们直接进入优化阶段。
我的代码不开$O2$在第十页,开了$O2$在第二页,算是一个比较优的复杂度了$233$……
那么窝萌考虑这个题,其实就是对$K$操作,然后,因为我们只需要统计$K$个约束的信息即可。我们可以离线下来,排个序,去个重(即将重复的置为$Inf$),然后再排一遍序,从后往前删除重复的,最后扫一遍剩下的合法约束即可。
在这里我一开始建了个桶存储信息,但是很显然空间不允许。所以便换了种写法,也是个小技巧吧。
上代码
```cpp
#include <cstdio>
#include <bitset>
#include <iostream>
#include <algorithm>
#define ll long long
#define MAXN 1000010
#define mod 1000000007
using namespace std ;
struct node{
ll L, R ;
}In[MAXN] ; ll S[MAXN], J, Last ;
ll L, R, Ans, N, M, K, i, T, base ;
inline ll qr(){
ll k = 0 ; char c = getchar() ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ;
return k ;
}
inline ll expow(ll A, ll B){
ll res = 1 ;
while (B){
if (B & 1) {
res = res * A ;
if (res > mod) res %= mod ;
}
A = A * A ; if (A > mod) A %= mod ;
B >>= 1 ;
}
return res % mod ;
}
inline bool compare(node A, node B){
if(A.L == B.L) return A.R < B.R ;
return A.L < B.L ;
}
int main(){
N = qr(), M = qr(), K = qr() ;
T = M, base = (1 + N) * N >> 1 ; base %= mod ;
for (i = 1; i <= K ; ++ i) In[i].L = qr(), In[i].R = qr() ;
sort (In + 1, In + K + 1, compare) ;
for (i = 2; i <= K ; ++ i)
if (In[i].R == In[i - 1].R && In[i].L == In[i - 1].L ) In[i - 1].L = 19260817000LL ;
sort (In + 1, In + K + 1, compare) ;
for (i = K; In[i].L == 19260817000LL ; -- i) K -- ;
for (i = 1; i <= K ; ++ i) {
L = In[i].L, R = In[i].R ;
if (L != Last) T --, Last = L, ++ J ; S[J] -= R ;
}//此处是用来存储约束的
Ans = (Ans + expow(base, T)) % mod ;
for (i = 1; i <= J ; ++ i){
Ans = Ans * (base + S[i]) % mod ;
if (Ans > mod) Ans %= mod ;
}
cout << ( Ans + mod ) % mod << endl ;
}
//这个版本是88ms……因为窝限制模运算结果反而更慢了……
```