結果
| 問題 | No.213 素数サイコロと合成数サイコロ (3-Easy) |
| ユーザー |
 yosupot
|
| 提出日時 | 2017-02-05 04:35:19 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,225 bytes |
| コンパイル時間 | 1,910 ms |
| コンパイル使用メモリ | 122,060 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-24 06:29:31 |
| 合計ジャッジ時間 | 2,320 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
ソースコード
#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>
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));
using Pc = complex<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] = polar<R>(1, i*2*PI/N);
}
}
vector<Pc> a(N), b(N);
copy(begin(c), end(c), begin(a));
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 = conj(now);
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);
}
copy(begin(a), end(a), begin(c));
}
template<class Mint>
vector<Mint> multiply(vector<Mint> x, vector<Mint> y) {
int S = x.size()+y.size()-1;
int N = 2<<bsr(S-1);
vector<Pc> a[3], b[3];
for (int fe = 0; fe < 3; fe++) {
a[fe] = vector<Pc>(N);
b[fe] = vector<Pc>(N);
for (int i = 0; i < int(x.size()); i++) {
a[fe][i] = Pc((x[i].v >> (fe*10)) & ((1<<10)-1), 0);
}
for (int i = 0; i < int(y.size()); i++) {
b[fe][i] = Pc((y[i].v >> (fe*10)) & ((1<<10)-1), 0);
}
fft(false, a[fe]);
fft(false, b[fe]);
}
vector<Mint> z(S);
vector<Pc> c(N);
Mint base = 1;
for (int fe = 0; fe < 5; fe++) {
fill_n(begin(c), N, Pc(0, 0));
for (int xf = max(fe-2, 0); xf <= min(2, 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].real()))) * base;
}
base *= 1<<10;
}
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 & (1<<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 = 140;
const int MC = 7;
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;
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 nw = MD-1; nw >= 0; nw--) {
for (int nc = c; nc >= 0; nc--) {
for (int us = 1; us <= nc; us++) {
if (nw < d*us) break;
buf[nc][nw] += buf[nc-us][nw-d*us];
}
}
}
}
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 nw = MD-1; nw >= 0; nw--) {
for (int nc = c; nc >= 0; nc--) {
for (int us = 1; us <= nc; us++) {
if (nw < d*us) break;
buf[nc][nw] += buf[nc-us][nw-d*us];
}
}
}
}
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;
}
/* for (int i = 0; i < 10; i++) {
cout << sm[i].v << " ";
} cout << endl;*/
Mint ans = 0;
for (int i = 0; i < MD; i++) {
ans += sm[i];
}
cout << ans.v << endl;
//to_string(Poly<Mint>(co)) << endl;
/* int k, n;
cin >> k >> n; n--;
Poly<Mint> md = [&](){
V<Mint> v(k, Mint(1));
v.push_back(-1);
return Poly<Mint>(v);
}();
Poly<Mint> p = nth_mod(n, md);
Mint sm = 0;
for (int i = 0; i < k; i++) {
sm += p.freq(i);
}
cout << sm.v << endl;*/
return 0;
}