代码源#960. 一个大整数（用DP实现组合计数）

题目：

​ 给出一个很大的整数x，以质因数分解的方式给出，请问有多少对x的因子是互质的。

分析：

​ 来枚举一下样例，可以发现12的因子有1,2,3,4,6,12。互质的因子对为(1, 1), (1, 2), (1, 3), (1, 4), (1, 6),(1, 12), (2, 1), (2, 3), (3, 1), (3, 2),(3, 4), (4, 1), (4, 3), (6, 1), (12, 1)，共15对。

​ 通过简单的猜想，我们可以得出结论，同一个质因子的不同次幂数不能组成互质的因子对，而质因数（也就是底数）不同的一定可以构成互质的因子对。因此，我们可以将问题抽象成一个取球问题，每个质因数代表一个种类的球，这种球的个数就是该质因数的次幂，那么我们要做的就是任取两种球组成一对。

实现：

​ 虽然思路是组合计数，但是略做思考发现通过排列组合很难去处理这类问题，会造成重复的计数。由于每一类球的选取策略很简单，对于第i种球，我们可以做的就是选或者不选，所以可以用\(f[i]\)来表示前i种球我们可以组成的互质因子对数，关系可以通过递推式\(f[i] = (f[i - 1]+f[i-1]*2*c[i])\)获得，记得取模。

#include <bits/stdc++.h>
    
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
#define SZ(x)    (int)x.size()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}

const int mod = 1e9 + 7;
const int N = 10005;
int n;
LL f[N]; //前i种质数所组成的个数，对于第i个可以选或者不选

void solve()
{
    scanf("%d", &n);
    f[0] = 1;
    vector<int> p(n + 1), c(n + 1);
    rep(i, 1, n + 1)
        scanf("%d%d", &p[i], &c[i]);

    for(int i = 1; i <= n; i ++)
        f[i] = (f[i - 1] + f[i - 1] * 2ll * c[i]) % mod;
    printf("%lld\n", f[n]);
}

signed main()
{
    int _ = 1;
    scanf("%d", &_);
    while(_--)
        solve();
}