A simple Blog for wyx I've been down the bottle hoping.
4921: 互质序列 枚举
发表于: | 分类: Oi | 评论:0 | 阅读:87

注意题中说的是取出一个子串

我去年买了个表我想了十分钟动态规划最后发现是连续子序列

那就非常套路了,考虑维护前缀gcd $pre$ 和 后缀gcd $last$

$pre$和$last$显然都只有$\log(n)$个取值直接暴力

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 998244353;
const int N = 1e5+5;
int a[N], pre[N], last[N];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int L[N];

int main() {
    int n = read();
    for(int i=1;i<=n;++i) a[i] = read();    
    pre[1] = a[1];
    for(int i=2;i<=n;++i) pre[i] = __gcd(pre[i-1], a[i]);
    for(int i=2;i<=n;++i) {
        if(pre[i] == pre[i-1]) L[i] = L[i-1];
        else L[i] = i - 1;
    }
    L[0] = -1;
    int ans = 0, now = 0;
    for(int i=n;i>=2;--i) {
        now = __gcd(now, a[i]);
        for(int j=i-2;~j;j=L[j]) {
            ans = (ans + (LL)(j-L[j])*(__gcd(now, pre[j]) %mod)) % mod;
        }
        if(i == n) ans = (ans - now + mod) % mod;
    }
    for(int i=2;i<n;++i) ans = (ans + pre[i]) % mod;
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP