NOI 赛前抱 3 个月的佛脚（ku
完成度：5/17
Catcats Contest #1
字符串 (count)
神必转化，壬都傻了
假设一个串有 (i) 个 (1) 和 (n-i) 个 (0)，则定义 (0) 的权值是 (i)，(1) 的权值是 (i-n)，一个字符串的权值是其所有字符权值之和。
所有长为 (l) 的循环子串的权值的平均值为 (0)，且两个相同长度的字符串相差不超过 (1) 当且仅当权值相差不超过 (n)，且相同长度的字符串权值(mod n) 的值都相同。
所以，一个字符串是好的当且仅当所有子串的权值 (in(-n,n))，也就是说 (exist kin[0,n)) 使得所有前缀和 (in(k-n,k])。
从大到小枚举 (k)，此时字符串是唯一的，维护出这个字符串然后顺便计算出不符合询问串限制的位置数量，如果为 (0) 说明满足条件。
时间复杂度 (O(n^2))，而且还可以得到答案也是 (le n^2) 的。注意不要算重了。
#include<bits/stdc++.h>
#define PB emplace_back
using namespace std;
const int N = 1030;
int T, n, ans, pre[N], cnt; bool num[N]; char str[N];
vector<int> vec[N];
void solve(){
scanf("%s", str+1); n = strlen(str+1); ans = 0;
for(int i = 0;i <= n;++ i){
cnt = pre[0] = 0; vec[0].PB(0);
for(int j = 1;j <= n;++ j){
if(pre[j-1] + i < n){
pre[j] = pre[j-1] + i;
num[j] = false;
cnt += str[j] == '1';
} else {
pre[j] = pre[j-1] + i - n;
num[j] = true;
cnt += str[j] == '0';
} if(pre[j] >= 0) vec[pre[j]].PB(j);
} for(int j = n-1;;-- j){
ans += !vec[j].empty() && !cnt;
if(!j) break;
for(int k : vec[j]){
cnt += (str[k] == '0') + (str[k+1] == '1') - (str[k] == '1') - (str[k+1] == '0');
swap(num[k], num[k+1]);
}
} for(int j = 0;j < n;++ j) vec[j].resize(0);
} printf("%d
", ans);
} int main(){scanf("%d", &T); while(T --) solve();}
Catcats Contest #2
己酸集合 (geo)
每个询问分别做，对左右边界跑 two-pointer。时间复杂度 (O(nq))。
构造题 (buhui)
IOI2006 的加强版，有点东西（/kel
首先发现一个性质：如果凸包上 (S,T) 不是连续段，则一定无解。构造证明其他情况都有解。
主要思路是把凸包范围做一个三角剖分，然后每个三角形内部分别做。
不知为何考虑递归构造，设 ( exttt{Solve(A,B,C)}) 表示 (A,B,C) 是逆时针方向，其中 (A) 与 (B,C) 分别属于不同集合，(BC) 有连边，你需要将 (Delta ABC) 内部的所有与 (A) 所属集合相同的点与 (A) 连通，与 (B) 所属集合相同的点与 (B) 或 (C) 中一个连通。
若内部点全都与 (B,C) 所属集合相同，就可以随便分治了，因为全部相同所以只要保证是一棵生成树即可。
否则任意选择一个与 (A) 所属集合相同的点 (X)，与 (A) 连边，将该三角形划分为三个小三角形，变成了子问题 ( exttt{Solve(X,B,C),Solve(C,A,X),Solve(B,X,A)})，递归做。
至于三角剖分，分类讨论一下：
- 若凸包上的点所属集合全相同，那么就在内部找一个不同的，以其为中心做三角剖分。
- 若凸包上的点所属集合不同，则一定是一段 (S) 还有一段 (T)，两边可以分别做，具体实现见代码（雾
在随机数据下的时间复杂度大概是 (O(nlog n))，最坏是 (O(n^2))。
#include<bits/stdc++.h>
#define PB emplace_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
const int N = 3003;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} int n, m;
struct Point {
int x, y;
Point(int _x = 0, int _y = 0): x(_x), y(_y){}
bool operator < (const Point &o) const {if(x != o.x) return x < o.x; return y < o.y;}
LL operator * (const Point &o) const {return (LL)x * o.y - (LL)y * o.x;}
Point operator - (const Point &o) const {return Point(x - o.x, y - o.y);}
Point operator + (const Point &o) const {return Point(x + o.x, y + o.y);}
} p[N];
vector<pii> ans[2];
inline bool col(int x){return x > n;}
void adde(int x, int y){
assert(col(x) == col(y));
if(col(x)) ans[1].PB(x - n, y - n);
else ans[0].PB(x, y);
}
bool intri(int a, int b, int c, int d){ // d in angle bac ?
Point v1 = p[b] - p[a], v2 = p[c] - p[a], v3 = p[d] - p[a];
if(v1 * v2 < 0) swap(v1, v2);
return v1 * v3 > 0 && v3 * v2 > 0;
}
void work(int a, int b, int c, VI now){
// printf("a = %d, b = %d, c = %d
", a, b, c);
if(now.empty()) return; VI tmp;
for(int i : now) if(col(i) == col(a)){
adde(a, i); tmp.resize(0);
for(int j : now) if(intri(i, a, b, j)) tmp.PB(j);
work(b, i, a, tmp); tmp.resize(0);
for(int j : now) if(intri(i, b, c, j)) tmp.PB(j);
work(i, b, c, tmp); tmp.resize(0);
for(int j : now) if(intri(i, c, a, j)) tmp.PB(j);
work(c, a, i, tmp); return;
} static LL dis[N];
for(int i : now) dis[i] = labs((p[c] - p[b]) * (p[i] - p[b]));
sort(now.begin(), now.end(), [&](int u, int v){return dis[u] < dis[v];});
adde(b, now[0]); for(int i = 1;i < now.size();++ i) adde(now[i-1], now[i]);
}
int main(){
read(n); read(m);
for(int i = 1;i <= n+m;++ i){read(p[i].x); read(p[i].y);}
VI id(n+m), hul; iota(id.begin(), id.end(), 1);
sort(id.begin(), id.end(), [&](int a, int b){return p[a] < p[b];});
for(int i : id){
while(hul.size() > 1 && (p[i] - p[hul.back()]) * (p[i] - p[hul[hul.size()-2]]) > 0) hul.pop_back();
hul.PB(i);
} id.pop_back(); reverse(id.begin(), id.end()); int tmp = hul.size();
for(int i : id){
while(hul.size() > tmp && (p[i] - p[hul.back()]) * (p[i] - p[hul[hul.size()-2]]) > 0) hul.pop_back();
hul.PB(i);
} hul.pop_back();
int pos = 1; for(;pos < hul.size() && col(hul[0]) == col(hul[pos]);++ pos);
// printf("pos = %d
", pos);
if(pos == hul.size()){
for(int i = 1;i < hul.size();++ i) adde(hul[i-1], hul[i]);
hul.PB(hul[0]);
for(int i = 1;i <= n+m;++ i) if(col(i) != col(hul[0])){
for(int j = 1;j < hul.size();++ j){
int a = hul[j-1], b = hul[j]; VI tmp;
for(int k = 1;k <= n+m;++ k) if(intri(i, a, b, k)) tmp.PB(k);
work(i, a, b, tmp);
} break;
}
} else {
rotate(hul.begin(), hul.begin() + pos, hul.end());
// for(int i : hul) printf("%d ", i); putchar('
');
for(pos = 1;pos < hul.size() && col(hul[0]) == col(hul[pos]);++ pos);
for(int _ = pos;_ < hul.size();++ _) if(col(hul[0]) == col(hul[_])){puts("Impossible"); return 0;}
for(int i = 1;i < pos;++ i){
int a = hul[pos], b = hul[i-1], c = hul[i]; VI tmp;
for(int k = 1;k <= n+m;++ k) if(intri(a, b, c, k)) tmp.PB(k);
adde(b, c); work(a, b, c, tmp);
} for(int i = pos+1;i < hul.size();++ i){
int a = hul[0], b = hul[i-1], c = hul[i]; VI tmp;
for(int k = 1;k <= n+m;++ k) if(intri(a, b, c, k)) tmp.PB(k);
adde(b, c); work(a, b, c, tmp);
}
} assert(ans[0].size() == n-1); assert(ans[1].size() == m-1);
for(int _ = 0;_ < 2;++ _) for(pii &u : ans[_]) printf("%d %d
", u.fi, u.se);
}
最长环 (route)
人类智慧，肝败吓疯（
#include<bits/stdc++.h>
using namespace std;
const int N = 303, B = 666, NIF = -1000000007;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, k, x[N], y[N], z[N], a[N][N], d[2][N][N], w[N][N][3], ans; bool f[N], o;
void ins(int u, int v, int x){
int p = 0;
for(;p < 3;++ p){
int t = w[u][v][p];
if(a[u][t] + a[v][t] < a[u][x] + a[v][x]) break;
} if(p < 3){
for(int i = 2;i > p;-- i) w[u][v][i] = w[u][v][i-1];
w[u][v][p] = x;
}
}
void calc(int u, int v, int x, int y){
int p = 0;
while(w[u][v][p] == x || w[u][v][p] == y) ++ p;
int z = w[u][v][p];
chmax(d[o][x][y], a[x][u] + a[u][z] + a[z][v] + a[v][y]);
}
void solve(int k){
for(int i = 0;i <= n;++ i)
for(int j = 0;j <= n;++ j) d[o][i][j] = NIF;
switch(k){
case 1: for(int i = 1;i <= n;++ i) if(f[i] == o) d[o][i][i] = 0; break;
case 2:
for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
d[o][x[i]][y[i]] = d[o][y[i]][x[i]] = z[i]; break;
case 3:
for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] == o && f[y[j]] == o){
if(x[i] == x[j]) chmax(d[o][y[i]][y[j]], z[i] + z[j]);
else if(y[i] == x[j]) chmax(d[o][x[i]][y[j]], z[i] + z[j]);
else if(x[i] == y[j]) chmax(d[o][y[i]][x[j]], z[i] + z[j]);
else if(y[i] == y[j]) chmax(d[o][x[i]][x[j]], z[i] + z[j]);
} break;
case 4:
for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] == o && f[y[j]] == o && x[i] != x[j] && x[i] != y[j] && y[i] != x[j] && y[i] != y[j]){
chmax(d[o][x[i]][x[j]], z[i] + z[j] + a[y[i]][y[j]]);
chmax(d[o][x[i]][y[j]], z[i] + z[j] + a[y[i]][x[j]]);
chmax(d[o][y[i]][x[j]], z[i] + z[j] + a[x[i]][y[j]]);
chmax(d[o][y[i]][y[j]], z[i] + z[j] + a[x[i]][x[j]]);
} break;
case 5:
for(int i = 1;i <= n;++ i) if(f[i] == o)
for(int j = 1;j <= n;++ j) if(f[j] == o){
w[i][j][0] = w[i][j][1] = w[i][j][2] = 0;
}
for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] == o && f[y[j]] == o){
if(x[i] == x[j]) ins(y[i], y[j], x[i]);
else if(y[i] == x[j]) ins(x[i], y[j], y[i]);
else if(x[i] == y[j]) ins(y[i], x[j], x[i]);
else if(y[i] == y[j]) ins(x[i], x[j], y[i]);
}
for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] == o && f[y[j]] == o && x[i] != x[j] && x[i] != y[j] && y[i] != x[j] && y[i] != y[j]){
calc(x[i], x[j], y[i], y[j]);
calc(y[i], x[j], x[i], y[j]);
calc(x[i], y[j], y[i], x[j]);
calc(y[i], y[j], x[i], x[j]);
}
}
}
int main(){
read(n); read(m); read(k);
for(int i = 0;i <= n;++ i)
for(int j = 0;j <= n;++ j) a[i][j] = NIF;
for(int i = 1;i <= m;++ i){
read(x[i]); read(y[i]); read(z[i]);
a[x[i]][y[i]] = a[y[i]][x[i]] = z[i];
} for(int _ = 0;_ < B;++ _){
for(int i = 1;i <= n;++ i) f[i] = rng() & 1;
if(k == 6){o = 0; solve(2); o = 1; solve(4);}
else {o = 0; solve(k>>1); o = 1; solve(k+1>>1);}
for(int i = 1;i <= m;++ i) if(f[x[i]] && !f[y[i]]) swap(x[i], y[i]);
for(int i = 1;i <= m;++ i) if(f[x[i]] != f[y[i]])
for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] != f[y[j]])
chmax(ans, d[0][x[i]][x[j]] + d[1][y[i]][y[j]] + z[i] + z[j]);
} if(ans > 0) printf("%d
", ans); else puts("impossible");
}
Catcats Contest #3
计数题 (count)
壬被玩傻了
首先 (n,m) 都为奇数时答案是 (1)。
其次 (n) 为偶数，(m) 为奇数时答案是 ((n/2+1)^{(m-1)/2})，这事因为 (1) 所在列已经被确定，每个要填的列都有 (n/2+1) 种独立的方式。
然后就是 (n,m) 都为偶数的情况。若将整个矩阵划分为 (2 imes 2) 的 block，则每块都恰有一个 (1)，且每行、每列填的 (1) 的位置形如 (010101|101010)，我们按列做 dp，将这个分界线的位置记录下来，并且将第 (i) 个 block 内的 (1) 是否靠右记录下来。要做的就是避免下面这种情况：
.x.. ..x.
...x x...
x... ...x
..x. .x..
转移是一个 SOS 形式，时间复杂度 (O(n^3m2^n))，其中这里的 (n,m) 是原来的一半。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, lim, mod, dp[2][13][4096], a[4096], ans; bool cr;
int ksm(int a, int b){
int res = 1;
for(;b;b >>= 1, a = (LL)a * a % mod)
if(b & 1) res = (LL)res * a % mod;
return res;
} void qmo(int &x){x += x >> 31 & mod;}
void FMT(int *a){
for(int mid = 1;mid < lim;mid <<= 1)
for(int i = 0;i < lim;i += mid<<1)
for(int j = i;j < i+mid;++ j)
qmo(a[j] += a[j|mid] - mod);
}
int main(){
scanf("%d%d%d", &n, &m, &mod);
if((n & 1) && (m & 1)){puts("1"); return 0;}
if(n & 1) swap(n, m); if(m & 1){printf("%d
", ksm((n>>1)+1, m>>1)); return 0;}
n>>=1; m>>=1; lim = 1<<n;
for(int i = 0;i <= n;++ i)
for(int j = 0;j < lim;++ j)
dp[0][i][j] = 1;
for(int _ = 1;_ < m;++ _, cr ^= 1){
memset(dp[!cr], 0, sizeof dp[!cr]);
for(int i = 0;i <= n;++ i){
memcpy(a, dp[cr][i], lim<<2); FMT(a);
for(int j = 0;j <= n;++ j)
for(int S = 0;S < lim;++ S){
int T = S;
for(int k = i+1;k < j;++ k)
if((S>>k-1&1) && !(S>>k&1)) T |= 1<<k;
for(int k = j;k < i-1;++ k)
if(!(S>>k&1) && (S>>k+1&1)) T |= 1<<k;
qmo(dp[!cr][j][S] += a[T] - mod);
}
}
}
for(int i = 0;i <= n;++ i)
for(int j = 0;j < lim;++ j)
qmo(ans += dp[cr][i][j] - mod);
printf("%d
", ans);
}
Catcats Contest #4
平方过百万 (million)
有一个我不会的转化：对于第 (2) 种操作，在 ((u_p,v_p)) 之间加一条权值为操作编号的边，则编号为 (T) 的询问 ( exttt{1 u}) 即为求从 (u) 开始走权值递增且 (le T) 的边，能到达的节点个数。
可以使用点分治，假设当前处理的分治中心是 (r)，对每个操作 (2)，求出从它到达分治中心的最早时间，和分治中心能到达它所出发的最晚时间。这大概是一个二维偏序，用排序 + 树状数组即可，时间复杂度 (O((n+m)log n))。有点烦，自闭了
Catcats Contest #5
构造题 (buhui)
stm 域论，等拿到数学女孩第 5 册了就学（
有限域相关基础：( ext{GF}(p^n)) 可以表示为系数模 (p)，整体模 (n) 次本原多项式 (F) 的意义下定义四则运算，由不超过 (n-1) 次的多项式构成的代数结构。
可以证明这东西是域，也可以证明它存在且唯一。其特征为 (p)，所以 ((x+y)^p=x^p+y^p)。
那至于这题怎么做：取最小的 (w) 使得 (2^w>|S|)，计算出 ( ext{GF}(2^w))，构造 (a_i=icdot 2^w+f(i))，其中 (f(i)) 是 ( ext{GF}(2^w)) 意义下的立方。
至于正确性，考虑反证法：假设存在 ((i_1,j_1) e (i_2,j_2)) 使得 (a_{i_1}oplus a_{j_1}=a_{i_2}oplus a_{j_2})，则 (i_1,j_1,i_2,j_2) 必须两两不同，且在 ( ext{GF}(2^w)) 意义下 (i_1+j_1=i_2+j_2 e 0)，且 (i_1^3+j_1^3=i_2^3+j_2^3)，得到 (i_1^2+i_1j_1+j_1^2=i_2^2+i_2j_2+j_2^2)，所以 (i_1j_1=i_2j_2)。
令 (s=i_1+j_1,p=i_1j_1)，得到 (x(s-x)=p) 有至少 (4) 个根，而其只有 (2) 次，矛盾。
因此 (a_ioplus a_j) 两两不同，得证。本原多项式可以事先预处理，具体实现上 mod 2 运算可以使用异或运算。
这个构造的背景在于一个经典问题：如何在 ([0,p)^2) 中构造 (p) 个整点使得不存在三点共线，其中 (p) 是质数。一种构造是取 (x_i=i,y_i=i^2mod p)，可以得到 (frac{y_j-y_i}{x_j-x_i}=frac{y_k-y_j}{x_k-x_j}Rightarrow x_i+x_j=x_j+x_kRightarrow x_i=x_k)。
#include<bits/stdc++.h>
using namespace std;
const int _[] = {2,7,11,19,37,67,131,283,515,1033,2053,4105};
int n, mod, lim;
int red(int x){
int p = mod; while(p <= x) p <<= 1;
for(;p >= mod;p >>= 1) if((x ^ p) < x) x ^= p;
return x;
} int mul(int x, int y){
int r = 0;
for(;x;x >>= 1, y <<= 1) if(x & 1) r ^= y;
return red(r);
}
int main(){
scanf("%d", &n); mod = _[n-1]; lim = 1<<n;
for(int i = 0;i < lim;++ i) printf("%d ", i<<n|mul(mul(i,i),i));
}