难难
POJ 3253 Round Numbers
求在
等价于求
分为二进制位数比
小的枚举
时间复杂度
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 30 + 10;
int n, m, binom[MAXN][MAXN];
int round(int x) {
int bit[MAXN];
memset(bit, 0, sizeof bit);
int ret = 0, sz = 0, tmp = x;
while (tmp) {
bit[++sz] = (tmp & 1);
tmp >>= 1;
}
for (int i = 2; i < sz; ++i) for (int j = (i + 1) >> 1; j <= i - 1; ++j) ret += binom[i - 1][j];
int zr = 0;
int cnt = (sz + 1) >> 1;
for (int i = sz - 1; i >= 1; --i) {
if (!bit[i]) zr++;
else {
int nzr = zr + 1;
for (int j = cnt - nzr; j <= i - 1; ++j) ret += binom[i - 1][j];
}
}
return ret;
}
int main() {
int l, r;
scanf("%d %d", &l, &r);
for (int i = 0; i < MAXN; ++i) {
binom[i][0] = 1;
for (int j = 1; j <= i; ++j) {
binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
}
}
printf("%d\n", round(r + 1) - round(l));
return 0;
}
HDU 5288 OO’s Sequence
给出序列
令
求
考虑每个数的贡献。
处理出
则每个数的贡献为
利用链表或类似思想即可。
时间复杂度
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10, P = 1e9 + 7;
int n, a[MAXN], pre[MAXN], lft[MAXN], rgt[MAXN];
vector<int> fac[MAXN];
ll ans;
void solve() {
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
memset(pre, 0, sizeof pre);
for (int i = 1; i <= n; ++i) {
int pre_pos = 0;
for (int idx = 0; idx < fac[a[i]].size(); ++idx) { int _fac = fac[a[i]][idx];
if (pre[_fac]) pre_pos = max(pre_pos, pre[_fac]);
}
lft[i] = pre_pos;
pre[a[i]] = i;
}
memset(pre, 0, sizeof pre);
for (int i = n; i >= 1; --i) {
int pre_pos = n + 1;
for (int idx = 0; idx < fac[a[i]].size(); ++idx) { int _fac = fac[a[i]][idx];
if (pre[_fac]) pre_pos = min(pre_pos, pre[_fac]);
}
rgt[i] = pre_pos;
pre[a[i]] = i;
}
int ans = 0;
for (int i = 1; i <= n; ++i) (ans += 1ll * (i - lft[i]) * (rgt[i] - i) % P) %= P;
printf("%d\n", ans);
}
int main() {
for (int i = 1; i <= 10000; ++i) {
for (int j = 1; j * j <= i; ++j) if (i % j == 0) fac[i].push_back(j), fac[i].push_back(i / j);
}
while (scanf("%d", &n) != EOF) {
solve();
}
return 0;
}
POJ 2142 The Balence
给出
的一组解,满足
不妨设
exgcd 得出通解
由于
即
时间复杂度
#include <cstdio>
#include <algorithm>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll _abs(ll x) { return x < 0 ? -x : x; }
pll exgcd(ll a, ll b) {
if (b == 0) return mp(1, 0);
pll tmp = exgcd(b, a % b);
pll res = mp(tmp.second, tmp.first - a / b * tmp.second);
return res;
}
ll a, b, c;
void solve() {
bool flg = false;
if (a < b) swap(a, b), flg = true;
ll g = gcd(a, b);
if (c % g) { puts("no solution"); return ; }
pll sol = exgcd(a, b);
ll x = sol.first, y = sol.second;
x *= c / g, y *= c / g;
ll t = y * g / a;
ll ansx = 0x7fffffff, ansy = 0x7fffffff;
for (ll i = t - 10; i <= t + 10; ++i) {
if (_abs(x + b / g * i) + _abs(y - a / g * i) < ansx + ansy) {
ansx = _abs(x + b / g * i), ansy = _abs(y - a / g * i);
}
}
if (flg) printf("%lld %lld\n", ansy, ansx);
else printf("%lld %lld\n", ansx, ansy);
}
int main() {
while (scanf("%lld %lld %lld", &a, &b, &c) && (a && b && c)) solve();
return 0;
}
一个重要的思想。
SGU 141 Jumping Joe
给出
首先求出通解,使得
时间复杂度
#include <bits/stdc++.h>
#define mkpir make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll a, b, k, p;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
pll exgcd(ll a, ll b) {
if (b == 0) return mkpir(1, 0);
pll tmp = exgcd(b, a % b);
return mkpir(tmp.second, tmp.first - a / b * tmp.second);
}
int pd(ll x) { return x & 1; }
int main() {
scanf("%lld %lld %lld %lld", &a, &b, &p, &k);
bool flg = false;
if (a < b) swap(a, b), flg = true;
ll g = gcd(a, b);
if (p % g) { puts("NO"); return 0; }
pll sol = exgcd(a, b);
ll x = sol.first * p / g, y = sol.second * p / g;
ll t = y * g / a;
for (ll i = t - 50; i <= t + 50; ++i) {
ll nx = x + b / g * i, ny = y - a / g * i;
if (abs(nx) + abs(ny) > k) continue;
if (!pd(nx + ny - k)) {
ll ans1, ans2, ans3, ans4;
ll del = k - abs(nx) - abs(ny);
if (nx < 0) {
nx = -nx;
ans2 = nx + del / 2, ans1 = del / 2;
} else ans1 = nx + del / 2, ans2 = del / 2;
if (ny < 0) {
ny = -ny;
ans4 = ny, ans3 = 0;
} else {
ans3 = ny, ans4 = 0;
}
puts("YES");
return flg ? printf("%lld %lld %lld %lld\n", ans3, ans4, ans1, ans2) & 0 : printf("%lld %lld %lld %lld\n", ans1, ans2, ans3, ans4) & 0;
}
}
puts("NO");
return 0;
}
F Joseph's Problem
求
利用数论分块:
则可以
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, k, ans;
int main() {
scanf("%lld %lld", &n, &k);
for (ll l = 1; l <= min(n, k); ) {
ll r = k / (k / l);
r = min(n, r);
ll val = k / l;
ans += (r - l + 1) * k - val * (l + r) * (r - l + 1) / 2;
l = r + 1;
}
if (n > k) ans += k * (n - k);
printf("%lld\n", ans);
return 0;
}
HDU 3398 String
用
考虑坐标轴:填一个 1 就向右走一格,填 2 向上走一格。
则题目为从
易知总方案数为
对于一个不合法方案,将
故答案为
化简一下式子得到答案为
考虑到这题模数不是质数,不能直接求逆元。则通过枚举质数计算分子分母在该质数上的指数即可。
时间复杂度
#include <cstdio>
#include <cassert>
using namespace std;
typedef long long ll;
const int PRMCNT = 1348764 + 10, RANGE = 2000000 + 10, P = 20100501;
int n, m;
ll ans;
int prime[PRMCNT], cnt, not_prime[RANGE];
void getprime() {
for (int i = 2; i <= 2000000; ++i) {
if (!not_prime[i]){
prime[++cnt] = i;
for (int j = i + i; j <= 2000000; j += i) not_prime[j] = true;
}
}
}
int getnum(int p, int n) { // 一个有用的 trick,计算 n! 在质数 p 上的指数
int ans = 0;
while (n) n /= p, ans += n;
return ans;
}
int qpower(int a, int x) {
int ret = 1;
for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? ret = 1ll * ret * a % P : 0;
return ret;
}
void solve() {
ans = 1;
scanf("%d %d", &n, &m);
int nm = n + 1 - m;
for (int i = 1; i <= cnt && prime[i] <= n + m; ++i) {
int cur = 0;
while (nm % prime[i] == 0) nm /= prime[i], cur ++;
cur += getnum(prime[i], n + m), cur -= getnum(prime[i], n + 1), cur -= getnum(prime[i], m);
ans = 1ll * ans * qpower(prime[i], cur) % P;
}
printf("%lld\n", ans);
}
int main() {
getprime();
int t; scanf("%d", &t);
while (t --) solve();
return 0;
}
坐标转换与组合计数!
还有一个高爸的回答,可以看看 :thinking: