奇怪方法求优化（违规紫衫）
查看原帖
奇怪方法求优化（违规紫衫）
892979
liuenyin楼主2023/10/10 20:01

rt, 大概是这样的，：

将原式拆开，得到（如 n=3n=3 ）

原式&=S(1,1)+S(1,2)+S(1,3)+S(2,2)+S(2,3)+S(3,3) \\ &=a1b1+(a1+a2)(b1+b2)+(a1+a2+a3)(b1+b2+b3)+...+a3b3 \\ &=a1b1+a1b1+a1b2+a2b1+a2b2+a1b1+a1b2+a1b3+a2b1+a2b2+a2b3+a3b1+a3b2+a3b3+a2b2+a2b2+a2b3+a3b2+a3b3+a3b3\\ &=3a1b1+2a1b2+1a1b3+2a2b1+4a2b2+2a2b3+1a3b1+2a3b2+3a3b3 \end{aligned}$$ 整理系数可得 $\begin{bmatrix} 3&2&1 \\ 2&4&2 \\1&2&3\end{bmatrix}$ 同理，得到 $n=5$ 时的系数矩阵 $\begin{bmatrix} 5&4&3 &2 &1\\ 4& 8 &6& 4 &2 \\ 3& 6 &9& 6& 3 \\ 2& 4& 6 &8 &4\\ 1& 2 &3 &4& 5\\ \end{bmatrix} $ 于是写出了 $O(n^2)$ 的代码，70pts，求优化（或者说这样子解不了）： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3005; const int M=1e9+7; int sx[N][N];//系数 int a[N],b[N]; int n; signed main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>b[i]; for(int i=1;i<=n;i++){ int num=n-i+1; for(int j=1;j<=i;j++){ sx[i][j]=num*j; //cerr<<sx[i][j]<<" "; } } ll ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ if(i!=j)ans+=(((1ll*a[i]*b[j])+(1ll*a[j]*b[i]))%M*sx[i][j])%M; else ans+=(1ll*a[i]*b[i]*sx[i][i])%M; ans%=M; } } cout<<ans; return 0; } ```
2023/10/10 20:01