~~中国场做着还是挺舒服的。~~

Codeforces 1106A Lunar New Year and Cross Counting

题目大意: 给定一个 $n \times n$ 的棋盘，输出里面如下形状的个数:

1
2
3

X.X
.X.
X.X

其中 . 可以替换为 X 。 $n \le 500$ 。

按照题意模拟就好了。复杂度 $O(n^2)$ 。

#include <bits/stdc++.h>
using namespace std; 
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
char s[505][505]; int n, c;
int main()
{
    n = rf(); for(rint i = 1; i <= n; scanf("%s",s[i]+1), i++);
    for(rint i = 2, j; i < n; i++) for(j = 2; j < n; j++)
        c += s[i][j]=='X'&&s[i-1][j-1]=='X'&&s[i-1][j+1]=='X'&&s[i+1][j-1]=='X'&&s[i+1][j+1]=='X';
    printf("%d\n",c); return 0;
}

Codeforces 1106B Lunar New Year and Food Ordering

题目大意: 有 $n$ 个物品，第 $i$ 个单价为 $c_i$ ，持有 $a_i$ 件。有 $m$ 次破坏性询问(即会改变现在物品持有数量): 有一个人要买 $d_j$ 个物品 $t_j$ 。如果够了就直接买，不够就从其他物品中选择最便宜且编号尽可能小的物品买直到买到 $d_j$ 个，如果所有物品总量都不够 $d_j$ ，这个人就逃单了(拿走所有物品不付钱)。求每个人的花费。 $n,m \le 10^5, c_i \le 10^6$ 。

显然，用来补订单的物品是有顺序的: 价格递增的前提下编号递增。所以只需要将所有物品的编号按照 $(c_i,i)$ 为关键字排序，然后用一个单调指针扫描现在该用什么补订单就可以了。

虽然每个人都要补订单的话复杂度乍一看是 $O(nm)$ ，但是因为每一次补订单相当于一种物品卖光了，均摊补订单次数只有 $O(m)$ (可以理解为指针单调递增)。总复杂度 $O(nm)$ 。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int a[MAXN+5], c[MAXN+5], s[MAXN+5], n, m, p = 1, t, d; long long r, j;
int main()
{
    n = rf(); m = rf(); generate(a+1,a+n+1,rf); generate(c+1,c+n+1,rf); iota(s+1,s+n+1,1); sort(s+1,s+n+1,[](int i, int j){return c[i]^c[j]?c[i]<c[j]:i<j;});
    for(; m--; printf("%I64d\n",d?0:r)) for(t = rf(), d = rf(), d -= j = min(d,a[t]), a[t] -= j, r = j*c[t]; d && p <= n; d -= j = min(d,a[s[p]]), a[s[p]] -= j, r += j*c[s[p]], p += !a[s[p]]); return 0;
}

Codeforces 1106C Lunar New Year and Number Division

题目大意: 将 $n$ 个数分为若干组，每组不少于 $2$ 个数，最小化【每组数的和的平方】的和。 $2 \le n \le 3 \times 10^5, n \equiv 0 \pmod 2$ 。

显然是两两一组。考虑怎么分最优秀。~~乱搞选手当然可以一眼就看出怎么分最优秀。~~

设分组方案为 $(a_1,b_1), (a_2,b_2), ..., (a_{n/2},b_{n/2})$ ，那么答案是:

$\sum_{i=1}^\frac{n}{2} (a_i+b_i)^2 = \sum_{i=1}^\frac{n}{2} (a_i^2 + 2 a_i b_i +b_i^2)$

因为 $\sum a_i^2$ 和 $\sum b_i^2$ 都是定值，只需要最小化 $\sum a_ib_i$ 。这就是排序不等式: 排序不等式。即最大的 $a_i$ 和最小的 $b_i$ 配对，次大的 $a_i$ 和次小的 $b_i$ 配对，…，以此类推，答案最小。

那么怎么证明 $a_i$ 和 $b_i$ 要交叉着分？

~~去翻了一下题解，题解这部分的证明是没有的，感觉不太严谨。~~

可以考虑将序列 $a_i$ 和 $b_i$ 都看做 $n$ 个数的完整集合，这时候最优配对方案就是逆序和。而任意一个将 $a_i$ 和 $b_i $ 分组配对的方案都可以对应一个完整集合方案(但是反之不一定)。例如1 2 3 4 5 6的一个分组配对方案是3-1 2-4 5-6，可以对应构造出完整集合方案:

1 2	1 2 3 4 5 6 3 4 1 2 6 5

而任意一个完整集合方案都不如逆序和更优。而逆序和恰好可以构造出一个分组配对方案。因此所有分组配对方案中交叉配对逆序和最优。即: 即一个分组配对方案为 $A_i$ ，交叉配对方案为 $A^*$ ，一个分组配对方案对应的完整集合方案为 $B_i = f(A_i)$ 。

$cost(A_i) = \frac{1}{2}cost(f(A_i)) = \frac{1}{2}cost(B_i) \ge \\ \frac{1}{2} cost(B^*) = cost(f^{-1}(B^*)) = cost(A^*)$

其中，最后一个等式有意义当且仅当 $f^{-1}(B^*) = A^*$ 存在，而其的确存在。因此证毕。

复杂度 $O(n \log n)$ ，瓶颈在于排序(当然可以桶排 $O(n+A)$ )。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sqr(x) ((x)*(x))
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int n, a[300005]; ll r; int main(){n = rf(); generate(a+1,a+n+1,rf); sort(a+1,a+n+1); for(rint i = 1, j = n; i < j; r += sqr(a[i]+a[j]), i++, j--); return !printf("%I64d\n",r);}

Codeforces 1106D Lunar New Year and a Wander

题目大意: 给定一张 $n$ 点 $m$ 边连通无向图，走一条可经过重复点和边的路径，每到达一个没到达过的节点时写下这个节点，求字典序最小的路径。 $n,m \le 10^5$ 。

~~怎么感觉是个经典老题？~~

从 $1$ 号点开始走，访问过的点一定是连通块，因为可以走重复点和边，因此每次可以走到连通块边界上的任何一个点。那么只需要维护当前连通块外围相邻的所有点，用一个优先队列排序每次贪心将最小的点加入连通块再扩展外围就行了。

复杂度 $O(m \log n)$ 。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
vector<int> e[MAXN+5]; int q[MAXN+5], s[MAXN+5], n, m, t; bool b[MAXN+5]; 
int main()
{
    n = rf(); m = rf(); for(rint i = 1, u, v; i <= m; u = rf(), v = rf(), e[u].push_back(v), e[v].push_back(u), i++); b[q[t=1]=1] = true;
    for(rint i = 1; i <= n; i++){s[i] = q[1]; pop_heap(q+1,q+t--+1,greater<int>()); for(auto v:e[s[i]]) if(!b[v]) b[q[++t]=v] = true, push_heap(q+1,q+t+1,greater<int>());}
    for(rint i = 1; i <= n; printf("%d%c",s[i],"\n "[i<n]), i++); return 0;
}

Codeforces 1106E Lunar New Year and Red Envelopes

题目大意: 含有整点 $1 \sim n$ 的数轴上，有 $k$ 条线段 $[s_i,t_i]$ ，如果当前在整点 $x \in [l_i,r_i]$ ，那么收益 $+= w_i$ 然后跳到点 $d_i+1$ ，如果点 $x$ 被多条线段覆盖，选择 $w_i$ 最大前提下 $d_i$ 最大的线段进行操作；如果没有线段覆盖那么跳到点 $x+1$ 。现在有 $m$ 次强制从 $x$ 跳到 $x+1$ 的机会，要求最小化收益。 $n,k \le 10^5, m \le 200$ 。

$DP$ 可以一眼瞅出来: $f[i][j]$ 表示当前在点 $i$ ，还剩 $j$ 次强制机会，最小收益是多少，在点 $i$ 可以选择强制或不强制:

$f[i][j] = \min(f[i+1][j-1],f[go(i)][j]+w(i))$

$DP$ 复杂度 $O(nm)$ 勉强可以接受，只需要预处理 $go(i)$ 和 $w(i)$ 就可以了。这个预处理随便怎么搞都行: 可以把线段差分，在 $s_i$ 处插入，在 $t_i+1$ 处删除。所有现存线段按照 $(w_i,d_i)$ 排序，支持查询最大值，这个用一个multiset或可删除堆维护即可。

复杂度 $O(n \log n +nm)$ 。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define f(i,j) f[(j)&1][i]
#define INF 0x3f3f3f3f3f3f3f3fll
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
struct E{int w,d;}_; inline bool operator < (const E &a, const E &b){return a.w^b.w?a.w>b.w:a.d>b.d;}
multiset<E> S; vector<E> ins[MAXN+5], del[MAXN+5]; long long f[2][MAXN+5]; int w[MAXN+5], g[MAXN+5], n, m, k;
int main()
{
    n = rf(); m = rf(); k = rf(); for(rint i = 1, s, t; i <= k; s = rf(), t = rf(), _.d = rf(), _.w = rf(), ins[s].push_back(_), del[t+1].push_back(_), i++);
    for(rint i = 1; i <= n; i++)
    {
        for(; ins[i].size(); S.insert(ins[i].back()), ins[i].pop_back()); for(; del[i].size(); S.erase(S.find(del[i].back())), del[i].pop_back());
        if(S.size()){_ = *S.begin(); w[i] = _.w; g[i] = _.d+1;} else g[i] = i+1;
    }
    for(rint j = 0, i; j <= m; j++) for(memset(f[j&1]+1,0x3f,n<<3), i = n; i; f(i,j) = min(j?f(i+1,j-1):INF,f(g[i],j)+w[i]), i--);
    printf("%I64d\n",f(1,m)); return 0;
}

一开始WA了: multiset.erase()会一次删除所有满足条件的元素，需要用multiset.erase(multiset.find())。

Codeforces 1106F Lunar New Year and a Recursive Sequence

题目大意: 给定递推式:

$f_n \equiv \prod_{i=1}^kf_{n-i}^{b_i} \pmod {998244353}$

已知 $b_1, b_2, ..., b_k$ ，且 $f_1=f_2=...=f_{k-1} = 1, f_n = m$ ，求任意一个满足条件的 $f_k$ 。 $k \le 100, n \le 10^9$ 。

~~暴露了毒瘤本质: 一看到一大堆公式就激动~~

一看到这道题第一反应就是取对数的冲动(专业叫法叫指标 $index$ ，但是我还是更喜欢写取对数)，以原根 $g = 3$ 为底对递推式取对数，记 $MOD = 998244353$ ， $PHI = \varphi(998244353) = 998244352$:

$\log_gf_n = \sum_{i=1}^kb_i \cdot \log_gf_{n-i} \pmod {PHI}$

这样数列 $\lbrace\log_gf_i\rbrace$ 就是一个常系数线性递推， $k$ 又非常小，就可以直接矩乘:

$\left[ \begin{matrix} b_1 & b_2 & b_3 & ... & b_k \\ 1 & 0 & 0 & ... & 0 \\ 0 & 1 & 0 & ... & 0 \\ & & ... & & \\ 0 & 0 & 0 & ... & 1 \end{matrix} \right]^{n-k} \left[ \begin{matrix} \log_g f_k \\ \log_g f_{k-1} = 0 \\ \log_g f_{k-2} = 0 \\ ...\\ \log_g f_{1} = 0 \end{matrix} \right] = \left[ \begin{matrix} \log_g f_n = \log_gm \\ \log_g f_{n-1} \\ \log_g f_{n-2} \\ ...\\ \log_g f_{n-k+1} \end{matrix} \right]$

记左侧转移矩阵为 $U$ ，就有 $U^{n-k}[1][1] \cdot \log_gf_k \equiv \log_gm \pmod {PHI}$ 。

简化一下就是 $a \cdot \log_g x \equiv M \pmod {PHI}$ ，现在要求解 $x$ 。

首先求解 $ay \equiv M \pmod {PHI}$ ，因为 $PHI$ 不是质数，要特别注意，首先同除 $d = GCD(a,M,PHI)$ ，这时候如果 $a/d$ 和 $PHI/d$ 还不互质就解不了了(因为 $(a/d)^{-1} \pmod {PHI/d}$ 不存在了)。否则只需要用 $EXGCD$ 求出 $(a/d)^{-1} \pmod {PHI/d}$ 即可，答案就是 $y = (M/d) \cdot (a/d)^{-1} \pmod {PHI/d}$ 。

$EXGCD$ 求逆: $a(a^{-1}) \equiv 1 \pmod p \Leftrightarrow a(a^{-1}) - pt = 1$ ，用 $EXGCD$ 解出 $(a^{-1})$ 和 $t$ 。

求出了 $y$ 以后，因为 $y = \log_gx$ ，就显然有 $x = g^y$ 。就做完了。

最后一个问题就是求 $M$ ，即求 $\log_g m$ 。就是一个 $BSGS$ :

$g^t \equiv m \pmod{MOD}\\ g^{iu-j} \equiv m \pmod{MOD}\\ g^{iu} \equiv mg^j \pmod{MOD}$

其中 $u = \lceil \sqrt{MOD} \rceil$ 。本题不要求求最小解，枚举 $j \in [1,u]$ 将右侧加入哈希表，枚举 $i \in [1,u]$ 查询即可。

复杂度瓶颈为矩乘和 $BSGS$ ，复杂度 $O(k^3 \log n + \sqrt p \log p)$ 。

#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define PHI 998244352
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
struct Mat{int c[105][105];}C, I, S, U; int n, N, M, a, d, e; unordered_map<int,int> G;
inline Mat &operator *= (Mat &A, Mat &B)
{
    for(rint i = 1; i <= n; memset(C.c[i]+1,0,n<<2), i++);
    for(rint i = 1, j, k; i <= n; i++) for(k = 1; k <= n; k++) if(A.c[i][k]) 
        for(j = 1; j <= n; C.c[i][j] = (C.c[i][j]+1ll*A.c[i][k]*B.c[k][j])%PHI, j++); return A=C;
}
inline Mat &operator ^= (Mat &A, int K){for(S = I; K; K&1 ? S*=A,0 : 0, A *= A, K >>= 1); return A=S;}
inline int fxp(int a, int n=MOD-2){int s=1;for(;n;n&1?s=1ll*a*s%MOD:0,a=1ll*a*a%MOD,n>>=1);return s;}
inline void EXGCD(int a, int b, int &x, int &y){b ? EXGCD(b,a%b,y,x),y-=a/b*x : x=-~(y=0);}
inline int inv(int a, int P){int _, __; EXGCD(a,P,_,__); return (_%P+P)%P;}
inline int GCD(int a, int b){return b?GCD(b,a%b):a;}
inline int Log(int B)
{
    int u = ceil(sqrt(MOD)+.5), t; for(rint j = 0, s = 1; j <= u; G[1ll*B*s%MOD] = j, s = 3ll*s%MOD, j++); t = fxp(3,u);
    for(rint i = 1, s = t; i <= u; s = 1ll*t*s%MOD, i++) if(G.count(s)) return (i*u-G[s]+PHI)%PHI;
}
int main()
{
    n = rf(); generate(U.c[1]+1,U.c[1]+n+1,rf); N = rf(); M = Log(rf()); for(rint i = 1; i <= n; I.c[i][i] = U.c[i+1][i] = 1, i++);
    U ^= N-n; a = U.c[1][1]; d = GCD(GCD(a,M),PHI); if(GCD(a/d,PHI/d)>1) return puts("-1"),0; printf("%d\n",fxp(3,1ll*inv(a/d,PHI/d)*(M/d)%(PHI/d)));
}

扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章: