結果
| 問題 | No.213 素数サイコロと合成数サイコロ (3-Easy) |
| ユーザー |
 snrnsidy
|
| 提出日時 | 2023-04-17 11:07:46 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,815 bytes |
| コンパイル時間 | 6,906 ms |
| コンパイル使用メモリ | 493,300 KB |
| 実行使用メモリ | 67,912 KB |
| 最終ジャッジ日時 | 2024-04-20 17:00:42 |
| 合計ジャッジ時間 | 15,000 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
ソースコード
#pragma GCC optimize("O3")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<int M>
struct MINT{
int v;
MINT() : v(0) {}
MINT(ll val){
v = (-M <= val && val < M) ? val : val % M;
if(v < 0) v += M;
}
friend istream& operator >> (istream &is, MINT &a) { ll t; is >> t; a = MINT(t); return is; }
friend ostream& operator << (ostream &os, const MINT &a) { return os << a.v; }
friend bool operator == (const MINT &a, const MINT &b) { return a.v == b.v; }
friend bool operator != (const MINT &a, const MINT &b) { return a.v != b.v; }
friend MINT pw(MINT a, ll b){
MINT ret= 1;
while(b){
if(b & 1) ret *= a;
b >>= 1; a *= a;
}
return ret;
}
friend MINT inv(const MINT a) { return pw(a, M-2); }
MINT operator - () const { return MINT(-v); }
MINT& operator += (const MINT m) { if((v += m.v) >= M) v -= M; return *this; }
MINT& operator -= (const MINT m) { if((v -= m.v) < 0) v += M; return *this; }
MINT& operator *= (const MINT m) { v = (ll)v*m.v%M; return *this; }
MINT& operator /= (const MINT m) { *this *= inv(m); return *this; }
friend MINT operator + (MINT a, MINT b) { a += b; return a; }
friend MINT operator - (MINT a, MINT b) { a -= b; return a; }
friend MINT operator * (MINT a, MINT b) { a *= b; return a; }
friend MINT operator / (MINT a, MINT b) { a /= b; return a; }
operator int32_t() const { return v; }
operator int64_t() const { return v; }
};
namespace fft{
template<int W, int M>
static void NTT(vector<MINT<M>> &f, bool inv_fft = false){
using T = MINT<M>;
int N = f.size();
vector<T> root(N >> 1);
for(int i=1, j=0; i<N; i++){
int bit = N >> 1;
while(j >= bit) j -= bit, bit >>= 1;
j += bit;
if(i < j) swap(f[i], f[j]);
}
T ang = pw(T(W), (M-1)/N); if(inv_fft) ang = inv(ang);
root[0] = 1; for(int i=1; i<N>>1; i++) root[i] = root[i-1] * ang;
for(int i=2; i<=N; i<<=1){
int step = N / i;
for(int j=0; j<N; j+=i){
for(int k=0; k<i/2; k++){
T u = f[j+k], v = f[j+k+(i>>1)] * root[k*step];
f[j+k] = u + v;
f[j+k+(i>>1)] = u - v;
}
}
}
if(inv_fft){
T rev = inv(T(N));
for(int i=0; i<N; i++) f[i] *= rev;
}
}
template<int W, int M>
vector<MINT<M>> multiply_ntt(vector<MINT<M>> a, vector<MINT<M>> b){
int N = 2; while(N < a.size() + b.size()) N <<= 1;
a.resize(N); b.resize(N);
NTT<W, M>(a); NTT<W, M>(b);
for(int i=0; i<N; i++) a[i] *= b[i];
NTT<W, M>(a, true);
return a;
}
}
template<int W, int M>
struct PolyMod{
using T = MINT<M>;
vector<T> a;
// constructor
PolyMod(){}
PolyMod(T a0) : a(1, a0) { normalize(); }
PolyMod(const vector<T> a) : a(a) { normalize(); }
// method from vector<T>
int size() const { return a.size(); }
int deg() const { return a.size() - 1; }
void normalize(){ while(a.size() && a.back() == T(0)) a.pop_back(); }
T operator [] (int idx) const { return a[idx]; }
typename vector<T>::const_iterator begin() const { return a.begin(); }
typename vector<T>::const_iterator end() const { return a.end(); }
void push_back(const T val) { a.push_back(val); }
void pop_back() { a.pop_back(); }
// basic manipulation
PolyMod reversed() const {
vector<T> b = a;
reverse(b.begin(), b.end());
return b;
}
PolyMod trim(int n) const {
return vector<T>(a.begin(), a.begin() + min(n, size()));
}
PolyMod inv(int n){
PolyMod q(T(1) / a[0]);
for(int i=1; i<n; i<<=1){
PolyMod p = PolyMod(2) - q * trim(i * 2);
q = (p * q).trim(i * 2);
}
return q.trim(n);
}
// operation with scala value
PolyMod operator *= (const T x){
for(auto &i : a) i *= x;
normalize();
return *this;
}
PolyMod operator /= (const T x){
return *this *= (T(1) / T(x));
}
// operation with poly
PolyMod operator += (const PolyMod &b){
a.resize(max(size(), b.size()));
for(int i=0; i<b.size(); i++) a[i] += b.a[i];
normalize();
return *this;
}
PolyMod operator -= (const PolyMod &b){
a.resize(max(size(), b.size()));
for(int i=0; i<b.size(); i++) a[i] -= b.a[i];
normalize();
return *this;
}
PolyMod operator *= (const PolyMod &b){
*this = fft::multiply_ntt<W, M>(a, b.a);
normalize();
return *this;
}
PolyMod operator /= (const PolyMod &b){
if(deg() < b.deg()) return *this = PolyMod();
int sz = deg() - b.deg() + 1;
PolyMod ra = reversed().trim(sz), rb = b.reversed().trim(sz).inv(sz);
*this = (ra * rb).trim(sz);
for(int i=sz-size(); i; i--) push_back(T(0));
reverse(a.begin(),a.end());
normalize();
return *this;
}
PolyMod operator %= (const PolyMod &b){
if(deg() < b.deg()) return *this;
PolyMod tmp = *this; tmp /= b; tmp *= b;
*this -= tmp;
normalize();
return *this;
}
// operator
PolyMod operator * (const T x) const { return PolyMod(*this) *= x; }
PolyMod operator / (const T x) const { return PolyMod(*this) /= x; }
PolyMod operator + (const PolyMod &b) const { return PolyMod(*this) += b; }
PolyMod operator - (const PolyMod &b) const { return PolyMod(*this) -= b; }
PolyMod operator * (const PolyMod &b) const { return PolyMod(*this) *= b; }
PolyMod operator / (const PolyMod &b) const { return PolyMod(*this) /= b; }
PolyMod operator % (const PolyMod &b) const { return PolyMod(*this) %= b; }
};
constexpr int W = 3, MOD = 1e9 + 7;
using mint = MINT<MOD>;
using poly = PolyMod<W, MOD>;
mint kitamasa(poly c, poly a, ll n){
poly d = vector<mint>{1};
poly xn = vector<mint>{0, 1};
poly f;
for(int i=0; i<c.size(); i++) f.push_back(-c[i]);
f.push_back(1);
while(n){
if(n & 1) d = d * xn % f;
n >>= 1; xn = xn * xn % f;
}
mint ret = 0;
for(int i=0; i<=a.deg(); i++) ret += a[i] * d[i];
return ret;
}
long long int dp[2][51][651];
long long int c[1251];
vector <int> a = {2,3,5,7,11,13};
vector <int> b = {4,6,8,9,10,12};
long long int n,p,q;
vector <int> v;
long long int dp2[1251];
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> p >> q;
int m = p*a[5] + q*b[5];
dp[0][0][0] = 1;
dp[1][0][0] = 1;
for(int i=0;i<a.size();i++)
{
for(int j=p-1;j>=0;j--)
{
for(int k=0;k<=p*a[5];k++)
{
if(dp[0][j][k]==0) continue;
for(int l=j+1;l<=p;l++)
{
if(k + (l-j)*a[i] > p*a[5]) break;
dp[0][l][k + (l-j)*a[i]] += dp[0][j][k];
dp[0][l][k + (l-j)*a[i]]%=MOD;
}
}
}
}
for(int i=0;i<b.size();i++)
{
for(int j=q-1;j>=0;j--)
{
for(int k=0;k<=q*b[5];k++)
{
if(dp[1][j][k]==0) continue;
for(int l=j+1;l<=q;l++)
{
if(k + (l-j)*b[i] > q*b[5]) break;
dp[1][l][k + (l-j)*b[i]] += dp[1][j][k];
dp[1][l][k + (l-j)*b[i]]%=MOD;
}
}
}
}
for(int i=0;i<=p*a[5];i++)
{
for(int j=0;j<=q*b[5];j++)
{
if(i+j > m) continue;
c[i+j] += ((dp[0][p][i]*dp[1][q][j])%MOD);
c[i+j]%=MOD;
}
}
dp2[0] = 1;
for(int i=0;i<=m;i++)
{
for(int j=0;j<=m;j++)
{
if(i+j > m) break;
dp2[i+j] += ((dp2[i]*c[j])%MOD);
dp2[i+j]%=MOD;
}
}
poly A,C;
for(int i=0;i<m;i++)
{
A.push_back(dp2[i]);
}
for(int i=m;i>0;i--)
{
C.push_back(c[i]);
}
mint res = 0;
long long int L = n - m;
if(L < 0) L = 0;
long long int R = n - 1;
for(long long int i=L;i<=R;i++)
{
mint val = kitamasa(C,A,i);
for(int j=0;j<=m;j++)
{
if(i+j >= n)
{
res += (val*(mint)c[j]);
}
}
}
cout << res << '\n';
return 0;
}