Cometoj出过这题。。考虑单个点的贡献(a[i] - a[x]) * (a[i] - a[x]) = a[i] * a[i] - 2 * a[i] * a[x] + a[x] * a[x]所以里面一共就有(n - 1)个a[i]的平方以及除了a[i]外其他所有数的平方，中间这部分减法就是2 * (sum - a[i]) * a[i], sum即是所有数字的和。最后别忘了除2，因为两两之间会算两次。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long l...

考点:并查集，离散化。这题题意很明确，做法也很明确。先对友好的弄一个并查集，最后再查询敌人是否为友好关系。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; const int mod = 10000; const int N = 5e6 + 10; int pre[N]; int a[N]; int b[N]; int c[N]; int d[N]; int find(i...

考点:二维差分，前缀和。这题题意很明确，做法也很明确，先对前k个操作差分，再进行二维前缀和，直接O(1)查询就行了。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; const int mod = 10000; const int N = 5e6 + 10; ll a[2010][2010]; int main() { #ifdef LOCAL freopen("...

这题给出  满足  求第n项  对做一次矩阵乘法， 得到的即是与 所以乘n次后， 取m[1][0]即是答案 但是这个数据范围太大了， 直接快速幂会超。 可以使用十进制快速幂 有个优化， 在对十倍增时， 可以使用2倍增， 压缩成3次 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int&n...

链接：https://ac.nowcoder.com/acm/contest/887/A 来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 A string is perfect if it has the smallest lexicographical ordering among its cyclic rotations. For example: "0101" is perfect as it is the smallest string among (...

可以使用组合数学或者数位dp来写组合数的写法， 就是通过枚举1 和 0的个数来计算总的方案数 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll pre[110]; ll C(ll n, ll m) // 算组合数 { ll res1 = 1, j = 1; if (n / 2 < m) m = n - m; for (ll i = n - m + 1; i <= n; i++) { res1 *= i; ...

这题布吉岛为啥可以降幂 P为质数， 所以对次方降幂， 取模(mod - 1) 设f[i][j][k]， i表示摆到第几个位置， j中0表示A的个数为偶数， 1为奇数， k中0表示B的个数为偶数， 1为奇数。 推出递推方程， 就可以矩阵快速幂了！ f[i][0][0] = 2 * f[i - 1][0][0] + f[i - 1][0][1] + f[i - 1][1][0]; f[i][0][1] = 2 * f[i - 1][0][1] + f[i - 1][1][1] + f[i - 1][0][0]; f...

为了避免溢出， 使用int128即可 使用int128即可 #include <stdio.h> #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() {     __int128_t x, a, y, b;     ll t;     while (cin >> t)     {  ...