#865495 (C++14) No.137 貯金箱の焦り

提出ソース

結果

問題	No.137 貯金箱の焦り
ユーザー	lbm364dl
提出日時	2023-05-03 01:50:15
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	474 ms / 5,000 ms
コード長	6,493 bytes
コンパイル時間	1,647 ms
コンパイル使用メモリ	105,072 KB
実行使用メモリ	8,736 KB
最終ジャッジ日時	2024-11-21 12:12:03
合計ジャッジ時間	4,839 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	5 ms 6,820 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	18 ms 6,820 KB
testcase_05	AC	5 ms 6,816 KB
testcase_06	AC	10 ms 6,820 KB
testcase_07	AC	5 ms 6,820 KB
testcase_08	AC	6 ms 6,820 KB
testcase_09	AC	10 ms 6,820 KB
testcase_10	AC	6 ms 6,820 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	474 ms 8,736 KB
testcase_13	AC	42 ms 6,816 KB
testcase_14	AC	239 ms 6,820 KB
testcase_15	AC	222 ms 6,816 KB
testcase_16	AC	221 ms 6,816 KB
testcase_17	AC	117 ms 6,816 KB
testcase_18	AC	236 ms 6,816 KB
testcase_19	AC	223 ms 6,816 KB
testcase_20	AC	12 ms 6,816 KB
testcase_21	AC	222 ms 6,820 KB
testcase_22	AC	56 ms 6,820 KB
testcase_23	AC	49 ms 6,816 KB
testcase_24	AC	100 ms 6,816 KB
testcase_25	AC	241 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <queue>
//#include <atcoder/all>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
//using namespace atcoder;

#ifdef LOCAL
#define show(x) cerr << #x" = " << (x) << "\n"
#else
#define show(x) 0
#endif

#define pb push_back
#define pp pop_back
#define mp make_pair
#define fst first
#define snd second
#define FOR(var, from, to) for(int var = from; var < int(to); ++var)
#define all(x) x.begin(), x.end()
#define rev(x) x.rbegin(), x.rend()
#define sz(x) int(x.size())
#define vec(x) vector<x>
#define INF 2000000000

//using mint = modint998244353;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
// use unique second element of pair to work as multiset
//typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const ll mod = 1234567891, mod2 = 998244353;

template<typename T, typename U> ostream &operator<<(ostream &os, pair<T,U> p){os << "(" << p.fst << "," << p.snd << ")"; return os;}
template<typename T, typename U> istream &operator>>(istream &is, pair<T,U> &p){is >> p.fst >> p.snd; return is;}
template<typename T> istream &operator>>(istream &is, vector<T> &v){FOR(i, 0, v.size()) is >> v[i]; return is;}
template<typename T> ostream &operator<<(ostream &os, vector<T> v){for(T x : v) os << x << " "; return os;}
template<typename T> ostream &operator<<(ostream &os, set<T> s){for(T x : s) os << x << " "; return os;} 
template<typename T> ostream &operator<<(ostream &os, multiset<T> s){for(T x : s) os << x << " "; return os;} 
template<typename T, typename U> ostream &operator<<(ostream &os, map<T,U> m){for(auto x : m) os << x << " "; return os;} 
//ostream &operator<<(ostream &os, ordered_set s){for(int x : s) os << x << " "; return os;} 
//ostream &operator<<(ostream &os, ordered_multiset s){for(pii x : s) os << x.fst << " "; return os;} 
ll mod_pow(ll a, ll b, ll m){ ll sol = 1; while(b){ if(b&1){ sol = (sol*a)%m; b--; }else{ a = (a*a)%m; b/=2; } } return sol;}
ll rem(ll a, ll b){ ll res = a%b; return res < 0 ? res+b : res; }

const int N = 3e5 + 9;

struct base {
  double x, y;
  base() { x = y = 0; }
  base(double x, double y): x(x), y(y) { }
};
inline base operator + (base a, base b) { return base(a.x + b.x, a.y + b.y); }
inline base operator - (base a, base b) { return base(a.x - b.x, a.y - b.y); }
inline base operator * (base a, base b) { return base(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
inline base conj(base a) { return base(a.x, -a.y); }
ll lim = 1;
vector<base> roots = {{0, 0}, {1, 0}};
vector<ll> rev = {0, 1};
const double PI = acosl(- 1.0);
void ensure_base(ll p) {
  if(p <= lim) return;
  rev.resize(1 << p);
  for(ll i = 0; i < (1 << p); i++) rev[i] = (rev[i >> 1] >> 1) + ((i & 1)  <<  (p - 1));
  roots.resize(1 << p);
  while(lim < p) {
    double angle = 2 * PI / (1 << (lim + 1));
    for(ll i = 1 << (lim - 1); i < (1 << lim); i++) {
      roots[i << 1] = roots[i];
      double angle_i = angle * (2 * i + 1 - (1 << lim));
      roots[(i << 1) + 1] = base(cos(angle_i), sin(angle_i));
    }
    lim++;
  }
}
void fft(vector<base> &a, ll n = -1) {
  if(n == -1) n = a.size();
  assert((n & (n - 1)) == 0);
  ll zeros = __builtin_ctz(n);
  ensure_base(zeros);
  ll shift = lim - zeros;
  for(ll i = 0; i < n; i++) if(i < (rev[i] >> shift)) swap(a[i], a[rev[i] >> shift]);
  for(ll k = 1; k < n; k <<= 1) {
    for(ll i = 0; i < n; i += 2 * k) {
      for(ll j = 0; j < k; j++) {
        base z = a[i + j + k] * roots[j + k];
        a[i + j + k] = a[i + j] - z;
        a[i + j] = a[i + j] + z;
      }
    }
  }
}
//eq = 0: 4 FFTs in total
//eq = 1: 3 FFTs in total
vector<ll> multiply(vector<ll> &a, vector<ll> &b, ll eq = 0) {
  ll need = a.size() + b.size() - 1;
  ll p = 0;
  while((1 << p) < need) p++;
  ensure_base(p);
  ll sz = 1 << p;
  vector<base> A, B;
  if(sz > (ll)A.size()) A.resize(sz);
  for(ll i = 0; i < (ll)a.size(); i++) {
    ll x = (a[i] % mod + mod) % mod;
    A[i] = base(x & ((1 << 15) - 1), x >> 15);
  }
  fill(A.begin() + a.size(), A.begin() + sz, base{0, 0});
  fft(A, sz);
  if(sz > (ll)B.size()) B.resize(sz);
  if(eq) copy(A.begin(), A.begin() + sz, B.begin());
  else {
    for(ll i = 0; i < (ll)b.size(); i++) {
      ll x = (b[i] % mod + mod) % mod;
      B[i] = base(x & ((1 << 15) - 1), x >> 15);
    }
    fill(B.begin() + b.size(), B.begin() + sz, base{0, 0});
    fft(B, sz);
  }
  double ratio = 0.25 / sz;
  base r2(0,  - 1), r3(ratio, 0), r4(0,  - ratio), r5(0, 1);
  for(ll i = 0; i <= (sz >> 1); i++) {
    ll j = (sz - i) & (sz - 1);
    base a1 = (A[i] + conj(A[j])), a2 = (A[i] - conj(A[j])) * r2;
    base b1 = (B[i] + conj(B[j])) * r3, b2 = (B[i] - conj(B[j])) * r4;
    if(i != j) {
      base c1 = (A[j] + conj(A[i])), c2 = (A[j] - conj(A[i])) * r2;
      base d1 = (B[j] + conj(B[i])) * r3, d2 = (B[j] - conj(B[i])) * r4;
      A[i] = c1 * d1 + c2 * d2 * r5;
      B[i] = c1 * d2 + c2 * d1;
    }
    A[j] = a1 * b1 + a2 * b2 * r5;
    B[j] = a1 * b2 + a2 * b1;
  }
  fft(A, sz); fft(B, sz);
  vector<ll> res(need);
  for(ll i = 0; i < need; i++) {
    long long aa = A[i].x + 0.5;
    long long bb = B[i].x + 0.5;
    long long cc = A[i].y + 0.5;
    res[i] = (aa + ((bb % mod) << 15) + ((cc % mod) << 30))%mod;
  }
  return res;
}

vector<ll> pow(vector<ll>& a, ll p) {
  vector<ll> res;
  res.emplace_back(1);
  while(p) {
    if(p & 1) res = multiply(res, a);
    a = multiply(a, a, 1);
    p >>= 1;
  }
  return res;
}

void test_case(){
	ll n, m; cin >> n >> m;
	vec(int) v(n); cin >> v;

	queue<vec(ll)> q;
	for(int x : v){
		vec(ll) cur(x+1);
		cur[0] = 1;
		cur[x] = 1;
		q.push(cur);
	}
	while(sz(q) > 1){
		vec(ll) p1 = q.front(); q.pop();
		vec(ll) p2 = q.front(); q.pop();
		q.push(multiply(p1, p2));
	}
	vec(ll) F = q.front();
	cerr << "xd\n";

	auto Si = [&](int r, vec(ll) v){
		FOR(i, 0, sz(v)){
			int who = 2*i + r;
			v[i] = who < sz(v) ? v[who] : 0LL;
		}
		while(!v.back()) v.pp();
		return v;
	};

	vec(ll) A{1};
	while(m){
		int r = m % 2;
		A = Si(r, multiply(A, F));
		m /= 2;
	}
	cout << A[0] << "\n";
}

int main(){
	#ifndef LOCAL
	ios_base::sync_with_stdio(false);
  	cin.tie(NULL);
	#endif

	int t = 1;
	FOR(i, 0, t) test_case();
	return 0;
}

yukicoder

結果

テストケース

ソースコード