补题链接：https://codeforces.com/gym/104337
原文链接：https://www.eriktse.com/algorithm/1136.html
M. Different Billing
签到题，写几个柿子然后枚举B或C即可。
#include
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int x, y;cin >> x >> y;
for(int c = 0;c = 0)
{
cout C. Darkness I
这题是对Minecraft中无限水的拓展过程为背景的一道思维题。
先考虑一下n, m均为奇数的情况：
然后从这种情况开始，增加一列，或者增加一行，都需要多加一个黑棋子，如果同时增加一行一列，那也是只需要增加一个棋子，增加到右下角的位置即可。
所以我们按照这种构造方法输出答案即可。
#include
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;cin >> n >> m;
int res = (n + 1) / 2 + (m + 1) / 2 - 1;
if(n % 2 == 0 || m % 2 == 0)res ++;
cout J.Expansion
这题可以转化为以下题意：
一开始身上资源为0，从1号点走到n号点，每个点上有一些资源（可能为负数），每秒钟可以选择走或者不走，且每秒会得到当前点上的资源（此时的资源已经做了前缀和），为了保证每时每刻身上的资源都不为负数，请问从1走到n所需的最小时间。
我们模拟一下这个过程，如果到了某个点发现如果在当前点停留1秒会使得资源变为负数，就说明“我应该在左边的某个正数点多停留一会儿”，而为了使得停留时间最少，我会选择最大的点进行停留。
注意一些特判，题意需要保证最后在n一直停留都不会使得资源为负数，所以prefix[n]需要大于等于零，还有为了使得可以走到n，需要保证第一个非0的数为正数。
#include
#define int long long
using namespace std;
const int N = 1e6 + 9, p = 998244353;
int a[N], prefix[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 1;i > a[i];
for(int i = 1;i H.Binary Craziness
赛时卡这道题了，一直在想拆位的做法（形成惯性思维了……糟糕）。
其实这题我们可以这样想，最多m条边，也就是所有点的出度之和一定是2m，然后我们最多n个点，也就是说出度的种类数不会超过 $sqrt{2m}$ 种。因为如果要使得种类数最多，那么就是每一种都只有一个，且从小到大，出度数组排序后（长度为t）将会是1, 2, 3, 4, 5, ...其和为$frac{t(t + 1)}{2} le 2m$，所以长度t不会很大。
我们就可以根据这个原理做一个桶记录一下某个数字出现的次数，然后直接双重循环暴力写！
#include
#define int long long
using namespace std;
const int N = 1e6 + 9, p = 998244353;
int cnt[2 * N], a[N];
int f(int x, int y)
{
return (x ^ y) * (x | y) * (x & y);
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;cin >> n >> m;
for(int i = 1;i > x >> y;
a[x] ++, a[y] ++;
}
for(int i = 1;i v;
for(int i = 1;i F.Inverse Manacher
这题甚至不需要会马拉车。
题目给定一个“回文半径”的数组，要你还原还原出一种可能的字符串（仅包含ab）。数据保证至少存在一种解。
只需要理解回文半径的含义即可。
当我们走到i时，如果a[i] > 1，说明我们要把i左边的一部分堆成到右边去，为了优化复杂度，我们可以用双指针，r表示此时b数组（也就是答案数组）的大小，也就是我们更新到的右端，当r 时，我们就拓展得到b[r]，如果此时i > r，再根据一些情况来确定b[i]即可（交替的取a, b）。
注意数组开大一点，马拉车一般是两倍空间。
#include
#define int long long
using namespace std;
const int N = 3e6 + 9;
int a[N];
char b[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 0;i > a[i];
char ch = 'a';
for(int i = 0, r = 0;i r)++ r, b[r] = b[2 * i - r];
if(i == 0)b[i] = '&';
else if(i & 1)b[i] = '|';
else if(b[i] == 0)b[i] = ch, ch = (ch == 'a' ? 'b' : 'a');
}
for(int i = 2;i K.Dice Game
这题主要难在分析出n个事件相互独立。
当x确定时，对于n个人当中的某一个人，他胜利的概率是$p = frac{m-x}{m-1}$，这个有两种理解，第一个感性的理解就是，当投出y = x是没有意义的，所以有效的y一共是m个，其中m - x个是可以赢的。
数学的理解是，这个人可能在第一次赢，也可能第二次赢，也可能第三次赢…，设平局概率为t，胜利概率为q。
$$ p= q + t * q + t^{2} * q + …. + t^{inf} * q $$
其中$t=frac{1}{m}$, $q = frac{m-x}{m}$。
根据等比数列求和我们可以知道：
$$p = frac{m-x}{m-1}$$
然后对于某个x，一共有n个人，那么答案就是$p^n = (frac{m-x}{m-1}) ^ n$。
#include
#define int long long
using namespace std;
const int N = 1e6 + 9, p = 998244353;
int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
int inv(int x){return qmi(x, p - 2);}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;cin >> n >> m;
int res = 1;
for(int i = 1;i I.Step
已知$2t | k(k+1)$，求最小的$k$，其中$t=lcm(p_1,p_2…,p_n)$。
不妨设$2t=a*b$，且$a|k,b|(k+1)$，且$ax=k,by=(k+1)$，那么我们可以得到:
$$ax+1=by$$
转换一下得到：
$$a(-x)+by=1$$
枚举a，可以算出b，然后exgcd搞出最小的x，即得到了k=ax答案。
现在问题是如何枚举a，我们看这个exgcd式子可以发现我们需要保证gcd(a, b) = 1，且有2t = a * b，所以我们可以对2t进行唯一分解，然后选取不同质因子种类分配给a和b。
分配方案可以通过二进制直接做。
#include
#define int long long
using namespace std;
const int N = 1e6 + 9, inf = 8e18;
int p[N];
int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
map mp;
vector v;
void func(int x)
{
for(int i = 2;i 1)v.push_back(x), mp[x] = x;
}
int exgcd(int a, int b, int &x, int &y)
{
if(!b)return x = 1, y = 0, a;
int d = exgcd(b, a % b, y , x);
y -= a / b * x;
return d;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for(int i = 1;i > p[i];
int lc = p[1];
for(int i = 2;i > j & 1)a = a * mp[v[j]];
int b = 2 * lc / a;
int x, y, d = exgcd(a, b, x, y);
x = -x;
x = (x % (b / d) + (b / d)) % (b / d);
if(a * x)res = min(res, x * a);
//cout 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
