题解 | 前缀平方和序列

#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long ll; 

const ll p = 1000000007;

ll fast_pow_mod(ll base, ll exp, ll p) {
	ll ans = 1;
	while (exp > 0) {
		if(exp & 1) ans = (ans * base) % p;
		base = (base * base) % p;
		exp >>= 1;
	}
	return ans;
}

//计算m * (m - 1) * ... *(m - n + 1)  
ll factorial(ll m, ll n, ll p) {
	ll result = 1;
	while (n-- > 0) {
		result = (result * m) % p;
		m--;
	}
	return result;
}
//提醒大家注意精度，建议全long long得了
int main() {
	ll n, x;
	cin >> n >> x;
	ll m;
	m = sqrt(x);
	//C m n
	ll a = factorial(m, n, p);
	ll b = factorial(n, n, p);
	ll inverse = fast_pow_mod(b, p - 2, p);
	cout << (a * inverse) % p << endl;
}