大水題一個，然而由于兩顆線段樹的陰影我死了……

算法一：對于50%的數據：?送分，直接一個一個乘，時間復雜度O(KN)。

算法二：對于80%的數據：如果我們不一個一個乘，將第i行的和乘x ,第j列的和乘y ,所計算出的結果與正解不同的地方僅僅是（i,j）這一個元素。而這樣的數不足K²個。所以我們把這些元素單獨計算一遍就可以了，時間復雜度O（K²）。

算法三：對于100%的數據：設h[i]為第i行總共乘的數,l[j]表示第j列總共乘的數，根據題意map[i][j]=(i-1)*m+j,顯然最后$ans=\sum\limits_{i=1}^{n} \sum \limits_{j=1}^{m} h[i]*l[j]*((i-1)*m+j)$,這樣復雜度是O（nm）的，再把求和拆一下，ans=$\sum\limits_{i=1}^{n}$ h[i]*(∑l[j]*j)+$\sum\limits_{j=1}^{m}$ l[j]*(∑h[i]*(i-1)*m)這樣復雜度就是O（m+n）的了。

1 #include<iostream> 2 #include<cstdio> 3 #define LL long long 4 #define MAXN 1000010 5 #define mod 1000000007 6 using namespace std; 7 LL h[MAXN],l[MAXN]; 8 int n,m,k; 9 char op;int x,y; 10 LL lj_j[MAXN],hi_i[MAXN]; 11 signed main() 12 { 13 cin>>n>>m>>k; 14 for(int j=1;j<=m;j++)l[j]=1; 15 for(int i=1;i<=n;i++)h[i]=1; 16 for(int i=1;i<=k;i++) 17 { 18 cin>>op>>x>>y; 19 if(op=='R')h[x]=h[x]*y%mod; 20 else l[x]=l[x]*y%mod; 21 } 22 LL sumj=0,sumi=0; 23 for(int j=1;j<=m;j++)lj_j[j]=l[j]*j%mod,sumj=(sumj+lj_j[j])%mod; 24 for(int i=1;i<=n;i++)hi_i[i]=h[i]*(i-1)%mod*m%mod,sumi=(sumi+hi_i[i])%mod; 25 LL ans=0; 26 for(int i=1;i<=n;i++)ans=(ans+h[i]*sumj)%mod; 27 for(int j=1;j<=m;j++)ans=(ans+l[j]*sumi)%mod; 28 printf("%lld\n",ans); 29 } View Code

?

轉載于:https://www.cnblogs.com/Al-Ca/p/11306655.html

總結

以上是生活随笔為你收集整理的HZOJ 矩阵游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。