首页 > 代码库 > Spoj 9887 Binomial coefficients 构造
Spoj 9887 Binomial coefficients 构造
题目链接:点击打开链接
#include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int MAX_N = 507; const long long INF = (long long)1e15; typedef long long ll; typedef pair<ll,ll> pii; ll C[MAX_N][MAX_N]; vector<pii> ord; ll get(ll nn, int m, ll A) { ll ret = 1; for (int i = 0; i < m; ++i) { if (ret > (A + nn + i - 1) / (nn + i)) return A + 1; ret *= (nn + i); } return ret; } void pre(ll n) { ll nn = n; for (int i = 1; i < 7; ++i) { nn *= i; ll l = 1, r = INF; while (l <= r) { ll mid = (l + r) >> 1; ll ans = get(mid, i, nn); if (ans > nn) r = mid - 1; else if (ans < nn) l = mid + 1; else { ord.push_back(make_pair(mid + i - 1, i)); if (mid - 1 != i) ord.push_back(make_pair(mid + i - 1, mid - 1)); break; } } } } int main() { int T; scanf("%d", &T); while (T-- > 0) { ll n; cin >> n; ord.clear(); pre(n); C[0][0] = 1; for (int i = 1; i < MAX_N; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; ++j) { C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; if (C[i][j] > n) break; if (C[i][j] == n) { ord.push_back(make_pair(i, j)); if (i - j != j) { ord.push_back(make_pair(i, i - j)); } } } } sort(ord.begin(), ord.end()); ord.erase(unique(ord.begin(), ord.end()), ord.end()); int len = (int)ord.size(); printf("%d\n", len); for (int i = 0; i < len; ++i) { if (i == 0) printf("(%lld,%lld)", ord[i].first, ord[i].second); else printf(" (%lld,%lld)", ord[i].first, ord[i].second); } puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。