杭州网站建设乐云seo模板中心,易企秀h5制作教程,编程网站免费中文版,济南seo优化外包cf1553F. Pairwise Modulo
题意#xff1a;
给你一个数组a#xff0c;a由n个不同的数组成,让你求出对应的数组p 数组p的定义为#xff1a; pk∑1≤i,j≤kaimodajp_{k}\sum_{1\leq i,j\leq k}a_{i} \mod a_{j}pk∑1≤i,j≤kaimodaj
题解#xff1a;
官方题解 首…cf1553F. Pairwise Modulo
题意
给你一个数组aa由n个不同的数组成,让你求出对应的数组p 数组p的定义为 pk∑1≤i,j≤kaimodajp_{k}\sum_{1\leq i,j\leq k}a_{i} \mod a_{j}pk∑1≤i,j≤kaimodaj
题解
官方题解 首先我们需要拜托mod操作一个常用公式 xmodyx−y∗⌊xy⌋x \mod y x - y * \lfloor \frac{x}{y} \rfloorxmodyx−y∗⌊yx⌋ 直接求p比较麻烦我们规定ij一个先后顺序我们将pkp_{k}pk分成sks_{k}sk和tkt_{k}tk两个部分 sk∑1≤i,j≤k,ijaimodajs_{k}\sum_{1\leq i,j\leq k,ij}a_{i} \mod a_{j}sk∑1≤i,j≤k,ijaimodaj tk∑1≤i,j≤k,ijaimodajt_{k}\sum_{1\leq i,j\leq k,ij}a_{i} \mod a_{j}tk∑1≤i,j≤k,ijaimodaj 也就是sks_{k}sk求的是编号大的数mod编号小的数的和tkt_{k}tk则正好相反。 怎么求sks_{k}sk? sksk−1∑i1k−1akmodaisk−1∑i1k−1(ak−ai∗⌊akai⌋)s_{k}s_{k-1}\sum_{i1}^{k-1}a_{k} \mod a_{i}s_{k-1}\sum_{i1}^{k-1}(a_{k}-a_{i}*\lfloor\frac{a_{k}}{a_{i}} \rfloor)sksk−1∑i1k−1akmodaisk−1∑i1k−1(ak−ai∗⌊aiak⌋) 我们将aka_{k}ak提出来会得到 sksk−1ak∗(k−1)−∑i1k−1(ai∗⌊akai⌋)s_{k}s_{k-1}a_{k}*(k-1)-\sum_{i1}^{k-1}(a_{i}*\lfloor \frac{a_{k}}{a_{i}} \rfloor)sksk−1ak∗(k−1)−∑i1k−1(ai∗⌊aiak⌋) 现在问题就是∑i1k−1(ai∗⌊akai⌋)\sum_{i1}^{k-1}(a_{i}*\lfloor \frac{a_{k}}{a_{i}} \rfloor)∑i1k−1(ai∗⌊aiak⌋)咋求 我们现在开始确定aia_{i}ai,然后看其对所有sks_{k}sk,ki的贡献
对于所有的aka_{k}ak在[ai,2∗ai)[a_{i},2*a_{i})[ai,2∗ai)贡献是−ai-a_{i}−ai对于所有的aka_{k}ak在[2∗ai,3∗ai)[2*a_{i},3*a_{i})[2∗ai,3∗ai)贡献是−2∗ai-2*a_{i}−2∗ai…对于所有的aka_{k}ak在[d∗ai,(d1)∗ai)[d*a_{i},(d1)*a_{i})[d∗ai,(d1)∗ai)贡献是−d∗ai-d*a_{i}−d∗ai
这意味着可以强制所有合法的d并执行类似这样的更新将x添加到范围[l,r]中的所有数字。这可以用线段树或树状数组 tkt_{k}tk的求法也超不多但是有区别
时间复杂度 M最大是3e5,每一次加一数进去会进行Mai\frac{M}{a_{i}}aiM次修改而aia_{i}ai各不相同所以M1...MnO(logn)\frac{M}{1}...\frac{M}{n}O(logn)1M...nMO(logn) 所以有O(M logn)更新操作每次更新是O(log M)总复杂度为O(M log M log n) 代码中我维护了两个树状数组A和B
代码
// Problem: F. Pairwise Modulo
// Contest: Codeforces - Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 Div. 2)
// URL: https://codeforces.com/contest/1553/problem/F
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// Data:2021-08-10 16:23:05#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
template typename T inline void read(T x)
{T f 1;x 0;char ch getchar();while (0 isdigit(ch)) {if (ch -)f -1;ch getchar();}while (0 ! isdigit(ch))x (x 1) (x 3) ch - 0, ch getchar();x* f;
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 3e5 9;
const int M 3e5;
struct Fenw
{ll w[maxn];Fenw(){fill(w 1, w maxn, 0ll);}ll lowbit(ll x){return x (-x);}void update(int pos, ll x){for (; pos M; pos lowbit(pos)) {w[pos] x;}}ll get(int pos){ll res 0;for (; pos 0; pos- lowbit(pos)) {res w[pos];}return res;}ll get(int l, int r){return get(r) - get(l - 1);}
} A, B;
void solve()
{int n;cin n;//A维护的是ak对[k1,n]B维护的是区间[1,k-1]对ak的贡献ll pre 0, ans 0;//debug(测试, 1);for (int i 1; i n; i) {int x;cin x;ans x * (i - 1ll); //加的skans- A.get(x); //s_2ans pre; //加的tkpre x;//debug(测试, 1);for (int j x; j M; j x) {int l j, r min(M, j x - 1); //枚举每个区间ans- B.get(l, r) * j; //t_2A.update(l, x);//在l位置上加x}B.update(x, 1);printf(%lld , ans);}printf(\n);
}
int main()
{//rd_test();solve();return 0;//Time_test();
}
