T1 CF607E Cross Sum
有n条直线，这些直线有若干的交点，求这些交点到一给定点的距离的前m小的和。
n <= 5e4 , m <= 3e7;
先二分一个半径，以给定点为圆心，r为半径作出一个圆，使得这个圆里恰好包住m个点，
之后统计答案即可。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
const long double eps = 1e-8;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n , m , tot;
long double A , B;
int tr[N] , lst[N] , L[N] , R[N];
long double k[N] , b[N];
struct node { long double ang; int id; }s[N];
void Add(int pos , int val) { if(pos <= 0) return ; while(pos <= tot) tr[pos] += val , pos += (pos & (-pos)); }
int Ask(int pos) { if(pos <= 0) return 0; int ans = 0; while(pos) ans += tr[pos] , pos -= (pos & (-pos)); return ans; }
long double sqr(long double k) { return k * k; }
inline bool cmp(const node &A , const node &B) { return A.ang < B.ang; }
bool check(long double r)
{
int sum = 0; tot = 0;
for(int i = 1 ; i <= n ; ++i)
{
long double A = sqr(k[i]) + 1 , B = 2 * k[i] * b[i] , C = b[i] * b[i] - r * r;
if(sqr(B) - 4 * A * C < eps) continue;
long double tmp = sqrt(sqr(B) - 4 * A * C);
long double x1 = (-B + tmp) / (2 * A) , x2 = (-B - tmp) / (2 * A);
long double y1 = k[i] * x1 + b[i] , y2 = k[i] * x2 + b[i];
s[++tot] = (node){ atan2(y1 , x1) , i }; s[++tot] = (node) { atan2(y2 , x2) , i }; // 求交点，按极角排序
}
sort(s + 1 , s + 1 + tot , cmp);
for(int i = 1 ; i <= tot ; ++i) // 类比扫描线
if(lst[s[i].id])
sum += Ask(i) - Ask(lst[s[i].id]) , Add(lst[s[i].id] , -1) , lst[s[i].id] = 0;
else lst[s[i].id] = i , Add(i , 1);
return sum < m;
}
long double calc(int i , int j)
{
long double x = (b[j] - b[i]) / (k[i] - k[j]);
long double y = x * k[i] + b[i];
return sqrt(sqr(x) + sqr(y));
}
int main()
{
n = read(); cin >> A >> B; A /= 1000; B /= 1000; m = read();
for(int i = 1 ; i <= n ; ++i) cin >> k[i] >> b[i] , k[i] /= 1000 , b[i] /= 1000;
for(int i = 1 ; i <= n ; ++i) b[i] += k[i] * A - B; // 转成以 A，B为原点
long double l = 0 , r = 1e10 , mid; int cnt = 100;
while(cnt--)
{
mid = (l + r) / 2;
if(check(mid)) l = mid; else r = mid;
}
check(l);
int j = 0; cnt = 0; long double ans = 0;
for(int i = 1 ; i <= tot ; ++i) // 同样是类比扫描线
{
if(lst[s[i].id])
{
int k;
for(k = j ; k > lst[s[i].id] ; k = L[k]) cnt++ , ans += calc(s[i].id , s[k].id);
R[L[k]] = R[k]; L[R[k]] = L[k];
if(k == j) j = L[j];
}
else
R[j] = i , L[i] = j , j = i , lst[s[i].id] = i;
}
double Ans = ans + (m - cnt) * l;
printf("%.15f
" , Ans);
return 0;
}
T2AT5202 [AGC038E] Gachapon
有一个随机数生成器，生成[0,n-1]之间的整数，其中生成ii的概率为(frac{A_i}{S}(S=sum A_i))。
再给你一个数组(B_0,B_1dots B_{n-1})。
这个随机数生成器不断生成随机数，一旦(forall iin[0,n-1])，i这个数至少出现了B_i次，就停止生成，否则继续生成。
现在想问你，期望生成随机数的次数是多少，输出答案对998244353取模的结果。
数据范围：400。
min-max 容斥。
小R问： 啊， 这题很好，但是我又不想写题解，题解太难写了，怎么办。
小Q说： 放个链接吧。
于是乎LINK
推荐第三篇题解。
关于那个式子，就是min-max套路+选择本集合期望步数+排列数+概率
关于那么用了一堆全都不够的来统计答案，想知道为什么可以考虑一个有向图，。，，
emmm.... 就这样。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int mod = 998244353;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n , sa , sb;
int a[420] , b[420] , f[420][420][420] , inv[420] , fac[420];
inline int add(int a , int b) { a += b; return a >= mod ? a - mod : a; }
inline int mul(int a , int b) { return (LL)a * b % mod; }
inline int ksm(int a , int k) { int ans = 1; for( ; k ; k >>= 1 , a = mul(a , a)) if(k & 1) ans = mul(ans , a); return ans; }
int main()
{
n = read();
for(int i = 1 ; i <= n ; ++i) sa += (a[i] = read()) , sb += (b[i] = read());
inv[0] = fac[0] = 1;
for(int i = 1 ; i <= 400 ; ++i) fac[i] = mul(fac[i-1] , i);
inv[400] = ksm(fac[400] , mod - 2);
for(int i = 399 ; i ; --i) inv[i] = mul(inv[i+1] , i+1);
f[0][0][0] = mod - 1;
for(int i = 1 ; i <= n ; ++i)
for(int j = 0 ; j <= sa ; ++j)
for(int k = 0 ; k <= sb ; ++k) if(f[i-1][j][k])
{
f[i][j][k] = add(f[i][j][k] , f[i-1][j][k]);
int res = 1;
for(int l = 0 ; l < b[i] ; ++l , res = mul(res , a[i]))
f[i][j + a[i]][k + l] = add(f[i][j + a[i]][k + l] , mod - mul(f[i-1][j][k] , mul(res , inv[l])));
}
int ans = 0;
for(int i = 1 ; i <= sa ; ++i)
{
int y = ksm(i , mod - 2);
int x = mul(sa , y);
for(int j = 0 ; j <= sb ; ++j , x = mul(x , y)) ans = add(ans , mul(fac[j] , mul(x , f[n][i][j])));
}
cout << ans << '
';
return 0;
}
T3AT4512 [AGC030C] Coloring Torus
构造一个n * n矩阵最大是500 * 500，要求1 ~ k （k <= 1000） 全都出现，且相同数的四周出现数的种类和数量一样。
对于 k <= 500 可以
1 1 1 1 1 1
2 2 2 2 2 2
k k k k k k k
对于k > 500
考虑往斜着的主对角线里插值，隔一个插一个。
1 2 3 4 ... n
2 3 4 ... n 1
3 4 ... n 1 2
4 ... n 1 2 3
. ... . . . .
. ... . . . .
. ... . . . .
n 1 2 . . . n-1
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int k = read();
int ans[520][520] , nex[520];
int main()
{
if(k <= 500)
{
cout << k << '
';
for(int i = 1 ; i <= k ; ++i) for(int j = 1 ; j <= k ; ++j) cout << i << (j == k ? '
' : ' ');
return 0;
}
else
{
cout << 500 << '
'; k -= 500; int id = 0;
for(int i = 1 ; i <= 500 ; ++i) nex[i] = i + 1; nex[500] = 1;
for(int i = 1 ; i <= 500 ; ++i)
{
int a = ++id , b = (k == 0 ? id : ++id); if(a != b) k--;
for(int x = 1 , y = i ; x <= 500 ; x++ , y = nex[y])
ans[x][y] = x & 1 ? a : b;
}
for(int i = 1 ; i <= 500 ; ++i) for(int j = 1 ; j <= 500 ; ++j) cout << ans[i][j] << (j == 500 ? '
' : ' ');
}
return 0;
}