Codeforces Round #323 (Div. 2) E - Superior Periodic Subarrays

E - Superior Periodic Subarrays

好难的一题啊。。。

这个博客讲的很好，搬运一下。

https://blog.csdn.net/thy_asdf/article/details/49406133

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int,int>

#define piii pair<int, pair<int,int> >

using namespace std;

const int N = 2e5 + ;

const int M =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int gcd(int a, int b) {

    return !b ? a : gcd(b, a % b);

}

int n, mx, a[N << ], cnt[N << ], f[N << ];

bool flag[N << ];

int main() {

    scanf("%d", &n);

    for(int i = ; i < n; i++) {

        scanf("%d", &a[i]);

        a[i + n] = a[i];

    }

    LL ans = ;

    for(int d = ; d < n; d++) { //枚举GCD(n,s)

        if(n % d) continue;

        memset(flag, false, sizeof(flag));

        for(int k = ; k < d; k++) { //枚举起点

            mx = ;

            for(int i = k; i <  * n; i += d) mx = max(mx, a[i]); //找出这些相隔为d的数之间最大的数

            for(int i = k; i <  * n; i += d) flag[i] = (a[i] == mx);//判断这个数是不是一系列数的最大值

        }

        f[] = flag[];  //以i结尾的"卓越子序列"最长可能长度

        for(int i = ; i <  * n; i++) {

            if(flag[i]) f[i] = f[i - ] + ;

            else f[i] = ;

            f[i] = min(f[i],  n - );

        }

        cnt[] = ; //1-i中有多少个数与n的gcd为枚举的d

        for(int i = ; i < n / d; i++) cnt[i] = cnt[i - ] + (gcd(i, n / d) == );

        //要把Gcd(s,n)==d化简成gcd(s/d,n/d)==1，不然会被卡

        for(int i = n; i < n * ; i++) ans += cnt[f[i] / d];

    }

    printf("%lld\n", ans);

    return ;

}

/*

*/