题解 P2220 【[HAOI2012]容易题】

皎月半洒花

2018-08-16 19:36:19

Solution

$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……因为窝限制模运算结果反而更慢了…… ```