Sep 15, 2019 由 小羊
考虑分情况不同做法。当 时,枚举 ,则根据不等式解出满足条件的 。当 ,考虑枚举不合法的方案数,即形如 的方案数,不等式左边可以通过FFT取得,然后前缀和再枚举 容斥掉即可。
大力施加常数优化,AC仅需1256ms啦啦啦~
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef complex<double> cplx;
int revs[1<<19], A[300010]; cplx wmks[1<<19];
const double PI = acos(-1.0);
void dft(cplx a[], int DFT, int N) {
int *rev = revs + N;
for (int i = 0; i < N; i++)
if (i < revs[N+i]) swap(a[i], a[rev[i]]);
for (int m = 2, m2 = 1; m <= N; m <<= 1, m2 <<= 1) {
cplx *wmk = wmks + m + (DFT==-1 ? m2 : 0), u, t;
for (int k = 0; k < N; k += m)
for (int j = 0; j < m2; j++)
t = wmk[j] * a[k+j+m2], u = a[k+j],
a[k+j] = u + t, a[k+j+m2] = u - t;
}
if (DFT == -1) for (int i = 0; i < N; i++) a[i] /= N;
}
int a[100010], b[100010], c[100010];
lld solveWithFFT(int n)
{
static cplx f[262144], g[262144], h[262144];
static lld bc[262144], ac[262144], ab[262144];
int ma = 0, mb = 0, mc = 0, md, len = 1; cplx tmp, tmp2;
for (int i = 0; i < n; i++) ma = max(ma, a[i]), mb = max(mb, b[i]), mc = max(mc, c[i]);
md = max(ma+mb, max(mb+mc, mc+ma)) + 2; while (len < md) len <<= 1;
for (int i = 0; i < len; i++) f[i] = g[i] = h[i] = 0;
for (int i = 0; i < n; i++) f[a[i]] += 1, g[b[i]] += 1, h[c[i]] += 1;
dft(f, 1, len), dft(g, 1, len), dft(h, 1, len);
for (int i = 0; i < len; i++) tmp = f[i] * g[i], tmp2 = g[i] * h[i], g[i] = f[i] * h[i], f[i] = tmp2, h[i] = tmp;
dft(f, -1, len), dft(g, -1, len), dft(h, -1, len);
for (int i = 0; i < len; i++) bc[i] = f[i].real()+0.2, ac[i] = g[i].real()+0.2, ab[i] = h[i].real()+0.2;
for (int i = 1; i < len; i++) bc[i] += bc[i-1], ac[i] += ac[i-1], ab[i] += ab[i-1];
lld ans = 1LL * n * n * n;
for (int i = 0; i < n; i++)
{
if (c[i] <= len) ans -= ab[c[i]-1];
if (b[i] <= len) ans -= ac[b[i]-1];
if (a[i] <= len) ans -= bc[a[i]-1];
}
return ans;
}
inline int abs(int x) { return x < 0 ? -x : x; }
lld solveWithBruteForce(int n)
{
for (int i = 0; i <= 200001; i++) A[i] = 0;
for (int i = 0; i < n; i++) A[c[i]]++;
for (int i = 1; i <= 200001; i++) A[i] += A[i-1];
lld ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
ans += A[a[i]+b[j]] - A[max(abs(a[i]-b[j])-1,0)];
return ans;
}
void solve(int cas)
{
int n; scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
printf("Case #%d: %lld\n", cas, n <= 1000 ? solveWithBruteForce(n) : solveWithFFT(n));
}
int main()
{
for (int N = 2, N2 = 1; N <= (1<<18); N <<= 1, N2 <<= 1)
{
int *rev = revs + N; cplx *wmk = wmks + N;
for (int i = 0; i < N; i++)
rev[i] = (rev[i>>1]>>1)|((i&1)?N2:0);
for (int i = 0; i < N2; i++)
wmk[i] = cplx(cos(PI*i/N2), sin(PI*i/N2));
for (int i = 0; i < N2; i++)
wmk[i+N2] = cplx(wmk[i].real(), -wmk[i].imag());
}
int T; scanf("%d", &T);
for (int i = 1; i <= T; i++) solve(i);
return 0;
}
首先发现是几个本质不同的方案的排列,于是想到打表。需要一个快速出结果的剪枝。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MOD = 1e9+7;
int n, jspx[3010], val[3010];
lld fac[3010], inv[3010], invs[3010], ans;
void dfs(int cur, int last, lld mul, int sum)
{
if (cur == n)
{
if (mul == sum)
{
for (int i = 1; i <= n; i++)
if (jspx[i])
printf("%dx%d ", jspx[i], i);
printf("\n");
lld tot = fac[n];
for (int i = 1; i <= n; i++)
tot = tot * invs[jspx[i]] % MOD;
ans = (ans + tot) % MOD;
}
}
else if (mul * pow(last, n-cur) <= sum + last * (n - cur))
{
for (int i = last; i <= n; i++)
{
val[cur] = i;
jspx[i]++;
dfs(cur + 1, i, mul * i, sum + i);
jspx[i]--;
}
}
}
int main()
{
fac[0] = fac[1] = invs[0] = invs[1] = inv[1] = 1;
for (int i = 2; i < 3010; i++)
fac[i] = i * fac[i-1] % MOD,
inv[i] = (MOD-MOD/i) * inv[MOD%i] % MOD,
invs[i] = invs[i-1] * inv[i] % MOD;
scanf("%d", &n);
dfs(0, 1, 1, 0);
printf("ANS = %lld\n", ans);
return 0;
}
不知道题解在写什么鬼东西……
考虑 中的每个数字 的排列型生成函数。如果 为奇数,则其生成函数为 ;否则只能出现偶数次,则为 。
那么答案相当于求
的 项系数。注意到 ,令 ,则可以化简为
即最后答案为
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MOD = 1e9+7, MAXN = 2e5+5;
int fac[MAXN], inv[MAXN], invs[MAXN];
int fpow(lld a, lld k)
{
lld b = 1; k %= MOD-1;
for (; k; k >>= 1, a = a * a % MOD)
if (k & 1) b = b * a % MOD;
return b;
}
void solve()
{
lld ans = 0, n; int m, k;
scanf("%lld %d", &n, &m); k = m / 2;
for (int s = 0; s <= k; s++)
ans += 1ll * fac[k] * invs[s] % MOD * invs[k-s] % MOD * fpow(2*s+(m&1), n) % MOD;
ans = ans % MOD * fpow((MOD+1)/2, k) % MOD;
printf("%lld\n", ans);
}
int main()
{
fac[0] = fac[1] = inv[1] = 1;
invs[0] = invs[1] = 1;
for (int i = 2; i < MAXN; i++)
fac[i] = 1ll * i * fac[i-1] % MOD,
inv[i] = 1ll * (MOD-MOD/i) * inv[MOD%i] % MOD,
invs[i] = 1ll * invs[i-1] * inv[i] % MOD;
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
考虑让每个矩阵只被运算一次,那么可以使用类似于分块的想法设立分界线。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 2e5+5;
unsigned lastans, seed, pow17[16], pow19[16];
char cost[MAXN];
struct matrix
{
char item[16][16];
int col[16], row[16];
// let row[k] = item[i][k], col[k] = item[k][i]
void norm()
{
for (int k = 0; k < 16; k++)
{
row[k] = col[k] = 0;
for (int i = 0; i < 16; i++)
row[k] = (row[k] << 1) | (item[i][k] & 1),
col[k] = (col[k] << 1) | (item[k][i] & 1);
}
}
matrix operator*(const matrix &b) const
{
matrix ans;
for (int i = 0; i < 16; i++)
for (int j = 0; j < 16; j++)
ans.item[i][j] = cost[col[i]&b.row[j]];
ans.norm();
return ans;
}
static matrix getOne()
{
matrix ans; memset(ans.item, 0, sizeof(ans.item));
for (int i = 0; i < 16; i++) ans.item[i][i] = 1;
ans.norm(); return ans;
}
unsigned getAns() const
{
unsigned ans = 0;
for (int i = 0; i < 16; i++)
for (int j = 0; j < 16; j++)
ans += item[i][j] * pow17[i] * pow19[j];
return ans;
}
void output() const
{
for (int i = 0; i < 16; i++)
for (int j = 0; j < 16; j++)
printf("%d%c", int(item[i][j]), " \n"[j==15]);
}
static matrix generate()
{
matrix ans;
seed ^= lastans;
for (int i = 0; i < 16; i++)
{
seed ^= seed * seed + 15;
for (int j = 0; j < 16; j++)
ans.item[i][j] = (seed >> j) & 1;
}
ans.norm();
return ans;
}
} Q[MAXN], tail;
void solve()
{
int front = 0, rear = 0, cut = 0, n; lastans = 0;
scanf("%d", &n); tail = matrix::getOne();
while (n--)
{
int t; scanf("%d %u", &t, &seed);
if (t == 1)
{
Q[rear++] = matrix::generate();
if (rear == front+1) tail = matrix::getOne(), cut = rear;
else tail = Q[rear-1] * tail;
}
else
{
front++;
if (front == cut)
{
cut = rear;
for (int i = rear-2; i >= front; i--) Q[i] = Q[i+1] * Q[i];
tail = matrix::getOne();
}
}
lastans = (front == rear) ? 0 : (tail * Q[front]).getAns();
printf("%u\n", lastans);
}
}
int main()
{
for (int sz2 = 1; sz2 < 65536; sz2 <<= 1)
for (int i = 0; i < sz2; i++)
cost[sz2+i] = cost[i] ^ 1;
pow17[0] = pow19[0] = 1;
for (int i = 1; i < 16; i++)
pow17[i] = pow17[i-1] * 17,
pow19[i] = pow19[i-1] * 19;
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
圆上整点。直接分解 然后暴力枚举点对。看题解以为卡了64倍常数,结果交了就过了(大雾)
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int,int> pear;
#define F first
#define S second
inline lld sqr(int a) { return 1ll * a * a; }
lld gcd(lld a, lld b) { return b ? gcd(b, a%b) : a; }
void gaussInteger(lld R, vector<pear> &tot)
{
auto check = [&tot] (lld r, lld rr) -> void
{
if (r == 1 || r % 4 != 1) return;
for (int n = 1; n*n*2 < r; n++)
{
int m = int(sqrt(r-n*n)+1e-5);
if (m * m + n * n != r) continue;
if (gcd(m,n) != 1 || m <= n) continue;
tot.emplace_back(rr*(m*m-n*n), 2*n*m*rr);
}
};
for (int i = 1; i * i <= R; i++)
{
if (R % i) continue;
check(R/i, i);
if (i * i != R) check(i, R/i);
}
}
void fillOver(vector<pear> &proc, int r)
{
int cnt = proc.size();
proc.resize(cnt*8+4);
for (int i = 0; i < cnt; i++)
proc[i+cnt] = pear(proc[i].S, proc[i].F);
for (int i = 0; i < 2*cnt; i++)
proc[i+cnt*2] = pear(proc[i].F, -proc[i].S),
proc[i+cnt*4] = pear(-proc[i].F, proc[i].S),
proc[i+cnt*6] = pear(-proc[i].F, -proc[i].S);
proc[cnt*8] = pear(0, r);
proc[cnt*8+1] = pear(r, 0);
proc[cnt*8+2] = pear(0, -r);
proc[cnt*8+3] = pear(-r, 0);
}
pair<pear,pear> ans[100050];
void solve()
{
vector<pear> possA, possB;
int a, b, c, tot = 0;
scanf("%d %d %d", &a, &b, &c);
gaussInteger(a, possA), gaussInteger(b, possB);
fillOver(possA, a), fillOver(possB, b);
for (auto A : possA) for (auto B : possB)
{
lld r2 = sqr(c), r3 = sqr(A.F-B.F)+sqr(A.S-B.S);
if (r2 == r3) ans[tot++] = make_pair(A, B);
}
sort(ans, ans+tot);
printf("%d\n", tot);
for (int i = 0; i < tot; i++) printf("%d %d %d %d\n", ans[i].F.F, ans[i].F.S, ans[i].S.F, ans[i].S.S);
}
int main()
{
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}