#164559 (C++14) No.502 階乗を計算するだけ

提出ソース

結果

問題	No.502 階乗を計算するだけ
ユーザー	koyumeishi
提出日時	2017-04-07 23:08:38
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	54 ms / 1,000 ms
コード長	6,701 bytes
コンパイル時間	926 ms
コンパイル使用メモリ	108,244 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-16 02:55:45
合計ジャッジ時間	2,490 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	1 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	1 ms 6,944 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	1 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	1 ms 6,940 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	7 ms 6,944 KB
testcase_23	AC	3 ms 6,944 KB
testcase_24	AC	5 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	3 ms 6,944 KB
testcase_27	AC	3 ms 6,944 KB
testcase_28	AC	4 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	6 ms 6,944 KB
testcase_31	AC	4 ms 6,940 KB
testcase_32	AC	33 ms 6,940 KB
testcase_33	AC	52 ms 6,944 KB
testcase_34	AC	47 ms 6,944 KB
testcase_35	AC	52 ms 6,944 KB
testcase_36	AC	28 ms 6,940 KB
testcase_37	AC	54 ms 6,940 KB
testcase_38	AC	24 ms 6,940 KB
testcase_39	AC	46 ms 6,944 KB
testcase_40	AC	10 ms 6,944 KB
testcase_41	AC	2 ms 6,944 KB
testcase_42	AC	2 ms 6,940 KB
testcase_43	AC	2 ms 6,940 KB
testcase_44	AC	2 ms 6,944 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	1 ms 6,940 KB
testcase_47	AC	2 ms 6,944 KB
testcase_48	AC	1 ms 6,940 KB
testcase_49	AC	1 ms 6,940 KB
testcase_50	AC	2 ms 6,940 KB
testcase_51	AC	2 ms 6,940 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator   end(){ return range_iterator(  end_, step_); } };

  inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

  mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

  template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }

  inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}
constexpr long long mod = 9_ten + 7;

vector<pair<long long,long long>> ans = {
  { 0 , 1 },
{ 10000000 , 682498929 },
{ 20000000 , 491101308 },
{ 30000000 , 76479948 },
{ 40000000 , 723816384 },
{ 50000000 , 67347853 },
{ 60000000 , 27368307 },
{ 70000000 , 625544428 },
{ 80000000 , 199888908 },
{ 90000000 , 888050723 },
{ 100000000 , 927880474 },
{ 110000000 , 281863274 },
{ 120000000 , 661224977 },
{ 130000000 , 623534362 },
{ 140000000 , 970055531 },
{ 150000000 , 261384175 },
{ 160000000 , 195888993 },
{ 170000000 , 66404266 },
{ 180000000 , 547665832 },
{ 190000000 , 109838563 },
{ 200000000 , 933245637 },
{ 210000000 , 724691727 },
{ 220000000 , 368925948 },
{ 230000000 , 268838846 },
{ 240000000 , 136026497 },
{ 250000000 , 112390913 },
{ 260000000 , 135498044 },
{ 270000000 , 217544623 },
{ 280000000 , 419363534 },
{ 290000000 , 500780548 },
{ 300000000 , 668123525 },
{ 310000000 , 128487469 },
{ 320000000 , 30977140 },
{ 330000000 , 522049725 },
{ 340000000 , 309058615 },
{ 350000000 , 386027524 },
{ 360000000 , 189239124 },
{ 370000000 , 148528617 },
{ 380000000 , 940567523 },
{ 390000000 , 917084264 },
{ 400000000 , 429277690 },
{ 410000000 , 996164327 },
{ 420000000 , 358655417 },
{ 430000000 , 568392357 },
{ 440000000 , 780072518 },
{ 450000000 , 462639908 },
{ 460000000 , 275105629 },
{ 470000000 , 909210595 },
{ 480000000 , 99199382 },
{ 490000000 , 703397904 },
{ 500000000 , 733333339 },
{ 510000000 , 97830135 },
{ 520000000 , 608823837 },
{ 530000000 , 256141983 },
{ 540000000 , 141827977 },
{ 550000000 , 696628828 },
{ 560000000 , 637939935 },
{ 570000000 , 811575797 },
{ 580000000 , 848924691 },
{ 590000000 , 131772368 },
{ 600000000 , 724464507 },
{ 610000000 , 272814771 },
{ 620000000 , 326159309 },
{ 630000000 , 456152084 },
{ 640000000 , 903466878 },
{ 650000000 , 92255682 },
{ 660000000 , 769795511 },
{ 670000000 , 373745190 },
{ 680000000 , 606241871 },
{ 690000000 , 825871994 },
{ 700000000 , 957939114 },
{ 710000000 , 435887178 },
{ 720000000 , 852304035 },
{ 730000000 , 663307737 },
{ 740000000 , 375297772 },
{ 750000000 , 217598709 },
{ 760000000 , 624148346 },
{ 770000000 , 671734977 },
{ 780000000 , 624500515 },
{ 790000000 , 748510389 },
{ 800000000 , 203191898 },
{ 810000000 , 423951674 },
{ 820000000 , 629786193 },
{ 830000000 , 672850561 },
{ 840000000 , 814362881 },
{ 850000000 , 823845496 },
{ 860000000 , 116667533 },
{ 870000000 , 256473217 },
{ 880000000 , 627655552 },
{ 890000000 , 245795606 },
{ 900000000 , 586445753 },
{ 910000000 , 172114298 },
{ 920000000 , 193781724 },
{ 930000000 , 778983779 },
{ 940000000 , 83868974 },
{ 950000000 , 315103615 },
{ 960000000 , 965785236 },
{ 970000000 , 492741665 },
{ 980000000 , 377329025 },
{ 990000000 , 847549272 },
{ 1000000000 , 698611116 },
{ 1000000007 , 0 }
};

int main(){
  long long n;
  cin >> n;

  if( n >= mod ){
    println(0);
    return 0;
  }

  long long v = 1;
  int i=0;
  while( ans[i+1].first < n ) i++;
  v = ans[i].second;
  for(long long k=ans[i].first+1; k<=n; k++){
    (v *= k) %= mod;
  }

  println(v);


  // vector<pair<long long,long long>> res;
  // res.push_back({0,1});
  // long long f = 1;
  // for(long long i=1; i<mod; i++){
  //   (f *= i) %= mod;
  //   if(i%10000000 == 0){
  //     res.push_back({i, f});
  //   }
  // }

  // for(auto p : res){
  //   println( "{", p.first, ",", p.second, "}" );
  // }


  return 0;
}

yukicoder

結果

テストケース

ソースコード