Project Euler 593

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

Project Euler 593

题目

Fleeting Medians

We define two sequences \(S = \{S(1), S(2), \dots, S(n)\}\) and \(S_2 = \{S_2(1), S_2(2), \dots, S_2(n)\}\):

\(S(k) = (p_k)^k \bmod 10007\) where \(p_k\) is the \(k\text{th}\) prime number.

\(S_2(k) = S(k) + S\left(\left\lfloor\dfrac{k}{10000}\right\rfloor + 1\right)\) where \(\lfloor \cdot \rfloor\) denotes the floor function.

Then let \(M(i, j)\) be the median of elements \(S_2(i)\) through \(S_2(j)\), inclusive. For example, \(M(1, 10) = 2021.5\) and \(M(10^2, 10^3) = 4715.0\).

Let \(F(n, k) = \sum_{i=1}^{n-k+1} M(i, i + k - 1)\). For example, \(F(100, 10) = 463628.5\) and \(F(10^5, 10^4) = 675348207.5\).

Find \(F(10^7, 10^5)\). If the sum is not an integer, use \(.5\) to denote a half. Otherwise, use \(.0\) instead.

解决方案

令\(N=10^7,M=10007,K=10^5\)。

计算出序列\(S_2\)后，那么问题只剩下计算出\(M(i,i+K-1)\)的值。由于\(K\)是偶数，因此我们需要计算出\(S_2\)的子数组\(S_2[i:i+K-1]\)中第\(\dfrac{K}{2},\dfrac{K}{2}+1\)大的值再将它们求平均值即可。这里将提供两种办法解决这个问题。

第一种办法则是使用树状数组。树状数组的意义在于计算维护\(s[i]\)的值：小于等于\(i\)的数一共有多少个，它可以做到以\(O(\log M)\)的时间复杂度维护好每一个长度为\(K\)的区间的数的数量。然后对树状数组进行二分，从而找到第\(\dfrac{K}{2},\dfrac{K}{2}+1\)大的值。单次计算操作需要\(O(\log^2 M)\)的时间复杂度。

第二种做法则是暴力维护两个多重集合sl, sr。sl用来存比较小的\(\dfrac{K}{2}\)个数，sr用来存比较大的\(\dfrac{K}{2}\)个数。最终sl的最大值和sr的最小值共同构成了这个最终中位数的值。单次操作的时间复杂度为\(O(\log k)\)。

然而，由于multiset本身操作的开销比较大。经过实验，虽然第一种做法的单次理论开销比较大，但是实践中它却远快于第二种做法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
# define lb(i) ((i) & -(i))
# include "tools.h"
using namespace std;
typedef long long ll;

const int N=1e7,K=1e5;
const int M=10007;

int s[N+4],s2[N+4];
int t[M+M];
void add(int p,int f){
    for(int i=p;i<M+M;i+=lb(i)) t[i]+=f;
}
int que(int p){
    int a=0;
    for(int i=p;i;i-=lb(i)) a+=t[i];
    return a;
}
int que_rank(int k){
    int l=1,r=M+M-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(que(mid)>=k) r=mid;
        else l=mid+1;
    }
    return l;
}
int main(){
    vector<int>pr=get_prime_by_counts(N);
    for(int i=1;i<=N;i++)
        s[i]=qpow(pr[i-1],i%(M-1),M);
    for(int i=1;i<=N;i++)
        s2[i]=s[i]+s[i/10000+1];
    for(int i=1;i<K;i++)
        add(s2[i],1);
    ll sum=0;
    for(int i=K;i<=N;i++){
        add(s2[i],1);
        sum+=que_rank((K+1)>>1);
        if(!(K&1)) sum+=que_rank((K>>1)+1);
        add(s2[i-K+1],-1);
    }
    double ans=K&1?sum:0.5*sum;
    printf("%.1f\n",ans);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# include <bits/stdc++.h>
# include "tools.h"
using namespace std;
typedef long long ll;

const int N=1e7,K=1e5;
const int M=10007;

int s[N+4],s2[N+4];
multiset<int>l,r;
void balance(){
    while(l.size()<r.size()){
        l.insert(*r.begin());r.erase(r.begin());
    }
    while(l.size()>r.size()+1){
        r.insert(*l.rbegin());
        auto it=l.end();
        l.erase(--it);
    }
}
void add(int x,int f){
    if(f==1){
        if(l.empty()||x<=*l.rbegin()) l.insert(x);
        else r.insert(x);
    }
    else{
        auto it=l.find(x);
        if(it!=l.end()) l.erase(it);
        else r.erase(r.find(x));
    }
    balance();
}
int main(){
    vector<int>pr=get_prime_by_counts(N);
    for(int i=1;i<=N;i++)
        s[i]=qpow(pr[i-1],i%(M-1),M);
    for(int i=1;i<=N;i++)
        s2[i]=s[i]+s[i/10000+1];
    for(int i=1;i<K;i++)
        l.insert(s2[i]);
    balance();
    ll sum=0;
    for(int i=K;i<=N;i++){
        add(s2[i],1);
        sum+=*l.rbegin();
        if(!(K&1)) sum+=*r.begin();
        add(s2[i-K+1],-1);
    }
    double ans=K&1?sum:0.5*sum;
    printf("%.1f\n",ans);

}