题解 | 牛牛的括号式

/*对于 k 个因子 (x + c₁)(x + c₂)...(x + c_k) 的乘积，其展开式中 x 的一次项系数是：sum = (c₂c₃...c_k) + (c₁c₃...c_k) + ... + (c₁c₂...c_{k-1})
这个和可以等价地表示为：sum = (c₁ * c₂ * ... * c_k) * (1/c₁ + 1/c₂ + ... + 1/c_k)
我们令 P = c₁ * c₂ * ... * c_k (即所有常数项的乘积)，那么一次项系数就是：sum = P * (1/c₁ + 1/c₂ + ... + 1/c_k)*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5,mod=10007;
ll n,h;
vector<ll>a;
string s;
ll qmi(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b/=2;
        a=a*a%mod;
    }
    return ans;
}
int main() {
    cin>>s;
    ll sum=1,ans=0;
    if(s.size()==5){//特判
        cout<<1;
        return 0;
    }
    for(ll i=0;i<s.size();i++){
        if(s[i]=='+'){
            ll d=s[i+1]-'0';
            a.push_back(d);
            sum=sum*(d)%mod;
        }else if(s[i]=='-'){
            ll d=s[i+1]-'0';
            a.push_back(-d);
            sum=sum*(-d)%mod;
        }
    }    
    //ans=(ans+(sum/a[i]))%mod;会出错
    //改成ans=(ans+sum*(1/a[i])%mod)
    //又因为模运算只支持加法、减法和乘法，但不直接支持除法 因此用费马小定理
    for(ll i=0;i<a.size();i++)
        ans=(ans+(sum*qmi(a[i],mod-2)%mod))%mod;
    if(ans<0) ans+=mod;//防止为负
    cout<<ans;
}