Submission #34960041

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint1000000007;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

mint low[40000]; // low[x] = f(x), // sqrt(1e9)
mint high[40000]; // high[x] = f(M/x)

int main() {
  int N = read();
  int M = read();
  ll L = llround(sqrt(M));
  ll K = M / (L + 1);
  rep(i,1,L+K+1){ // [1..L]:1..L,  [L+1...L+K] : M/K .. M/1
    int x = i <= L ? i : M / (L + K + 1 - i);
    mint sum = N;
    int l = 2;
    while(l <= min(N,x)){ // 暴力 f(x) = (n + f(x/2)+..+f(x/n))/(n-1)
      int q = x / l;
      int r = min(N, x / q) + 1; // x/[l..r) = q
      mint cur = q <= L ? low[q] : high[M / q];
      sum += cur * (r - l);
      l = r;
    }
    (i <= L ? low[i] : high[L + K + 1 - i]) = sum / (N - 1);
  }
  printf("%d\n",(M <= L ? low[M] : high[1]).val());
}

Submission Info

Submission Time
Task Ex - Dice Product 2
User cromarmot
Language C++ (GCC 9.2.1)
Score 600
Code Size 903 Byte
Status AC
Exec Time 516 ms
Memory 4144 KiB

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:8:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    8 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 5
AC × 56
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 01_small_05.txt, 01_small_06.txt, 01_small_07.txt, 01_small_08.txt, 01_small_09.txt, 01_small_10.txt, 01_small_11.txt, 01_small_12.txt, 01_small_13.txt, 01_small_14.txt, 01_small_15.txt, 01_small_16.txt, 01_small_17.txt, 01_small_18.txt, 01_small_19.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 03_max_00.txt, 03_max_01.txt, 03_max_02.txt, 03_max_03.txt, 03_max_04.txt, 03_max_05.txt, 04_boundary_A_00.txt, 04_boundary_A_01.txt, 04_boundary_A_02.txt, 04_boundary_A_03.txt, 04_boundary_A_04.txt, 04_boundary_A_05.txt, 04_boundary_A_06.txt, 04_boundary_A_07.txt, 04_boundary_A_08.txt, 04_boundary_A_09.txt, 05_boundary_B_00.txt, 05_boundary_B_01.txt, 05_boundary_B_02.txt, 05_boundary_B_03.txt, 05_boundary_B_04.txt, 05_boundary_B_05.txt, 05_boundary_B_06.txt, 05_boundary_B_07.txt, 05_boundary_B_08.txt, 05_boundary_B_09.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 7 ms 4068 KiB
00_sample_01.txt AC 2 ms 4068 KiB
00_sample_02.txt AC 2 ms 3952 KiB
00_sample_03.txt AC 2 ms 4088 KiB
00_sample_04.txt AC 512 ms 4020 KiB
01_small_00.txt AC 3 ms 4072 KiB
01_small_01.txt AC 2 ms 4020 KiB
01_small_02.txt AC 2 ms 4092 KiB
01_small_03.txt AC 2 ms 3956 KiB
01_small_04.txt AC 2 ms 4020 KiB
01_small_05.txt AC 2 ms 3952 KiB
01_small_06.txt AC 2 ms 4020 KiB
01_small_07.txt AC 2 ms 4088 KiB
01_small_08.txt AC 2 ms 4096 KiB
01_small_09.txt AC 2 ms 4092 KiB
01_small_10.txt AC 3 ms 4024 KiB
01_small_11.txt AC 2 ms 4064 KiB
01_small_12.txt AC 2 ms 3968 KiB
01_small_13.txt AC 2 ms 3968 KiB
01_small_14.txt AC 2 ms 4124 KiB
01_small_15.txt AC 2 ms 3944 KiB
01_small_16.txt AC 2 ms 4016 KiB
01_small_17.txt AC 2 ms 4064 KiB
01_small_18.txt AC 2 ms 4064 KiB
01_small_19.txt AC 2 ms 3960 KiB
02_random_00.txt AC 438 ms 4124 KiB
02_random_01.txt AC 364 ms 4064 KiB
02_random_02.txt AC 482 ms 3872 KiB
02_random_03.txt AC 391 ms 3952 KiB
02_random_04.txt AC 422 ms 4072 KiB
03_max_00.txt AC 513 ms 3956 KiB
03_max_01.txt AC 514 ms 4096 KiB
03_max_02.txt AC 511 ms 4072 KiB
03_max_03.txt AC 510 ms 3868 KiB
03_max_04.txt AC 516 ms 3988 KiB
03_max_05.txt AC 509 ms 4068 KiB
04_boundary_A_00.txt AC 91 ms 4144 KiB
04_boundary_A_01.txt AC 90 ms 4068 KiB
04_boundary_A_02.txt AC 91 ms 3988 KiB
04_boundary_A_03.txt AC 92 ms 4068 KiB
04_boundary_A_04.txt AC 89 ms 3948 KiB
04_boundary_A_05.txt AC 188 ms 3944 KiB
04_boundary_A_06.txt AC 181 ms 3956 KiB
04_boundary_A_07.txt AC 183 ms 3952 KiB
04_boundary_A_08.txt AC 185 ms 3972 KiB
04_boundary_A_09.txt AC 185 ms 4020 KiB
05_boundary_B_00.txt AC 155 ms 3956 KiB
05_boundary_B_01.txt AC 156 ms 4064 KiB
05_boundary_B_02.txt AC 156 ms 4092 KiB
05_boundary_B_03.txt AC 156 ms 3968 KiB
05_boundary_B_04.txt AC 161 ms 4016 KiB
05_boundary_B_05.txt AC 186 ms 3956 KiB
05_boundary_B_06.txt AC 182 ms 3948 KiB
05_boundary_B_07.txt AC 181 ms 3972 KiB
05_boundary_B_08.txt AC 184 ms 4064 KiB
05_boundary_B_09.txt AC 182 ms 3868 KiB