专栏文章

题解：CF2037G Natlan Exploring

zzhouruoheng
CF2037G题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mir31r87
此快照首次捕获于
2025/12/04 14:56
3 个月前
此快照最后确认于
2025/12/04 14:56
3 个月前
查看原文
dp 加容斥。
逐步推导，设 fif_i 为从 11 到 ii 的方案数，按题意模拟就有：
f1=1 f_1=1 fi=fi+fj(1≤j<i,gcd⁡(ai,aj)≠1) f_i=f_i+f_j (1 \le j < i,\gcd(a_i,a_j)\neq 1)
这样做是 O(n2)O(n^2) 的。
CPP
#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⁡(ai,aj)\gcd(a_i,a_j) 是啥，只要求不为 11，将 aia_i 质因数分解，aia_i 与 aja_j 是通过相同的质因数产生联系的。每次分解 aia_i，找前面的位置进行转移。
CPP
#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(n2)O(n^2) 的，随便就能卡掉。
然后不妨按质因数划分集合，设 bxb_x 为质因数为 xx 的数产生的贡献。这样每次 aia_i 分解出 xx fif_i 只需要加上 bxb_x 就行了。但是仅仅如此的话连样例都过不了。
考虑这样一组数据 12,12\mathtt{12,12}。i=1i=1，f1=1f_1=1，更新 bb，有 b2=1,b3=1b_2=1,b_3=1。i=2i=2，f2=b2+b3=2f_2=b_2+b_3=2，但实际上是 f2=1f_2=1。
这里就是 22 和 33 重复算了，因为这里显然还要减去 66 出现的次数 11。可知，当一个数有两个及以上的质因数时，会出现重复计算的情况。
如何避免这样情况呢？用容斥原理。
将 aia_i 质因数分解后，每个质因数只取一次相乘得到 yy，取 yy 的所有约数放在动态数组 g[a[i]] 中。比如 g[12]={2,3,6}，这时候可以计算上面例子，i=1i=1，有 b2=b3=b6=1b_2=b_3=b_6=1，i=2i=2，有 f2=b2+b3−b6=1f_2=b_2+b_3-b_6=1。
也就是说在每次更新 fif_i 时对于 g[a[i]] 中的每个元素 xx，如果 xx 的质因数个数为奇数，说明要加上贡献，否则减去贡献。同样 bxb_x 的更新也需要取 g[a[i]] 中的每个元素 xx。
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...