#include<bits/stdc++.h> typedef long long ll; typedef long double ld; typedef std::pair<ll, ll> pll; typedef std::pair<int, int> pii; #define all(x) (x).begin(),(x).end() #define debug std::cout<<"ok"<<std::endl const ll INF=1e18; const ll MOD=1000000007; main () { int n; std::cin>>n; std::vector<ll> V(n); ll S=0; for (auto &a:V) { std::cin>>a; S+=a; } std::sort(all(V)); std::vector<ll> D(S+2,0); if (V[0]!=1) { std::cout<<0<<std::endl; return 0; } ll MAX=1; for (int i=0; i<V.size(); i++) { std::queue<pll> Q; for (int j=V[i]-2; j<D.size()-V[i]-1 && j<MAX; j++) { if (j<0) j=0; if (D[j]) Q.push({j+V[i],D[j+V[i]]+D[j]}); } while(Q.size()) { D[Q.front().first]=Q.front().second; MAX=std::max(MAX,Q.front().first+1); if (D[Q.front().first%MOD]) D[Q.front().first]=D[Q.front().first]%MOD; else D[Q.front().first]=MOD; Q.pop(); } if (V[i]==1) D[0]++; } ll W=0; for (auto a:D) W=(W+a)%MOD; std::cout<<W<<std::endl; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include<bits/stdc++.h> typedef long long ll; typedef long double ld; typedef std::pair<ll, ll> pll; typedef std::pair<int, int> pii; #define all(x) (x).begin(),(x).end() #define debug std::cout<<"ok"<<std::endl const ll INF=1e18; const ll MOD=1000000007; main () { int n; std::cin>>n; std::vector<ll> V(n); ll S=0; for (auto &a:V) { std::cin>>a; S+=a; } std::sort(all(V)); std::vector<ll> D(S+2,0); if (V[0]!=1) { std::cout<<0<<std::endl; return 0; } ll MAX=1; for (int i=0; i<V.size(); i++) { std::queue<pll> Q; for (int j=V[i]-2; j<D.size()-V[i]-1 && j<MAX; j++) { if (j<0) j=0; if (D[j]) Q.push({j+V[i],D[j+V[i]]+D[j]}); } while(Q.size()) { D[Q.front().first]=Q.front().second; MAX=std::max(MAX,Q.front().first+1); if (D[Q.front().first%MOD]) D[Q.front().first]=D[Q.front().first]%MOD; else D[Q.front().first]=MOD; Q.pop(); } if (V[i]==1) D[0]++; } ll W=0; for (auto a:D) W=(W+a)%MOD; std::cout<<W<<std::endl; } |