結果

問題 No.502 階乗を計算するだけ
ユーザー iiljjiiljj
提出日時 2020-04-09 01:09:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 1,000 ms
コード長 14,816 bytes
コンパイル時間 2,976 ms
コンパイル使用メモリ 202,036 KB
最終ジャッジ日時 2025-01-09 15:15:51
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* #region Head */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;
template <class T, class U> using um = unordered_map<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;

#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))
#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))
#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))
#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))
#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))
#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define ALL(x) begin(x), end(x)
#define SIZE(x) ((ll)(x).size())
#define PERM(c)                                                                                                        \
    sort(ALL(c));                                                                                                      \
    for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))
#define UNIQ(v) v.erase(unique(ALL(v)), v.end());

#define endl '\n'
#define sqrt sqrtl
#define floor floorl
#define log2 log2l

constexpr ll INF = 1'010'000'000'000'000'017LL;
constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.14159265358979323846;

template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力
    for (T &x : vec) is >> x;
    return is;
}
template <typename T> ostream &operator<<(ostream &os, vc<T> &vec) { // vector 出力 (for dump)
    os << "{";
    REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T> ostream &operator>>(ostream &os, vc<T> &vec) { // vector 出力 (inline)
    REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");
    return os;
}

template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力
    is >> pair_var.first >> pair_var.second;
    return is;
}
template <typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &pair_var) { // pair 出力
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

// map, um, set 出力
template <class T> ostream &out_iter(ostream &os, T &map_var) {
    os << "{";
    REPI(itr, map_var) {
        os << *itr;
        auto itrcp = itr;
        if (++itrcp != map_var.end()) os << ", ";
    }
    os << "}";
    return os;
}
template <typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) { return out_iter(os, map_var); }
template <typename T, typename U> ostream &operator<<(ostream &os, um<T, U> &map_var) { return out_iter(os, map_var); }
template <typename T> ostream &operator<<(ostream &os, set<T> &set_var) { return out_iter(os, set_var); }

// dump
#define DUMPOUT cerr
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) DUMPOUT << ", ";
    dump_func(move(tail)...);
}

// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {
    if (comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {
    if (comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// ローカル用
#define DEBUG_

#ifdef DEBUG_
#define DEB
#define dump(...)                                                                                                      \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                                                                    \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl                                        \
            << "    ",                                                                                                 \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif

struct AtCoderInitialize {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    AtCoderInitialize() {
        ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH) cout << unitbuf;
    }
} ATCODER_INITIALIZE;

string yes = "Yes", no = "No";
// string yes = "YES", no = "NO";

/* #endregion */

struct mint {
    ll x;
    mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}
    mint &operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint &operator-=(const mint a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint &operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    // O(log(t))
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1); // ⌊t/2⌋ 乗
        a *= a;               // ⌊t/2⌋*2 乗
        if (t & 1)            // ⌊t/2⌋*2 == t-1 のとき
            a *= *this;       // ⌊t/2⌋*2+1 乗 => t 乗
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(MOD - 2); // オイラーの定理から， x^(-1) ≡ x^(p-2)
    }
    mint &operator/=(const mint a) { return (*this) *= a.inv(); }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
    bool operator==(const mint a) const { return this->x == a.x; }
    bool operator==(const ll a) const { return this->x == a; }

    // mint 入力
    friend istream &operator>>(istream &is, mint &x) {
        is >> x.x;
        return is;
    }

    // mint 出力
    friend ostream &operator<<(ostream &os, mint x) {
        os << x.x;
        return os;
    }
};

constexpr ll _sx = 11;
constexpr ll _sy = 92;
constexpr ll _x = 8;
constexpr ll _y = 15;
struct Dec {
    vll str2vll(string &s) { return vcs2vll(split(dec(s))); }
    string dec(const string &encoded) {
        const string table0("0123456789,"),
            table1("!#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}~");
        ll sz = SIZE(encoded), tmp;
        assert(sz % _x == 0);
        string ret;
        vll map1(256);
        REP(i, 0, SIZE(table1)) map1[table1[i]] = i;
        REPD(i, 0, sz, _x) {
            tmp = 0;
            REP(cur, i, i + _x) tmp = _sy * tmp + map1[encoded[cur]];
            REP(cur, 0, _y) ret.push_back(table0[tmp % _sx]), tmp /= _sx;
        }
        return ret;
    }
    vc<string> split(const string &s, char delim = ',') {
        vc<string> elems;
        string item;
        for (char ch : s) {
            if (ch == delim) {
                if (!item.empty()) elems.push_back(item);
                item.clear();
            } else {
                item += ch;
            }
        }
        if (!item.empty()) elems.push_back(item);
        return elems;
    }
    vll vcs2vll(const vc<string> &v) {
        vll ret(SIZE(v));
        REP(i, 0, SIZE(v)) ret[i] = stoll(v[i]);
        return ret;
    }
    vll dif2vc(vll &v) {
        ll sz = SIZE(v);
        vll ret(sz);
        ret[0] = v[0];
        REP(i, 1, sz) ret[i] = ret[i - 1] + v[i];
        return ret;
    }
};

// Problem
void solve() {
    string ss = "`hPDga*vEtD;P/&PAuxoON-adWSZAn:U.,<p]/PS]j<*2?eAF%W1s|i'8o}ld4)X?okv,NLkLwpfnXNQ3W*RRM[l^V}66ptW#w$k"
                "w^d5H)]*OHW9+6;'?=O%%=Ex,UA4`$e-e9V@Nbxt,%dWOizYv2F$>)kL2(d?P=^h|=6^&l}P`P`.@%S7volw5[&mJO3*b!SX!FA["
                "BE%B|db4a%X33L4v/}?H8;lFZ+<s/B}OP=70e?!(G%,O!mBvK5.eZO&tTVFWU7y8gd$)-b$@8g-kv!WfgvK9N(-z9slgXYB.lyr("
                "8%La]DnX|F=1J:?KJAf<dAIU[>%D:1e568*.j^2]'6>ABnXh~G/gk47Tj?b#W*|K.%CDj(_:j'7~7}Zr;@%KM<AGWFk+;]Bv{}DW"
                ";z;3%q?RedZoFXo>UBJZ!LHG$OqAB>!f:,W|Ncbt_2eCRo@Teo585x6:R^{Q)}K:H@>;}AC=),kA,Z5gIWtFg9`>K%9K0YiM?Rq)"
                "i`V/N{ICF~sr]zqET+zaaIhB0C29AD9k2>poStJu=0f'<8>3#<.zCQ?Hi6evBuo69aJi&=UDs]]P*Ft^B4.}24=vp;wz5WgH-r'9"
                "&sE@+8nNK%fwc{Oq0Yp7ynM5T(#NJq5.0u_xXYjD!rj^?gpgbYTbs1lbB6_]w~L#>vvD[q|m3QfOf_!d1dM31bXG%H}wx}/$B[H9"
                "h>}elW5(>$H~G`+n|C{8gC3J$DxYZAT80nYpm4J_QL#)==](G$m?J9f!)Cm=`AkLv(&NI~nUh@a.RSQ`alVB7t![DQSo>+stC+.t"
                "ch%~H65o2X'TN<qCc,Z25P7l^<1.h#58UkZgbn`9Xw}wIT}~aV~}@#oR;LdiWwYq;ln7y9z-6SgKdw&D$q()Z)%9gsB2KpY3LlFX"
                "(?MbX4s1v,}4C:~m0CeZ*E.I.q?L.oP8L5P($*H67B&e@gv-P=my3q-fQ||;;+N9baJi70Ia#7p=l5RhB9RH;s~MV>O-g55Oc)!&"
                "ROkH2YgPldL7y?'kM(#'4g6[Q:;J&}(7M$H,92hw--+$nEh!E+1dt>N%Gc9]v(_]IPy@^wRQJ2?DZofJ#RJwr|4)4TafgQqaHM1Z"
                "YDy.CF-}[3AuaG#7<wNJc?f}00Z,;67GONPNOhO+u,;icR2(^/LrB._%k4Ob,Tfg1)3{A68w>7TO?DA80`NA3F9_H=PV/oF$x2+f"
                "SvyNn)/G%v-q=23&N_L5?c`|gMM=8hvK.*u]^p@!c?-l/^M5A'C;h$TE-f_Dr*$x!Hdz5|S@NRiHJA`ePXY|d_O*e23PiUS&Kr5e"
                "9vLn$=s]X(DReWJ|`qJrbA[-1pV*MAI{vIzmb[_|]iPi?z0$9rFIF!=McZRtU/b-VS#()xGGL/Z;&7gWH734b[N{y01Ka3E6AOA?"
                "Kb2+]^ma3W!4S]FdYM<]=%t>ME+&%EprP|cHZ|*8dqFETRyQ$mQ3w{?]8aW,MwA+@dShd}J@'P6O)xUr`nl_CvM3HnR4f+];F=EV"
                "088zd0W*~;9uQal7oPb4`k0ligUzeXP,y<C[hj4n=k1A+D7D$+b%lqSPvQk2!%)0<$uNj>Aj0X)1MRU0mWDqla57(iNH9+3i;&,y"
                "k15DKWoKP^(MmV47i6Q{H5MS&_Ng}~*pkx#&(4N5^6Wv05:sgL3+ShUR;dT_Ddy#m)!:}=mwVO;Op$8!<Z;8><X]dmYz{X0mf_!z"
                "*$n`J|?iOES2e3j!8`~*?<o|{6w6U@t6<amI:5gAwv=qTg+?aCG946Ko828Yc?>$2#_Z.vo4Ld1-$M$:TBbw0];#;D^2:M4TL?zm"
                "!^2:R_WtJ,4b+l^[GV4mF!>tL^6LU4d<3,JC;]tx>w(d&*]L^OGpPE4>KvhyiP}f;lXz6ugdBVR=YezG/>B:YsCf>Y.BK3&S%'rM"
                ")_i;%~SQK4N-50l`!ujVAYWq0y}CPC2&0@pxOy8%9XIJ_##daC;+cLdN>.VU3?BHxRO;-SZ[L~0T?&(G/b>H!5`nf0S/*!O]L!!M"
                "K){Nu%qTDi^*NB9EPs=r)&=o^=1=DxrZb7c|92K!RoG0}YVeb__8L-E-X{_0~ziE;U'>^La?_C[74%}5*>Pk%!B!*zjZqXZ}gZUt"
                "N861[;c/MVI,j^GlHI*+$tmKr<eDhGnO..VmG?Ghs?x@i];]o_i.++Prd.R)h3Ky_K:ga/YpB{pHl:flA-#T;QK}SyCokT^`w8xI"
                "@]s5E,@n]/9hCW~7VQl+50e&VToh9EBD@!EFAj't?%>(q18m1c628X8WfJ8&P0T{?yu}6pUs>K]YPF+yVmsCC@ULfHoykndV8Ub)"
                "E^Op^D%mpL6%-s2ApUs5_[>D]K)$f4YI>>h2-ea7x2g=TFU%U?5-T,?Xb/YBf%HnB=ZkHB[Uv),sADE@'Hcd9FdLbb]Ue({1-Q9%"
                "?^L@2]<f>)<ZQx7(NzLVEh)0Qj53rS9<2s>:'EF).F,i.Gu=YWd<[X,`;VnpMeJ/`nz[x1@K'lKG7KthZ*6pec(cUwA0^F`~DDAa"
                "gbew0a6^6+rn#;Z$E%`(hjyF[q:&$u3s1WM3gxtb:[<F1M[N+lKFZvQ7q.<75>U|TT&&&xrpF1a]ZO1~7nP]FOT!N!v:#xH=s|xe"
                "K[sL8HK!@[sB,u*nB[f8(8Zg8LfS43#(c]w%/~Y:Zh,x?yS2XwYfG!c/kw>->n$s#Lk.G,`hhPi)6{-A,=f%cgM)O/WVwpIEA(cW"
                "+n$=L&oa%dG?ME{F</>}.|6v(S*Y;U1[dQ;nI58r_rOqE)OzV,rP]KZ=LqoT9r_'oj.]dfSD,3z5j)i^tDl7/hBQum-5haN)L@%L"
                "6Z}`BEJ&iF`s3:Ip=Zpr8ydXk:#bAkm|4^3.Axaqi5rEnd$(<5;i-oN7g?cTeTH0Fo,-Ys?mkluX9{/I`B@5fJ.+l2jNbS%::kqX"
                "PHJ%iJ{I:9IoMg7DJD0.hRYiohwA(!;Y+6~~j1q:q5)*IBewW'0IhQ@|4Na+2q[Y,^^fiq`<@pfebgCuJ_Tml.&-{4QvTmb-E+sv"
                "l|Lt^}TJ4Ai`QV<kg6R,,Li8ZBqhW:bPWxYGT(&(4g'cn<#fWz#5WSW#ByvJtPUk9NvCe<IY@EMsin2PMXuybQ$YUE0+fu?|*i}!"
                "rtN<eW8;1@#046dH-%*m4@`UZlCO%:&&b7&:.^vF:M5ZQpC?Z`t4Q{#PS3S2=tld%S:tDf649)m!Jxa:i)t5UrJR!b.y#s`t4]d-"
                "NF)Hv_>[Vlj7mzuaj$}>{)&/^y1-s2qFk,L!8adcQn~/8y%5_fn$2h<xcK?Sgu32QV=[Sw+j:uwj%'twCqT%$3h~R%a<SW=V%(un"
                "=9/m$D2ez?lCG+.fwuCZ$Qap{2$E5l@Q<ro6IiaJg#-/E7G~cy[KB#GEIgH4(.cy.#U_bY2Ko=Z[8q%a&g[bI.w(^N$j?%hIh240"
                "VvZ*`P-M#nZvM*jz]N4WCHF1G8&`jUq@i#6-VR@1?M>QTx'#j2dFkVkX]cP+@&8rdI4fN`5B<Nnl#ByjSZrYj>g/YN]hQB(saJt:"
                ">ok9MPW]d`?{!pT=TQxea3U:%BdfN+NmZZ`qJ/r)fT)JT7l`5is*9uHASB>p''h]b+`gGNtR^uwdBFw?,T#,:9X]{D%d4{%hrp}G"
                "%xV;2n1waEv!,iWv/d1nG.1>Ej^/I$/.RV/EH-e/>(JQgWoKP{<{J'>rE0q0+2~`A$U-3X]<DR`O'(-tiZZ_SHA9OCB$O&4'<}+Y"
                "2/9!DlAK?l!1fX^6u5hYS8!6rGOZCg/hCOn#54;7;k1uX;pT=%Li1<)K_|P#fMIIGd1%PI0+(`PdfwwH1?T&=Gq/t9R/QT/GkFVC"
                "2V=jyeu`Co>7mUT+2Td-6v:^Cf3c0p,^8CG,o+vu65t>].ja4d792ymBCSpCI,muLolL?U>+fL/~`LordfMmo%l=<qv@Gq<{9R(T"
                "<JER5ze&!/q22$8?h@3vX5G]UBM>5!JRr]Xe6?;=RS&fW.cC{X)0.BPDShW5eh@O9+nxU{x$E2,HM0yk:}<=IWmEp`#C]uB@>99l"
                "4Ssg/rjO4+Hqkh|5Tbe}|[]4`{y?}+R#:glc/f!]^U1-'39<-Rn{xlB:'2<Vo}@C_8yRpF:q=DE!OOj@5b=Z5VO3)]tA%dr;7O-`"
                "#3jK+v38eAPVX{TlazQqO*EZC1]+E+QMu5>f#.o^|PA1aJ{i(l_]0ZpoRSHn6ca,+nDxWRn'^U.p#^#*&wDGBWAuVs=OH%n/byJ8"
                "_kWGg>rN.K=1w~}B`/N'-OA:!Ng$i;~0<abUE-]l^iz6~TMBX$K<5s8LGi1eWtG_Q=>1BJJQ8%!qqiG|/B!Lyo%;#..1!/R$fh'G"
                "0#*ON<+UNCJ5Q/hK[hMiIjgs:7;&`1k2Bobb0&Do)=R/2aTSqGj2/atzz*g-+:%{Dp58DC2!pfKG<:x~|U>h>i+/Qz9?BVP]qGwi"
                "7B>HbW_.b'i;O_/O9({2mQ8n3_o{PTIA)%zPKImw!,9>aE5%l)d10@a[RU*N)YF7_k/XEV%bF}*Wn>9sfwzU?5-r-8*W)Un-/(Js"
                "_gZRT:DHPQhw`'4p-,)IA4Mx/_c6X$Q+3Hz{S-5(dz}Q65OwRp;HZ6F.'nnNQKJhjm!nE]ToO$81ErI%_ju`%0Q{DC7<2(hd}-f|"
                "ZFgk0X~V$Ls)u_<HZ,+F?+u{H|X)pg!4GK+@hP.,e3oGl'esK0a4S,!M]idsMs|-1SB6PE0C&u~iw<zO+~f%4Ltb&>5w05EbU(!#"
                "7ztEcmQeG%&s5>`EY{{uG9mt5Wamh7u(dH}s@)z,R~L+kXPGP19{,+^VED]OfSh3QgLI42Q3Vkm&CT!ML19<cTkB+2s>`/Becq=v"
                "'/0gZOn/f}rL6NfdNk;[ojbEf`(iCX0M#@N)|q~B/-:{spX$54J{=})2Q,G]6m9lQp@y6[o(6$u&5j]nZ5xSL%$^H|]#qraxT!lV"
                "d|hY<;':[+cK#PBGpt3v6zhxR@a0gHe*eK|/8LT8y_3pl`3vQctK;6,.`AW)_d@uI;:PO+#rI`NV9RIv,X7NF@f%3fyU8[&Z$@N%"
                "j9]08@)u8,LlxQ/Sff&V`gRwO*ujGJ&QCvq}l^'n?,AyP(ilQ#y4d9GZNs.=a%M[_!'9**:6:GnEz,0T,M6ER(t+^Xm`OBepQ#j:"
                "C^EoKeh6{weOL%uYe'A^;O2sc@/@:*cxs}O`]?,%QOOs:+s_.EsR9CLQ|Fz)$K!K6*%S]u[Y8LzpT)NcchwY,0lkK<@qU>KPIJY_"
                "Kn[g,z!:T[x1<CwhU=*X]LA[K[mgdgm'MGD)0m9v^Kq#7SV8h4g]^S9^@rXbWYJ.jq.D:2b3";

    Dec dec;
    vll facs = dec.str2vll(ss);

    ll n;
    cin >> n;
    if (n >= (ll)1e9 + 7) {
        cout << 0 << endl;
        return;
    }
    ll q = n / ((ll)1e6);

    mint ret = 1;
    if (q > 0) ret *= facs[q - 1];
    REPM(i, ((ll)1e6) * q + 1, n) ret *= i;
    cout << ret << endl;
}

// entry point
int main() {
    solve();
    return 0;
}
0