权威的网站建设排行榜,图片类网站模板,义乌 外贸网站 开发,网站怎么做全屏的来源#xff1a;牛客网#xff1a;
区间权值
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 1048576K#xff0c;其他语言2097152K
64bit IO Format: %lld题目描述
输入描述: 第一行一个正整数 n 第二行 n 个正整数 a1…an 第三行 n 个正…来源牛客网
区间权值
时间限制C/C 1秒其他语言2秒
空间限制C/C 1048576K其他语言2097152K
64bit IO Format: %lld题目描述
输入描述: 第一行一个正整数 n 第二行 n 个正整数 a1…an 第三行 n 个正整数 w1…wn 输出描述: 输出答案对 1097 取模后的值 示例1 输入
复制
3
1 1 1
1 1 1输出 复制
10备注: 1≤ n≤ 3x 105 1≤ ai≤ 107 1≤ wi≤ 107 题解
吐槽一下官方题解有点小错误应该是打错了。。。 题目是求公式我们将式子化简 for(l 1–n) for(r l --n) f(l,r) f(1,1)f(1,2)…f(1,n) f(2,2)f(2,3)…f(2,n) … f(n,n) 我们再拆一下 a1w1(a1w2a2w2)(a1a2a3)w3.(a1a2…an)wn a2w1(a2a3)w2…(a2a3…an)w(n-1) … 是不是感觉有点规律了 我们用sum[]来求前缀和这样括号里面都可以用sum来表示 然后我们将所有w1合并将所有w2合并能得到 (sum[1]-sum[0]sum[2]-sum[1]sum[3]…sum[n]-sum[n-1])w1(sum[n]-sum[0])w1 w2也合并(sum[n]sum[n-1]-sum[1]-sum[0])w2(sum[n]-sum[0])sum[n-1]-sum[1] … wi的系数就是sum[n-i1]-sum[i-1]wi-1的系数
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn3e59;
const int mod1e97;
ll w[300004],sum[maxn],a[maxn];
int main()
{int n;cinn;for(int i1;in;i){cina[i];sum[i](sum[i-1]a[i])%mod;}for(int i1;in;i)cinw[i];ll ans0;ll tot0;for(int i1;in;i){tot(tot(sum[n-i1]-sum[i-1]mod)%mod)%mod;ans(anstot*w[i]%mod)%mod;}coutans;}
