原题链接：https://ac.nowcoder.com/acm/contest/1084/C

目录

• 题意
• 分析
• Code

题意

有n个数字，你可以仍意选择一些数字，这些数字可以取正也可以取负且数量无限，问有多少种取数的方法使得取到的这些数拼出所有数字。

分析

如果我们取两个数，那么要使得 a x + b y = 1 ax+by=1 ax+by=1，其中a，b为整数，其中 g c d ( x , y ) = 1 gcd(x,y)=1 gcd(x,y)=1

那么拓展一下，我们取m个数，使得 g c d ( a 1 , a 2.. a m ) = 1 gcd(a1,a2..am)=1 gcd(a1,a2..am)=1

这样可以用dp来解决，我们设出状态 f [ i ] [ j ] f[i][j] f[i][j]代表前i个数中使得gcd为j的方案数，那么只有两个种转移，一种是取当前数，一种是不取

1. 取当前数 f [ i ] [ g c d ( j , a [ i ] ) ] + = f [ i − 1 ] [ j ] f[i][gcd(j,a[i])]+=f[i-1][j] f[i][gcd(j,a[i])]+=f[i−1][j]
2. 不取当前数 f [ i ] [ j ] + = f [ i − 1 ] [ j ] f[i][j]+=f[i-1][j] f[i][j]+=f[i−1][j]

Code

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define re register
typedef long long ll;
typedef pair<ll, ll> PII;
typedef unsigned long long ull;
const int N = 5e5 + 10, M = 1e6 + 5, INF = 0x3f3f3f3f;
const int MOD = 998244353;
int a[3005];
int dp[3005][2005];
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        dp[i][a[i]] = 1;
        for (int j = 1; j <= 2000; j++) {
            dp[i][j] += dp[i-1][j];
            dp[i][j] %= MOD;
            dp[i][__gcd(j, a[i])] += dp[i-1][j];
            dp[i][__gcd(j, a[i])] %= MOD;
        }
    }
    cout << dp[n][1] << endl;
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    solve();
}