fork download
copy 
  1. /*
  2.     Author: Nguyen Nhut Truong
  3.     From Chuyen Tien Giang High School For The Gifed
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. //#define int long long
  9. #define start signed main
  10. #define fi first
  11. #define se second
  12. #define pb push_back
  13. #define eb emplace_back
  14. #define il pair<int,ll>
  15. #define ii pair<int,int>
  16. #define len(s) (int)s.size()
  17. #define all(s) (s).begin(),(s).end()
  18. #define OpenFile(Name) if (fopen(Name".inp","r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  19.  
  20. #define MASK(x) ((1LL)<<(x))
  21. #define Bit(x,i) (((x)>>(i))&1)
  22. #define Countbit(x) __builtin_popcountll(x)
  23.  
  24. typedef long long ll;
  25. typedef long double ld;
  26.  
  27. int dx[]={1,-1,0,0,-1,1,1,-1};
  28. int dy[]={0,0,1,-1,-1,-1,1,1};
  29.  
  30. template <class C> bool Minimize(C &a, C b) { if (a>b) { a=b; return true; } return false;}
  31. template <class C> bool Maximize(C &a, C b) { if (a<b) { a=b; return true; } return false;}
  32.  
  33. inline ll add(ll a,ll b,ll c) { return (a+b)%c; };
  34. inline ll suf(ll a,ll b,ll c) { return (a-b+c)%c; };
  35. inline ll mul(ll a,ll b,ll c) { return ((a%c)*(b%c))%c; };
  36.  
  37. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  38.  
  39. ll rand(ll l,ll r){
  40.     assert(l<=r);
  41.     return l+rd()%(r-l+1);
  42. }
  43.  
  44. void MakeInp() {
  45.     ofstream cout("Task.inp");
  46.  
  47.     ll n=rand(1,1000),s=rand(1,1000);
  48.     cout<<n<<' '<<s<<endl;
  49.     for (int i=1;i<=n;++i) {
  50.         ll f=rand(0,1e3);
  51.         cout<<f<<' ';
  52.     }
  53.  
  54.  
  55.     cout.close();
  56. }
  57.  
  58. /// Constant Limit
  59.  
  60. const int N=1e6+5,M=1e3+5,INF=1e9,lim=1e6;
  61. const int block=448,base=31;
  62.  
  63. ll Mod=998244353,Mod_base=1777777777,LNF=1e18;
  64.  
  65. ///________________________________________________________________________________________________________
  66.  
  67. int n;
  68. ll s;
  69. vector<ll> a;
  70.  
  71. namespace task1 {
  72.     void solve() {
  73.         ll res=0;
  74.         for (int mask=1;mask<MASK(n);++mask) {
  75.             ll cur=0;
  76.             for (int i=1;i<=n;++i)
  77.             if (Bit(mask,i-1)) cur+=a[i];
  78.  
  79.             if (cur==s) res++;
  80.         }
  81.  
  82.         cout<<res%Mod;
  83.     }
  84. }
  85.  
  86. namespace task2 {
  87.     void solve() {
  88.         int res=0;
  89.         vector<vector<ll>> dp(n+3,vector<ll>(s+3,0));
  90.  
  91.         dp[0][0]=1;
  92.         for (int i=1;i<=n;++i)
  93.         for (int j=0;j<=s;++j) {
  94.             dp[i][j]=dp[i-1][j];
  95.             if (j-a[i]>=0) dp[i][j]=add(dp[i][j],dp[i-1][j-a[i]],Mod);
  96.         }
  97.  
  98.         cout<<dp[n][s];
  99.     }
  100. }
  101.  
  102. namespace task3 {
  103.     vector<int> res1,res2;
  104.  
  105.     void Try1(int i,ll sum) {
  106.         if (sum>s) return;
  107.         if (i==n/2+1) res1.pb(sum);
  108.         else {
  109.          Try1(i+1,sum+a[i]);
  110.          Try1(i+1,sum);
  111.         }
  112.     }
  113.  
  114.     void Try2(int i,ll sum) {
  115.         if (sum>s) return;
  116.         if (i==n+1) res2.pb(sum);
  117.         else {
  118.             Try2(i+1,sum+a[i]);
  119.             Try2(i+1,sum);
  120.         }
  121.     }
  122.  
  123.     void solve() {
  124.         ll ans=0;
  125.         Try1(1,0);
  126.         Try2(n/2+1,0);
  127.         sort(all(res1));
  128.         for(ll x:res2) {
  129.            int tmp1=upper_bound(all(res1),s-x)-res1.begin();
  130.            int tmp2=lower_bound(all(res1),s-x)-res1.begin();
  131.  
  132.            ans=add(ans,tmp1-tmp2,Mod);
  133.            //ans+=tmp1-tmp2;
  134.         }
  135.  
  136.         cout<<ans;
  137.     }
  138. }
  139.  
  140. start() {
  141.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  142.     OpenFile("TASK");
  143.  
  144.     //MakeInp();
  145.     cin>>n>>s;
  146.  
  147.     a.eb(0);
  148.     for (int i=1;i<=n;++i) {
  149.         ll x; cin>>x;
  150.         a.eb(x);
  151.     }
  152.  
  153.     //task1::solve();
  154.     //task2::solve();
  155.     //task3::solve();
  156.  
  157.     if (n<=20) task1::solve(); else
  158.     if (n<=40) task2::solve(); else task3::solve();
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.     //cerr<<"\nBien dich thanh cong\nTime: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s\n";
  166.     return 0;
  167. }
  168.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DTYaxx
language:
C++14 (clang 8.0)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!