結果

問題 No.137 貯金箱の焦り
コンテスト
ユーザー suzumi
提出日時 2026-05-09 16:44:00
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 183 ms / 5,000 ms
コード長 2,661 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,105 ms
コンパイル使用メモリ 354,384 KB
実行使用メモリ 26,368 KB
最終ジャッジ日時 2026-05-09 16:44:12
合計ジャッジ時間 7,725 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>
#include <unordered_map>
#include <queue>
#include <deque>
#include <math.h>
#include <limits.h>
#include <set>
#include <stack>
#include <map>
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <cmath>
#define Lt Line<ll>
#define Pt Point<ll>
//#define ll ll
#define Pd Point<ld>
#define Ld Line<ld>
#define LL ll
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define debug(x) cout<<"DEBUG"<<x;
#define Hash __gnu_pbds::gp_hash_table 
// #define ll ll
// using i64 = ll;
using ll = long long  ;
using namespace std;

#define i128 __int128

const ll N=2e6+10;
const ll M=1e7+10;
const ll MOD= 1234567891;
const ll all=(1<<12);
using ld =long double;

typedef std::pair<ll,ll> pii;
typedef std::pair<ll,pii> piii;


using ld =long double;
const ld PI = acosl(-1);
const ld EPS = 1e-9;
const ld INF = numeric_limits<ld>::max();
#define cc(x) cout << fixed << setprecision(x);

const long long G = 3;
const long long Gi = 1234567891; // 3 在模 998244353 下的逆元


ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

ll qpow(ll a,ll b,const ll &mm)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mm;
        a=a*a%mm;
        b>>=1;
    }
    return res;
}


ll n,m,g;

ll dp[62][50010];


void reset()
{

}


void solve()
{
    cin>>n>>m;
    vector<ll> num(n);
    ll sum=0;
    for(auto &t:num) cin>>t,sum+=t;

    dp[0][0]=1;

    ll f;

    for(ll mask=0;mask<61;mask++)
    {
        
        for(ll j=0;j<n;j++)
        {
            for(ll i=sum*2;i>=0;i--)
            {
                if(dp[mask][i]==0) continue;
                dp[mask][i+num[j]]=(dp[mask][i+num[j]]+dp[mask][i])%MOD;
            }
        }

        f=(m&1);

        for(ll i=sum*2;i>=0;i--)
        {
            if((i&1)!=f) continue;
            dp[mask+1][i/2]=(dp[mask+1][i/2]+dp[mask][i])%MOD;
        }

        m/=2;
    }

    cout<<dp[61][0];

    

}




int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // ll size(256<<20);
    // __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size)); 

    // cout.tie(0);
    //cout<<__lg((ll)1e9+10);

    // cc(12);
    //cout<<(ll<<20)<<'\n';
    //cout<<t<<'\n';


    ll t_=1; //cin>>t_;
    while(t_--)
    {
        solve();
        reset();
        if(t_==0) break;
        cout<<'\n';
    } 
    
    // exit(0);

    return 0;
}

// 7 7
// 1 2 3 4 5 1 6 6
0