-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathCF - 1174E.cc
66 lines (55 loc) · 1.64 KB
/
CF - 1174E.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// This problem can also be solved without DP using only combinatorics.
// This is DP based solution
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define fr(i,j,k) for(i = j; i < (k); i++)
#define all(x) x.begin(), x.end()
#define el '\n'
#define remax(a,b) a = max(a, b)
#define remin(a,b) a = min(a, b)
#define sz(x) int32_t(x.size())
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<pii> vpi;
// --------------------------- TEMPLATE ENDS -------------------------------------
const int mod = 1e9+7;
const int NN = 1e6 + 2;
int dp2[NN][20][2];
void solve(){
int i = 0, j = 0, k = 0, n = 0, m = 0;
cin >> n;
int pow2 = 0;
for(; (1<<(pow2 + 1)) <= n; pow2++);
if((1<<(pow2 - 1)) * 3 <= n)
dp2[1][pow2 - 1][1] = 1;
dp2[1][pow2][0] = 1;
for(int len = 2; len <= n; len++) {
// for pow3 = 1
for(int x = 0; x < pow2; x++) {
int &v = dp2[len][x][1];
v = dp2[len - 1][x + 1][1] * 1LL * (n/((1<<x) * 3) - n/((1<<(x + 1)) * 3)) % mod;
v = (v + (dp2[len - 1][x][1] * 1LL * (n/((1<<x) * 3) - len + 1) % mod)) % mod;
}
// for pow3 = 0
for(int x = 0; x < pow2; x++) {
int &v = dp2[len][x][0];
v = dp2[len - 1][x + 1][0] * 1LL * (n/(1<<x) - n/(1<<(x+1))) % mod;
v = (v + (dp2[len - 1][x][0] * 1LL * (n/(1<<x) - len + 1) % mod)) % mod;
v = (v + (dp2[len - 1][x][1] * 1LL * (n/(1<<x) - n/((1<<x) * 3)) % mod)) % mod;
}
}
cout << dp2[n][0][0] << el;
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
solve();
return 0;
}