2017CCPC_final补

划水划水划水……然后就挂了……

D.Mr. Panda and Circles

分三种情况讨论:
两端都没有圆在线段外
一端有圆在线段外
两端都有圆在线段外
……然后就是各种前缀和优化组合数求方案了
第三种情况要用到任意模数的fft,然后还要写个前缀和减去自身卷积自身的情况……
因为组合数太大了,所以还需要考虑单独维护模数的幂……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
//created by missever
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int add(int x, int y) {
x += y;
if(x >= mod) x -= mod;
return x;
}
int fmod(LL x) {
return x - x / mod * mod;
}
int mul(int x, int y) {
return fmod(1LL * x * y);
}
int powt(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = mul(r, a);
a = mul(a, a);
b >>= 1;
}
return r;
}
int sqr(int x) {
return fmod(1LL * x * x);
}
const int LN = 18;
const int N = 1 << LN;
const double pi = acos(-1.0);
int fa[N], fb[N];
struct Complex {
double r, i;
Complex(double r = 0.0, double i = 0.0): r(r), i(i) {};
Complex operator + (const Complex &rhs) {
return Complex(r + rhs.r, i + rhs.i);
}
Complex operator - (const Complex &rhs) {
return Complex(r - rhs.r, i - rhs.i);
}
Complex operator * (const Complex &rhs) {
return Complex(r * rhs.r - i * rhs.i, i * rhs.r + r * rhs.i);
}
Complex conj() {
return Complex(r, -i);
}
} wn[N];
int bitrev[N];
void fft_prepare() {
for(int i = 0; i < N; i++) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (LN - 1));
for(int i = 0; i < N; i++) wn[i] = Complex(cos(2 * pi * i / N), sin(2 * pi * i / N));
}
void FFT(Complex a[], int l, int op) {
int d = 0;
while((1 << d) * l != N) d++;
for(int i = 0; i < l; i++) {
if(i < (bitrev[i] >> d)) swap(a[i], a[(bitrev[i] >> d)]);
}
for (int i = 2; i <= l; i <<= 1) {
int lyc = N / i;
for (int j = 0; j < l; j += i) {
Complex *l = a + j, *r = a + j + (i >> 1), *p = wn;
for(int k = 0; k < (i >> 1); k++) {
Complex tmp = *r * *p;
*r = *l - tmp, *l = *l + tmp;
++l, ++r, p += lyc;
}
}
}
if(op == -1) {
for(int i = 0; i < l; i++) {
a[i].r /= l;
a[i].i /= l;
}
}
}
Complex va[N], vb[N], da[N], db[N], dd[N];
void Conv(int fa[], int fc[], int l) {
int i;
for(i = 0; i < l; i++) va[i] = Complex(fa[i] & 32767, fa[i] >> 15);
FFT(va, l, 1);
for(i = 0; i < l; i++) {
int j = (l - i) & (l - 1);
Complex qa, qb, qc, qd;
qa = (va[i] + va[j].conj()) * Complex(0.5, 0.0);
qb = (va[i] - va[j].conj()) * Complex(0.0, -0.5);
da[j] = qa * qa;
db[j] = qa * qb;
dd[j] = qb * qb;
}
for(i = 0; i < l; i++) va[i] = da[i] + db[i] * Complex(0.0, 1.0);
for(i = 0; i < l; i++) vb[i] = db[i] + dd[i] * Complex(0.0, 1.0);
FFT(va, l, -1);
FFT(vb, l, -1);
for(i = 0; i < l; i++) {
int wa = fmod(va[i].r + 0.5);
int wb = fmod(va[i].i + 0.5);
int wc = fmod(vb[i].r + 0.5);
int wd = fmod(vb[i].i + 0.5);
fc[i] = add(wa, add(fmod(((LL)add(wb, wc)) << 15), fmod(((LL)wd) << 30)));
}
}
struct node {
int res, cnt;
void init(LL a, LL b) {
res = 1;
cnt = 0;
while(a <= b) {
int c = fmod(a);
if(c == 0) cnt++;
else res = mul(res, c);
a++;
}
}
int val() {
return cnt ? 0 : res;
}
void add(LL x) {
x = fmod(x);
if(x == 0) cnt++;
else res = mul(res, x);
}
void del(LL x) {
x = fmod(x);
if(x == 0) cnt--;
else res = mul(res, powt(x, mod - 2));
}
} fac;
int a[maxn], r[maxn];
int solve() {
int n, i, x, y, l, rmax = 0, ans = 0;
P u;
LL m, d, s = 0;
scanf("%d%lld", &n, &m);
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
s += a[i];
rmax = max(rmax, a[i]);
}
s *= 2;
d = m - 1 - s;
// step1
if(d > 0) {
fac.init(d + 1, d + n);
ans = add(ans, mul(sqr(fmod(d)), fac.val()));
}
// step2
memset(r, 0, sizeof(r));
for(i = 0; i < n; i++) r[a[i]]++;
for(i = 100000; i > 0; i--) r[i] += r[i + 1];
i = min(max(0LL, -d), 200000LL);
fac.init(d + i + 1, d + i + n - 1);
for(i = i + 1, y = 0; i <= 100000; i++) {
fac.add(d + i + n - 1);
fac.del(d + i);
if(r[i]) y = add(y, mul(r[i], mul(fac.val(), sqr(fmod(d + i)))));
}
ans = add(ans, mul(y, 2));
// step3
if(n == 1) return ans;
for(l = 1; l <= (rmax << 1); l <<= 1);
memcpy(fa, r, sizeof(r));
if(l > maxn) fill(fa + maxn,fa + l,0);
Conv(fa, fb, l);
memset(fa, 0, sizeof(fa));
for(i = 0; i < n; i++) {
fa[2]++;
fa[a[i] + 2] -= 2;
fa[(a[i] << 1) + 2]++;
}
for(x = y = i = 0; i < l; i++) {
x = add(x, mod + fa[i]);
y = add(x, y);
fb[i] = add(fb[i], mod - y);
}
i = min(max(0LL, -d), 500000LL);
fac.init(d + i + 1, d + i + n - 2);
for(i = i + 1; i < l; i++) {
fac.add(d + i + n - 2);
fac.del(d + i);
if(fb[i]) ans = add(ans, mul(fb[i], mul(fac.val(), sqr(fmod(d + i)))));
}
return ans;
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int t, i;
fft_prepare();
scanf("%d", &t);
for(i = 1; i <= t; i++) printf("Case #%d: %d\n", i, solve());
return 0;
}

F.Fair Lottery

把等式转化成不等式,直接线性规划莽……
不过这个单纯形的板子过不了uoj179的$hack$数据…………似乎没有太大影响?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//created by missever
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1050;
const double eps = 1e-8;
struct Simplex {
int n, m;
int idx[maxn], idy[maxn];
double a[maxn][maxn], ans[maxn];
void init(int _n, int _m) {
n = _n;
m = _m;
for(int i = 0; i <= n; i++) idx[i] = i;
for(int i = 1; i <= m; i++) idy[i] = i + n;
}
void pivot(int u, int v) {
swap(idx[v], idy[u]);
double t = a[u][v];
a[u][v] = 1.0;
for(int i = 0; i <= n; i++) a[u][i] /= t;
for(int i = 0; i <= m; i++) {
if(i == u || fabs(a[i][v]) < eps) continue;
t = a[i][v];
a[i][v] = 0;
for(int j = 0; j <= n; j++) a[i][j] -= a[u][j] * t;
}
}
bool init_check() {
while(true) {
int u = 0, v = 0;
double mn = -eps;
for(int i = 1; i <= m; i++) {
if(a[i][0] < mn && (!u || (rand() & 1))) {
mn = a[i][0];
u = i;
}
}
if(!u) return true;
mn = -eps;
for(int i = 1; i <= n; i++) {
if(a[u][i] < mn && (!v || (rand() & 1))) {
mn = a[u][i];
v = i;
}
}
if(!v) return false;
pivot(u, v);
}
}
bool do_simplex() {
while(true) {
int u = 0, v = 0;
double mn = 1e15, mx = eps;
for(int i = 1; i <= n; i++) {
if(a[0][i] > mx && (!v || (rand() & 1))) {
mx = a[0][i];
v = i;
}
}
if(!v) return true;
for(int i = 1; i <= m; i++) {
if(a[i][v] > eps && a[i][0] / a[i][v] < mn) {
mn = a[i][0] / a[i][v];
u = i;
}
}
if(!u) return false;
pivot(u, v);
}
}
void get_ans() {
memset(ans, 0, sizeof(ans));
ans[0] = -a[0][0];
for(int i = 1; i <= m; i++) {
if(idy[i] <= n) ans[idy[i]] = a[i][0];
}
}
} sf;
int d[15], f[12][1050];
double solve() {
int n, m, i, j, x, tot = 0;
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++) scanf("%d", &d[i]);
memset(f, 0, sizeof(f));
for(i = 0; i < (1 << n); i++) {
for(j = x = 0; j < n; j++) {
if((i >> j) & 1) x += d[j];
}
if(x <= m) {
tot++;
for(j = 0; j < n; j++) {
if((i >> j) & 1) f[j][tot] = 1;
}
}
}
sf.init(tot, n + 2);
for(i = 0;i <= tot; i++) sf.a[0][i] = f[0][i];
for(i = 1;i < n; i++) {
for(j = 0;j <= tot; j++) sf.a[i][j] = f[i][j] - f[i - 1][j];
}
for(j = 0;j <= tot; j++) sf.a[n][j] = f[0][j] - f[n - 1][j];
for(j = 1;j <= tot; j++) {
sf.a[n + 1][j] = 1;
sf.a[n + 2][j] = -1;
}
sf.a[n + 1][0] = 1;
sf.a[n + 2][0] = -1;
sf.init_check();
sf.do_simplex();
return -sf.a[0][0];
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
srand(time(NULL));
int t, i;
scanf("%d", &t);
for(i = 1; i <= t; i++) printf("Case #%d: %.10f\n", i, solve());
return 0;
}

H.Equidistance

先求出$m-1$个线性无关的基向量,然后随机一个向量尝试把这组基向量扩展到满秩即可……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//created by missever
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const double eps = 1e-8;
inline sgn(double x) {
if(x < -eps) return -1;
else if(x > eps) return 1;
else return 0;
}
int n, m;
struct Point {
vector<double> a;
Point operator +(const Point &b) const {
Point c;
c.a.resize(n);
for(int i = 0; i < n; i++) c.a[i] = a[i] + b.a[i];
return c;
}
Point operator -(const Point &b) const {
Point c;
c.a.resize(n);
for(int i = 0; i < n; i++) c.a[i] = a[i] - b.a[i];
return c;
}
double operator *(const Point &b) const {
double res = 0;
for(int i = 0; i < n; i++) res += a[i] * b.a[i];
return res;
}
Point operator *(const double &b) const {
Point c = *this;
for(int i = 0; i < n; i++) c.a[i] *= b;
return c;
}
} p[105], f[105], s, us;
uniform_real_distribution<double> df(-100, 100);
default_random_engine gen(time(NULL));
Point work() {
Point x;
x.a.resize(n);
while(true) {
for(int i = 0; i < n; i++) x.a[i] = df(gen);
for(int i = 1; i < m; i++) {
double u = x * f[i];
x = x - f[i] * u;
}
if((x * x) > eps) return x;
}
}
void solve() {
int i, j;
double u;
scanf("%d%d", &n, &m);
printf("%d\n", n + 1 - m);
s.a.clear();
s.a.resize(n,0);
for(i = 0; i < m; i++) {
p[i].a.resize(n);
for(j = 0; j < n; j++) scanf("%lf", &p[i].a[j]);
s = s + p[i];
}
us = s * (1.0 / m);
for(i = 1; i < m; i++) {
f[i] = p[i] - us;
for(j = 1; j < i; j++) {
u = f[i] * f[j];
f[i] = f[i] - f[j] * u;
}
u = sqrt(f[i] * f[i]);
f[i] = f[i] * (1.0 / u);
}
while(m < n + 1) {
p[m] = work();
u = sqrt(p[m] * p[m]);
double v = sqrt(1.0 - (p[0] - us) * (p[0] - us));
p[m] = p[m] * (v / u) + us;
for(i = 0; i < n; i++) printf("%.10f%c", p[m].a[i], " \n"[i + 1 == n]);
f[m] = p[m] - us;
u = sqrt(f[m] * f[m]);
f[m] = f[m] * (1.0 / u);
s = s + p[m];
us = s * (1.0 / (++m));
}
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int i, t;
scanf("%d", &t);
for(i = 1; i <= t; i++) {
printf("Case #%d: ", i);
solve();
}
return 0;
}