結果
問題 | No.215 素数サイコロと合成数サイコロ (3-Hard) |
ユーザー | yosupot |
提出日時 | 2017-02-07 15:42:16 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,847 ms / 4,000 ms |
コード長 | 11,453 bytes |
コンパイル時間 | 3,111 ms |
コンパイル使用メモリ | 240,400 KB |
実行使用メモリ | 20,348 KB |
最終ジャッジ日時 | 2024-06-06 19:37:43 |
合計ジャッジ時間 | 9,045 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,847 ms
20,348 KB |
testcase_01 | AC | 1,837 ms
20,324 KB |
ソースコード
#pragma GCC target ("avx") #include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cstring> #include <cassert> #include <algorithm> #include <numeric> #include <random> #include <vector> #include <array> #include <bitset> #include <queue> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <complex> #include <x86intrin.h> #define ALIGN __attribute__((aligned(32))) using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; template<class T> using V = vector<T>; template<class T> using VV = V<V<T>>; constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); } int bsr(int x) { return 31 - __builtin_clz(x); } int bsr(ll x) { return 63 - __builtin_clzll(x); } int bsf(int x) { return __builtin_ctz(x); } int bsf(ll x) { return __builtin_ctzll(x); } template<class T> T pow(T x, ll n, T r = 1) { while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } template<uint MD> struct ModInt { uint v; ModInt() : v{0} {} ModInt(ll v) : v{normS(v%MD+MD)} {} explicit operator bool() const {return v != 0;} static uint normS(const uint &x) {return (x<MD)?x:x-MD;}; static ModInt make(const uint &x) {ModInt m; m.v = x; return m;} static ModInt inv(const ModInt &x) {return pow(ModInt(x), MD-2);} ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));} ModInt operator-(const ModInt &r) const {return make(normS(v+MD-r.v));} ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);} ModInt operator/(const ModInt &r) const {return *this*inv(r);} ModInt& operator+=(const ModInt &r) {return *this=*this+r;} ModInt& operator-=(const ModInt &r) {return *this=*this-r;} ModInt& operator*=(const ModInt &r) {return *this=*this*r;} ModInt& operator/=(const ModInt &r) {return *this=*this/r;} }; template<uint MD> string to_string(ModInt<MD> m) {return to_string(m.v);} using Mint = ModInt<TEN(9)+7>; using R = double; const R PI = 4*atan(R(1)); struct Pc { R x, y; Pc() : x(0), y(0) {} Pc(R x, R y) : x(x), y(y) {} Pc operator+(const Pc &r) const {return Pc(x+r.x, y+r.y);} Pc operator-(const Pc &r) const {return Pc(x-r.x, y-r.y);} Pc operator*(const Pc &r) const {return Pc(x*r.x-y*r.y, x*r.y+y*r.x);} Pc operator*(const R &r) const {return Pc(x*r, y*r);} Pc& operator+=(const Pc &r) {return *this=*this+r;} Pc& operator-=(const Pc &r) {return *this=*this-r;} Pc& operator*=(const Pc &r) {return *this=*this*r;} Pc& operator*=(const R &r) {return *this=*this*r;} static Pc polar(R r, R th) {return Pc(cos(th)*r, sin(th)*r);} }; void fft(bool type, vector<Pc> &c) { static vector<Pc> buf[30]; int N = int(c.size()); int s = bsr(N); assert(1<<s == N); if (!buf[s].size()) { buf[s] = vector<Pc>(N); for (int i = 0; i < N; i++) { buf[s][i] = Pc::polar(1, i*2*PI/N); } } vector<Pc> a = c, b(N); for (int i = 1; i <= s; i++) { int W = 1<<(s-i); //変更後の幅W for (int y = 0; y < N/2; y += W) { Pc now = buf[s][y]; if (type) now.y *= -1; for (int x = 0; x < W; x++) { auto l = a[y<<1 | x]; auto r = now * a[y<<1 | x | W]; b[y | x] = l+r; b[y | x | N>>1] = l-r; } } swap(a, b); } c = a; } template<class Mint> vector<Mint> multiply(vector<Mint> x, vector<Mint> y) { constexpr int B = 3, SHIFT = 10; int S = x.size()+y.size()-1; int N = 2<<bsr(S-1); vector<Pc> a[B], b[B]; for (int fe = 0; fe < B; fe++) { a[fe] = vector<Pc>(N); b[fe] = vector<Pc>(N); vector<Pc> c(N); for (int i = 0; i < int(x.size()); i++) { c[i].x = (x[i].v >> (fe*SHIFT)) & ((1<<SHIFT)-1); } for (int i = 0; i < int(y.size()); i++) { c[i].y = (y[i].v >> (fe*SHIFT)) & ((1<<SHIFT)-1); } fft(false, c); for (int i = 0; i < N; i++) { c[i] *= 0.5; } for (int i = 0; i < N; i++) { int j = (N-i)%N; a[fe][i] = Pc(c[i].x+c[j].x, c[i].y-c[j].y); b[fe][i] = Pc(c[i].y+c[j].y, -c[i].x+c[j].x); } } vector<Mint> z(S); vector<Pc> c[B]; for (int fe = 0; fe < B; fe++) { c[fe] = vector<Pc>(N); } for (int af = 0; af < B; af++) { for (int bf = 0; bf < B; bf++) { int cf = (af+bf)%B; for (int i = 0; i < N; i++) { if (af+bf<B) { c[cf][i] += a[af][i]*b[bf][i]; } else { c[cf][i] += a[af][i]*b[bf][i]*Pc(0, 1); } } } } for (int fe = 0; fe < B; fe++) { fft(true, c[fe]); } Mint base = 1; for (int fe = 0; fe < 2*B-1; fe++) { for (int i = 0; i < S; i++) { if (fe < B) { c[fe][i].x *= 1.0/N; z[i] += Mint(ll(round(c[fe][i].x)))*base; } else { c[fe-B][i].y *= 1.0/N; z[i] += Mint(ll(round(c[fe-B][i].y)))*base; } } base *= 1<<SHIFT; } /* vector<Pc> c(N); Mint base = 1; for (int fe = 0; fe <= (B-1)*2; fe++) { fill_n(begin(c), N, Pc(0, 0)); for (int xf = max(fe-(B-1), 0); xf <= min(B-1, fe); xf++) { int yf = fe-xf; for (int i = 0; i < N; i++) { c[i] += a[xf][i]*b[yf][i]; } } fft(true, c); for (int i = 0; i < S; i++) { c[i] *= 1.0/N; z[i] += Mint(ll(round(c[i].x))) * base; } base *= 1<<SHIFT; }*/ return z; } template<class D> struct Poly { V<D> v; int size() const {return int(v.size());} Poly(int N = 0) : v(V<D>(N)) {} Poly(const V<D> &v) : v(v) {shrink();} Poly& shrink() {while (v.size() && !v.back()) v.pop_back(); return *this;} D freq(int p) const { return (p < size()) ? v[p] : D(0); } Poly operator+(const Poly &r) const { int N = size(), M = r.size(); V<D> res(max(N, M)); for (int i = 0; i < max(N, M); i++) res[i] = freq(i)+r.freq(i); return Poly(res); } Poly operator-(const Poly &r) const { int N = size(), M = r.size(); V<D> res(max(N, M)); for (int i = 0; i < max(N, M); i++) res[i] = freq(i)-r.freq(i); return Poly(res); } Poly operator*(const Poly &r) const { int N = size(), M = r.size(); if (min(N, M) == 0) return Poly(); assert(N+M-1 >= 0); V<D> res = multiply(v, r.v); return Poly(res); } Poly operator*(const D &r) const { V<D> res(size()); for (int i = 0; i < size(); i++) res[i] = v[i]*r; return Poly(res); } Poly& operator+=(const Poly &r) {return *this = *this+r;} Poly& operator-=(const Poly &r) {return *this = *this-r;} Poly& operator*=(const Poly &r) {return *this = *this*r;} Poly& operator*=(const D &r) {return *this = *this*r;} Poly operator<<(const int n) const { assert(n >= 0); V<D> res(size()+n); for (int i = 0; i < size(); i++) { res[i+n] = v[i]; } return Poly(res); } Poly operator>>(const int n) const { assert(n >= 0); if (size() <= n) return Poly(); V<D> res(size()-n); for (int i = n; i < size(); i++) { res[i-n] = v[i]; } return Poly(res); } // x % y Poly rem(const Poly &y) const { return *this - y * div(y); } Poly rem_inv(const Poly &y, const Poly &ny, int B) const { return *this - y * div_inv(ny, B); } Poly div(const Poly &y) const { int B = max(size(), y.size()); return div_inv(y.inv(B), B); } Poly div_inv(const Poly &ny, int B) const { return (*this*ny)>>(B-1); } // this * this.inv() = x^n + r(x) (size()) Poly strip(int n) const { V<D> res = v; res.resize(min(n, size())); return Poly(res); } Poly rev(int n = -1) const { V<D> res = v; if (n != -1) res.resize(n); reverse(begin(res), end(res)); return Poly(res); } // f * f.inv() = x^B + r(x) (B >= n) Poly inv(int n) const { int N = size(); assert(N >= 1); assert(n >= N-1); Poly c = rev(); Poly d = Poly(V<D>({D(1)/c.freq(0)})); int i; for (i = 1; i+N-2 < n; i *= 2) { auto u = V<D>({2}); d = (d * (Poly(V<D>{2})-c*d)).strip(2*i); } return d.rev(n+1-N); } }; template<class D> string to_string(const Poly<D> &p) { if (p.size() == 0) return "0"; string s = ""; for (int i = 0; i < p.size(); i++) { if (p.v[i]) { s += to_string(p.v[i])+"x^"+to_string(i); if (i != p.size()-1) s += "+"; } } return s; } // x^n % mod template<class D> Poly<D> nth_mod(ll n, const Poly<D> &mod) { int B = mod.size() * 2 - 1; Poly<D> mod_inv = mod.inv(B); Poly<D> p = V<D>{Mint(1)}; int m = (!n) ? -1 : bsr(n); for (int i = m; i >= 0; i--) { if (n & (1LL<<i)) { // += 1 p = (p<<1).rem_inv(mod, mod_inv, B); } if (i) { // *= 2 p = (p*p).rem_inv(mod, mod_inv, B); } } return p; } const int MD = 610 * 13; const int MC = 310; const V<int> pd = {2, 3, 5, 7, 11, 13}; const V<int> cd = {4, 6, 8, 9, 10, 12}; int main() { ll n; int x, y; cin >> n >> x >> y; // n = 918741897598888935; x = 298; y = 299; V<Mint> co(MD+1); co[0] = 1; { int c = x; Mint buf[MC][MD]; buf[0][0] = 1; for (int d: pd) { for (int nc = 1; nc < MC; nc++) { for (int nw = d; nw < MD; nw++) { buf[nc][nw] += buf[nc-1][nw-d]; } } } V<Mint> co2(MD+1); for (int i = 0; i < MD; i++) { for (int j = 0; j < MD-i; j++) { co2[i+j] += co[i]*buf[c][j]; } } co = co2; } { int c = y; Mint buf[MC][MD]; buf[0][0] = 1; for (int d: cd) { for (int nc = 1; nc < MC; nc++) { for (int nw = d; nw < MD; nw++) { buf[nc][nw] += buf[nc-1][nw-d]; } } } V<Mint> co2(MD+1); for (int i = 0; i < MD; i++) { for (int j = 0; j < MD-i; j++) { co2[i+j] += co[i]*buf[c][j]; } } co = co2; } co[0] = -1; auto rco = co; reverse(begin(rco), end(rco)); auto pol = nth_mod(n, Poly<Mint>(rco)); V<Mint> buf(MD); buf[0] = 1; V<Mint> sm(MD); for (int i = 0; i < MD; i++) { //v[i] * f for (int j = 0; j < MD; j++) { sm[j] += pol.freq(i)*buf[j]; } for (int j = 1; j < MD; j++) { buf[j] += buf[0]*co[j]; } for (int j = 0; j < MD-1; j++) { buf[j] = buf[j+1]; } buf[MD-1] = 0; } Mint ans = 0; for (int i = 0; i < MD; i++) { ans += sm[i]; } cout << ans.v << endl; return 0; }