考虑每个点的贡献。因为题目说 和 算一组，所以我们不妨令 。然后我们发现点 对后面节点的贡献为一个 首相为1 公差为1 的等差数列。于是我们便可以愉快地二阶差分了，最后遍历每个1答案加上其位置上的权值即可。 my code: #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5 + 10,mod = 1e9 + 7; int n; ll ans; ll sum[maxn]; char a[maxn]; int main(){ scanf(&quot...

我们可以用一个数组 记录下前 次操作后第 杯子里球的颜色，也可用一个 vector 存储。那么每个询问 到 后的结果，我们可以对于每一个 找到对应的 ，这里的对应指杯子里球的颜色相等，并将 。 那么为什么呢？ 原因如下： 如果 那么就说明如果颜色 在第 号杯子里，那么无论如何经过 的操作后 都会出现在第 个杯子里。因为我们是从 操作开始的所以 。 my code(有点写麻烦了，但不想改了): #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n,m; ...

直接上结论，对 数组差分以后所有正数或所有负数的绝对值即为答案。 my code: #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n,ans; int a[maxn]; int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); if(a[i] > a[i - 1]) an...

考虑前缀积。令 表示 ，则 可表示为 ，预处理出数组，查询的时候套上一个乘法逆元即可。 下面是关于乘法逆元，我们可以利用费马小定理 如果 是质数，且 即 互质，则 所以可推出 。又因为 对比两个式子即可得出在模 意义下 和 同余。 my code: #include <bits/stdc++.h> #define ll long long using namespace std; const int mod = 1e9 + 7,maxn = 1e5 + 10; int n,m; ll a[maxn]; ll q_pow(ll x,ll y){ ...