Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using pld = pair<ld, ld>;
- #define fi first
- #define se second
- #define left BAO
- #define right ANH
- #define pb push_back
- #define pf push_front
- #define mp make_pair
- #define ins insert
- #define btpc __builtin_popcount
- #define btclz __builtin_clz
- #define sz(x) (int)(x.size());
- #define all(x) x.begin(), x.end()
- #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
- int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
- int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
- template<class X, class Y>
- bool minimize(X &x, const Y &y) {
- if (x > y)
- {
- x = y;
- return true;
- }
- return false;
- }
- template<class X, class Y>
- bool maximize(X &x, const Y &y) {
- if (x < y)
- {
- x = y;
- return true;
- }
- return false;
- }
- const int MOD = 1e9 + 7; //998244353
- template<class X, class Y>
- void add(X &x, const Y &y) {
- x = (x + y);
- if(x >= MOD) x -= MOD;
- }
- template<class X, class Y>
- void sub(X &x, const Y &y) {
- x = (x - y);
- if(x < 0) x += MOD;
- }
- /* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
- const ll INF = 1e9;
- const int N = 1e6 + 10;
- template <typename T> T mod_inv_in_range(T a, T m) {
- // assert(0 <= a && a < m);
- T x = a, y = m;
- T vx = 1, vy = 0;
- while (x) {
- T k = y / x;
- y %= x;
- vy -= k * vx;
- std::swap(x, y);
- std::swap(vx, vy);
- }
- assert(y == 1);
- return vy < 0 ? m + vy : vy;
- }
- template <typename T> T mod_inv(T a, T m) {
- a %= m;
- a = a < 0 ? a + m : a;
- return mod_inv_in_range(a, m);
- }
- template <int MOD_> struct modnum {
- static constexpr int MOD = MOD_;
- static_assert(MOD_ > 0, "MOD must be positive");
- using ll = long long;
- int v;
- public:
- modnum() : v(0) {}
- modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
- explicit operator int() const { return v; }
- friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
- friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
- friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
- friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
- modnum inv() const {
- modnum res;
- res.v = mod_inv_in_range(v, MOD);
- return res;
- }
- friend modnum inv(const modnum& m) { return m.inv(); }
- modnum neg() const {
- modnum res;
- res.v = v ? MOD-v : 0;
- return res;
- }
- friend modnum neg(const modnum& m) { return m.neg(); }
- modnum operator- () const {
- return neg();
- }
- modnum operator+ () const {
- return modnum(*this);
- }
- modnum& operator ++ () {
- v ++;
- if (v == MOD) v = 0;
- return *this;
- }
- modnum& operator -- () {
- if (v == 0) v = MOD;
- v --;
- return *this;
- }
- modnum& operator += (const modnum& o) {
- v -= MOD-o.v;
- v = (v < 0) ? v + MOD : v;
- return *this;
- }
- modnum& operator -= (const modnum& o) {
- v -= o.v;
- v = (v < 0) ? v + MOD : v;
- return *this;
- }
- modnum& operator *= (const modnum& o) {
- v = int(ll(v) * ll(o.v) % MOD);
- return *this;
- }
- modnum& operator /= (const modnum& o) {
- return *this *= o.inv();
- }
- friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
- friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
- friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
- friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
- friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
- friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
- };
- using num = modnum<MOD>;
- struct Query {
- int n, k, id;
- bool operator < (const Query & temp) const {
- return n < temp.n;
- }
- } query[N];
- num f[N], invf[N];
- int prime[N], cnt[N];
- num res[N];
- num power(num a, ll b) {
- if(b == 0) return 1;
- num ans = power(a, b / 2);
- ans = ans * ans;
- if(b & 1) ans = ans * a;
- return ans;
- }
- void BaoJiaoPisu() {
- int q; cin >> q;
- for(int i = 1; i <= q; i++) {
- cin >> query[i].n >> query[i].k;
- query[i].id = i;
- }
- sort(query + 1, query + 1 + q);
- int iter = 0;
- int n = 1e6;
- for(int i = 2; i <= n; i++) prime[i] = i;
- for(int i = 2; i <= n; i++) {
- if(prime[i] == i) {
- for(int j = i * 2; j <= n; j += i) prime[j] = i;
- }
- }
- f[0] = 1;
- for(int i = 1; i <= n; i++) f[i] = f[i - 1] * i;
- invf[n] = 1 / f[n];
- for(int i = n - 1; i >= 0; i--) invf[i] = invf[i + 1] * (i + 1);
- auto C = [&](int n, int k) -> num {
- if(n < k || k < 0) return 0;
- return f[n] * invf[k] * invf[n - k];
- };
- auto S = [&](int n, int k) -> num {
- //Stirling number of the second kind
- if(n < k || k < 0) return 0;
- num ans = 0;
- for(int i = 0; i <= k; i++) {
- if(i & 1) ans -= C(k, i) * power(k - i, n);
- else ans += C(k, i) * power(k - i, n);
- }
- ans /= f[k];
- return ans;
- };
- int cp = 0;
- num ans = 1;
- for(int i = 1; i <= q; i++) {
- while(iter < query[i].n) {
- ++iter;
- int x = iter;
- while(x > 1) {
- int p = prime[x];
- if(cnt[p]) ans /= cnt[p];
- cnt[p]++;
- ans *= cnt[p];
- x /= p;
- }
- if(prime[iter] == iter) ++cp;
- }
- // cout << ans << endl;
- // num t = 0;
- // for(int j = 1; j <= query[i].k; j++) t += S(cp, j);
- res[query[i].id] += (S(cp, query[i].k) + S(cp, query[i].k - 1)) * ans;
- }
- for(int i = 1; i <= q; i++) {
- cout << res[i] << '\n';
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //online
- #endif
- int tc = 1, ddd = 0;
- // cin >> tc;
- while(tc--) {
- //ddd++;
- //cout << "Case #" << ddd << ": ";
- BaoJiaoPisu();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement