제출 #22324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22324		- - - - - - - List of honorable mention follows - - - - - - - (#40)	Fully Generate (KRIII5_FG)	C++98	7 / 7	409 ms	252020 KiB

FG

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

const int mmod = 1000000007;
const int m = 32000000;

int G[m+1], H[m+1];

int pw(int a, int b) {
  if (b == 0) return 1;
  int c= pw(a, b/2);
  c = (1LL * c*c) % mmod;
  if (b % 2)
    c = (1LL * a * c) % mmod;
  return c;
}

int main()
{
  G[1] = 1;
  G[2] = G[3] = 2;
  for (int i=3, j=4; ;) {
    for (int iter=0; iter<G[i]; iter++) {
      G[j++] = i;
      if (j == m) break;
    }
    if (j == m) break;
    i ++;
  }

/*  long long sum = 0;
  for (int i=0; i<m/2; i++) sum += G[i];
  printf("%lld\n", sum);*/

  long long n;
  cin >> n;

  long long precalc = 1;
  int end_i = 0;
  if (n >= 336795949707LL) {
    n -= 336795949707LL;
    end_i = 15999999;
    precalc = 496411188;
  }

  for (int i=end_i+1; n; i++) {
    int iter = min((long long)G[i], n);
    n -= iter;
    if (!H[iter]) H[iter] = i;
    else H[iter] = (H[iter] * 1LL * i) % mmod;
  }

  int res = 1;
  int now = 1;
  for (int i=m; i>=1; i--) {
    if (H[i]) now = (now * 1LL * H[i]) % mmod;
    res = (res * 1LL * now) % mmod;
  }
  cout << (res * precalc) % mmod << endl;
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5