题解：CF2037G Natlan Exploring

dp 加容斥。

逐步推导，设 f_i 为从 1 到 i 的方案数，按题意模拟就有：

这样做是 O(n^2) 的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353,M=1e6+5;
int n;
int a[N];
int f[N];
int gcd(int x,int y)
{
    return y ? gcd(y,x%y) : x;
}
vector<int> g[M],h[N];
set<int> v;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i-1;j++) 
            if(gcd(a[i],a[j])!=1) 
                f[i]=(f[i]+f[j])%mod;
    cout<<f[n]<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

考虑优化，不难发现我们其实并不在意具体的 \gcd(a_i,a_j) 是啥，只要求不为 1，将 a_i 质因数分解，a_i 与 a_j 是通过相同的质因数产生联系的。每次分解 a_i，找前面的位置进行转移。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353,M=1e6+5;
int n;
int a[N],f[N];
vector<int> g[M],h[N];
set<int> v;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int x=a[1];
    for(int j=2;1ll*j*j<=n;j++)
    {
        if(x%j==0) 
        {
            g[j].push_back(1);
            while(x%j==0) x/=j;
        }
    }
    if(x>1) g[x].push_back(1);
    f[1]=1;
    for(int i=2;i<=n;i++)
    {
        int x=a[i];
        for(int j=2;1ll*j*j<=x;j++)
        {
            if(x%j==0) 
            {
                for(int k:g[j]) 
                {
                    if(v.count(k)==0) f[i]=(f[i]+f[k])%mod;
                    v.insert(k);
                }
                g[j].push_back(i);
                while(x%j==0) x/=j;
            }
        }
        if(x>1) 
        {
            for(int k:g[x]) 
            {
                if(v.count(k)==0) f[i]=(f[i]+f[k])%mod;
                v.insert(k);
            }
            g[x].push_back(i);
        }
        v.clear();
    }
    cout<<f[n]<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

但这样还是过不了。因为这最坏还是 O(n^2) 的，随便就能卡掉。

然后不妨按质因数划分集合，设 b_x 为质因数为 x 的数产生的贡献。这样每次 a_i 分解出 x f_i 只需要加上 b_x 就行了。但是仅仅如此的话连样例都过不了。

考虑这样一组数据 \mathtt{12,12}。i=1，f_1=1，更新 b，有 b_2=1,b_3=1。i=2，f_2=b_2+b_3=2，但实际上是 f_2=1。

这里就是 2 和 3 重复算了，因为这里显然还要减去 6 出现的次数 1。可知，当一个数有两个及以上的质因数时，会出现重复计算的情况。

如何避免这样情况呢？用容斥原理。

将 a_i 质因数分解后，每个质因数只取一次相乘得到 y，取 y 的所有约数放在动态数组 g[a[i]] 中。比如 g[12]={2,3,6}，这时候可以计算上面例子，i=1，有 b_2=b_3=b_6=1，i=2，有 f_2=b_2+b_3-b_6=1。

也就是说在每次更新 f_i 时对于 g[a[i]] 中的每个元素 x，如果 x 的质因数个数为奇数，说明要加上贡献，否则减去贡献。同样 b_x 的更新也需要取 g[a[i]] 中的每个元素 x。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5,M=1e6+5,mod=998244353;
int n;
int a[N],b[M],f[N];
vector<int> g[M],h[M];
void divide1(int x,int id)
{
    for(int i=2;1ll*i*i<=x;i++)
    {
        if(x%i==0) 
        {
            h[id].push_back(i);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) h[id].push_back(x);
}
void divide2(int x,int id)
{
    x=1;
    for(auto t:h[id]) x*=t;
    for(int i=2;1ll*i*i<=x;i++)
    {
        if(x%i==0)
        {
            g[id].push_back(i);
            if(x!=i) g[id].push_back(x/i);
        }
    }
    if(x>1) g[id].push_back(x);
}
void solve()
{
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++) cin>>a[i],mx=max(mx,a[i]);
    for(int i=2;i<=mx;i++) divide1(i,i),divide2(i,i);
    f[1]=1;
    for(int i=1;i<=n;i++)
    {
        for(auto x:g[a[i]])
        {
            if(h[x].size()&1) f[i]=(f[i]+b[x])%mod;
            else f[i]=(f[i]+mod-b[x])%mod;
        }
        for(auto x:g[a[i]]) b[x]=(b[x]+f[i])%mod;
    }
    cout<<f[n]<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}