1 条题解

  • 0
    @ 2026-10-2 2:21:44

    使用十亿进制任意精度整数累加组合数,覆盖 20 种面值组成 4000 时超过 64 位的答案。

    #include <bits/stdc++.h>
    using namespace std;
    struct Big{vector<unsigned>a;Big(unsigned v=0){if(v)a.push_back(v);}Big&operator+=(const Big&b){a.resize(max(a.size(),b.a.size()));unsigned long long carry=0;for(size_t i=0;i<a.size();i++){unsigned long long value=a[i]+carry+(i<b.a.size()?b.a[i]:0);a[i]=value%1000000000;carry=value/1000000000;}if(carry)a.push_back(carry);return *this;}friend ostream&operator<<(ostream&o,const Big&b){if(b.a.empty())return o<<0;o<<b.a.back();for(int i=int(b.a.size())-2;i>=0;i--)o<<setw(9)<<setfill('0')<<b.a[i];return o;}};
    int main(){int n,target;cin>>n>>target;vector<Big>d(target+1);d[0]=Big(1);while(n--){int coin;cin>>coin;for(int j=coin;j<=target;j++)d[j]+=d[j-coin];}cout<<d[target]<<"\n";}
    
    • 1

    信息

    ID
    3948
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    0
    已通过
    0
    上传者