Project Euler 155

题目

Counting Capacitor Circuits

An electric circuit uses exclusively identical capacitors of the same value $C$.

The capacitors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel with other capacitors or other sub-units to form larger sub-units, and so on up to a final circuit.

Using this simple procedure and up to n identical capacitors, we can make circuits having a range of different total capacitances. For example, using up to $n=3$ capacitors of $60\mu F$ each, we can obtain the following $7$ distinct total capacitance values:

If we denote by $D(n)$ the number of distinct total capacitance values we can obtain when using up to n equal-valued capacitors and the simple procedure described above, we have: $D(1)=1, D(2)=3, D(3)=7 \dots$

Find $D(18)$.

Reminder : When connecting capacitors $C_1, C_2$ etc in parallel, the total capacitance is $C_T=C_1+C_2+\dots$, whereas when connecting them in series, the overall capacitance is given by:$\dfrac{1}{C_T}=\dfrac{1}{C_1}+\dfrac{1}{C_2}+\dots$.

解决方案

目前的办法应该只有暴力枚举，剩下的只是优化：

1. 为减少枚举量，如果全局集合已经有的值，那就不需要继续添加到当前集合了。
2. 实现一个简易的分数类，避免用浮点数产生误差，同时避免进行除法操作。

枚举的思想：如果已经有一对整体的电容值分别是$u,v$，那么分别把这两“块”进行串联或者并联，得到新值$\dfrac{1}{\dfrac{1}{u}+\dfrac{1}{v}},u+v$。

这个数列在OEIS上的查询结果为A153588。

代码

# include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 18;
struct Fraction{
    ll num,den;
    Fraction operator + (Fraction f){
        ll a = num*f.den+den*f.num;
        ll b = den*f.den;
        ll g=__gcd(a,b);
        return {a/g,b/g};
    }
    Fraction inv(){
        return {den,num};
    }
    //这里的小于只是为了用于区分分数的不同，而并非是分数的值大小本身。
    bool operator < (const Fraction &f) const{
        return num<f.num||num==f.num&&den<f.den;
    }
};
set<Fraction>st,now[N+2];
int main(){
    st.insert(Fraction{1,1});
    now[1].insert(Fraction{1,1});
    for(int i=2;i<=N;i++){
        for(int j=1;j<=i/2;j++){
            for(Fraction u:now[j]){
                for(Fraction v:now[i-j]){
                    Fraction x=u+v,y=(u.inv()+v.inv()).inv();
                    if(!st.count(x)){
                        st.insert(x);
                        now[i].insert(x);
                    }
                    if(!st.count(y)){
                        st.insert(y);
                        now[i].insert(y);
                    }
                }
            }
        }
    }
    int ans=st.size();
    printf("%d\n",ans);

}