結果

問題 No.137 貯金箱の焦り
ユーザー chocoruskchocorusk
提出日時 2018-12-11 10:47:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,989 ms / 5,000 ms
コード長 4,843 bytes
コンパイル時間 1,588 ms
コンパイル使用メモリ 112,072 KB
実行使用メモリ 27,304 KB
最終ジャッジ日時 2023-10-19 23:43:50
合計ジャッジ時間 56,115 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,964 ms
27,304 KB
testcase_01 AC 1,966 ms
27,304 KB
testcase_02 AC 1,965 ms
27,304 KB
testcase_03 AC 1,968 ms
27,304 KB
testcase_04 AC 1,963 ms
27,304 KB
testcase_05 AC 1,963 ms
27,304 KB
testcase_06 AC 1,966 ms
27,304 KB
testcase_07 AC 1,966 ms
27,304 KB
testcase_08 AC 1,966 ms
27,304 KB
testcase_09 AC 1,974 ms
27,304 KB
testcase_10 AC 1,969 ms
27,304 KB
testcase_11 AC 1,964 ms
27,304 KB
testcase_12 AC 1,969 ms
27,304 KB
testcase_13 AC 1,976 ms
27,304 KB
testcase_14 AC 1,968 ms
27,304 KB
testcase_15 AC 1,965 ms
27,304 KB
testcase_16 AC 1,985 ms
27,304 KB
testcase_17 AC 1,986 ms
27,304 KB
testcase_18 AC 1,980 ms
27,304 KB
testcase_19 AC 1,989 ms
27,304 KB
testcase_20 AC 1,970 ms
27,304 KB
testcase_21 AC 1,963 ms
27,304 KB
testcase_22 AC 1,964 ms
27,304 KB
testcase_23 AC 1,964 ms
27,304 KB
testcase_24 AC 1,969 ms
27,304 KB
testcase_25 AC 1,963 ms
27,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<int, int> Pii;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)

template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }
ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }

template<int mod, int primitive_root>
class NTT {
public:
	int get_mod() const { return mod; }
	void _ntt(vector<ll>& a, int sign) {
		const int n = sz(a);
		assert((n ^ (n&-n)) == 0); //n = 2^k

		const int g = 3; //g is primitive root of mod
		int h = (int)mod_pow(g, (mod - 1) / n, mod); // h^n = 1
		if (sign == -1) h = (int)mod_inv(h, mod); //h = h^-1 % mod

		//bit reverse
		int i = 0;
		for (int j = 1; j < n - 1; ++j) {
			for (int k = n >> 1; k >(i ^= k); k >>= 1);
			if (j < i) swap(a[i], a[j]);
		}

		for (int m = 1; m < n; m *= 2) {
			const int m2 = 2 * m;
			const ll base = mod_pow(h, n / m2, mod);
			ll w = 1;
			FOR(x, m) {
				for (int s = x; s < n; s += m2) {
					ll u = a[s];
					ll d = a[s + m] * w % mod;
					a[s] = u + d;
					if (a[s] >= mod) a[s] -= mod;
					a[s + m] = u - d;
					if (a[s + m] < 0) a[s + m] += mod;
				}
				w = w * base % mod;
			}
		}

		for (auto& x : a) if (x < 0) x += mod;
	}
	void ntt(vector<ll>& input) {
		_ntt(input, 1);
	}
	void intt(vector<ll>& input) {
		_ntt(input, -1);
		const int n_inv = mod_inv(sz(input), mod);
		for (auto& x : input) x = x * n_inv % mod;
	}

	// 畳み込み演算を行う
	vector<ll> convolution(const vector<ll>& a, const vector<ll>& b){
		int ntt_size = 1;
		while (ntt_size < sz(a) + sz(b)) ntt_size *= 2;

		vector<ll> _a = a, _b = b;
		_a.resize(ntt_size); _b.resize(ntt_size);

		ntt(_a);
		ntt(_b);

		FOR(i, ntt_size){
			(_a[i] *= _b[i]) %= mod;
		}

		intt(_a);
		return _a;
	}
};

typedef NTT<167772161, 3> NTT_1;
typedef NTT<469762049, 3> NTT_2;
typedef NTT<1224736769, 3> NTT_3;

// garnerのアルゴリズムを直書きしたversion,速い
vector<ll> fast_int32mod_convolution(vector<ll> a, vector<ll> b,int mod){
	for (auto& x : a) x %= mod;
	for (auto& x : b) x %= mod;
	
	NTT_1 ntt1; NTT_2 ntt2; NTT_3 ntt3;
	assert(ntt1.get_mod() < ntt2.get_mod() && ntt2.get_mod() < ntt3.get_mod());
	auto x = ntt1.convolution(a, b);
	auto y = ntt2.convolution(a, b);
	auto z = ntt3.convolution(a, b);

	// garnerのアルゴリズムを極力高速化した
	const ll m1 = ntt1.get_mod(), m2 = ntt2.get_mod(), m3 = ntt3.get_mod();
	const ll m1_inv_m2 = mod_inv<ll>(m1, m2);
	const ll m12_inv_m3 = mod_inv<ll>(m1 * m2, m3);
	const ll m12_mod = m1 * m2 % mod;
	vector<ll> ret(sz(x));
	FOR(i, sz(x)){
		ll v1 = (y[i] - x[i]) *  m1_inv_m2 % m2;
		if (v1 < 0) v1 += m2;
		ll v2 = (z[i] - (x[i] + m1 * v1) % m3) * m12_inv_m3 % m3;
		if (v2 < 0) v2 += m3;
		ll constants3 = (x[i] + m1 * v1 + m12_mod * v2) % mod;
		if (constants3 < 0) constants3 += mod;
		ret[i] = constants3;
	}

	return ret;
}

const ll MOD=1234567891;

int main()
{
	int n; ll m;
	cin>>n>>m;
	int a[50];
	for(int i=0; i<n; i++) cin>>a[i];
	ll dp0[51][25001]={};
	dp0[0][0]=1;
	for(int i=0; i<n; i++){
		for(int j=0; j<=25000; j++){
			dp0[i+1][j]+=dp0[i][j];
			if(j>=a[i]) dp0[i+1][j]+=dp0[i][j-a[i]];
			dp0[i+1][j]%=MOD;
		}
	}
	vector<ll> v[2];
	for(int k=0; k<=25000; k++){
		v[k&1].push_back(dp0[n][k]);
	}
	ll dp[61][25001]={};
	dp[0][0]=1;
	for(int i=0; i<60; i++){
		int par=((m&(1ll<<i))?1:0);
		vector<ll> w[2];
		for(int j=0; j<=25000; j++){
			w[j&1].push_back(dp[i][j]);
		}
		if(par){
			auto u=fast_int32mod_convolution(w[1], v[0], (int)MOD);
			u.resize(sz(w[1]) + sz(v[0]) - 1);
			for(int j=0; j<u.size(); j++){
				dp[i+1][j]+=u[j];
				dp[i+1][j]%=MOD;
			}
			u=fast_int32mod_convolution(w[0], v[1], (int)MOD);
			u.resize(sz(w[0]) + sz(v[1]) - 1);
			for(int j=0; j<u.size(); j++){
				dp[i+1][j]+=u[j];
				dp[i+1][j]%=MOD;
			}
		}else{
			auto u=fast_int32mod_convolution(w[0], v[0], (int)MOD);
			u.resize(sz(w[0]) + sz(v[0]) - 1);
			for(int j=0; j<u.size(); j++){
				dp[i+1][j]+=u[j];
				dp[i+1][j]%=MOD;
			}
			u=fast_int32mod_convolution(w[1], v[1], (int)MOD);
			u.resize(sz(w[1]) + sz(v[1]) - 1);
			for(int j=0; j<u.size(); j++){
				dp[i+1][j+1]+=u[j];
				dp[i+1][j+1]%=MOD;
			}
		}
	}
	cout<<dp[60][0]<<endl;
	return 0;
}
0