Codechef May Challenge 2020 简要题解

这次赛时没打，赛后补了下题目，被最后一题打爆，特意学了一波相关姿势。

Triple Sort

略

Chef and Bitwise Product

略

Sorting Vases

显然$M$个交换的意义就是将位置划分为若干等价类。那么可以将最初的每个数$i$写成$(u_i,v_i)$的形式，代表一开始在等价类$u_i$，最后要到等价类$v_i$。
考虑将数字间的交换当做一条边，那么得到的每个弱连通分量需要满足每个等价类在$u$中出现次数等于在$v$中出现次数。并且对于一个大小为$k$的弱连通分量，至少需要交换$k?1$次，那么假设$N$个数最多能划分为$w$个合法的可以作为弱连通分量集合的非空集合，答案下界即为$N?w$，并且容易达到这个下界。
现在问题是求出$w$，直接枚举集合的子集DP或是暴力做$N$次子集卷积复杂度分别为$\mathcal{O}(3^N)$或$\mathcal{O}(2^N?N^2)$，都不好通过。考虑关注一下性质，显然若干个合法的不交集合的并也是合法的，那么考虑已经求出了所有的能够划分为$i$个合法非空集合的集合，对于每个集合$S$，它能够划分为$i+1$个非空集合当且仅当它自身是合法的且存在一个$T?S$使得$T$能够划分为$i$个非空集合，做$O(N)$次高维前缀和即可。
单组数据时间复杂度为$\mathcal{O}(2^N?N^2)$。

#include <bits/stdc++.h>using namespace std;namespace SETS {
    int fa[20];void init(int n) {
    for(int i=1;i<=n;i++) fa[i]=i;
}int find_father(int x) {
    return (fa[x]==x)?x:fa[x]=find_father(fa[x]);
}void merge(int x,int y) {
    x=find_father(x);y=find_father(y);if (x==y) return;fa[x]=y;
}}int p[20];
int col[20],cnt[20];bool f[1<<18];void pre(int n) {
    for(int i=1;i<(1<<n);i++) {
    memset(cnt,0,sizeof(cnt));for(int j=1;j<=n;j++)if ((i>>(j-1))&1) {
    cnt[col[j]]++;cnt[col[p[j]]]--;}bool ok=1;for(int j=1;j<=n;j++)if (cnt[j]) {
    ok=0;break;}f[i]=ok;}
}void fwt(int *p,int len) {
    for(int i=1;i<len;i<<=1)for(int j=0;j<len;j++)if (j&i) p[j]+=p[j^i];
}int g[1<<18];int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&p[i]);SETS::init(n);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);SETS::merge(x,y);}for(int i=1;i<=n;i++) col[i]=SETS::find_father(i);pre(n);int ans=n-1;for(;;) {
    for(int i=0;i<(1<<n);i++) g[i]=f[i];fwt(g,1<<n);for(int i=0;i<(1<<n);i++) f[i]=(f[i]&&g[i]>1);if (!f[(1<<n)-1]) break;ans--;}printf("%d\n",ans);}return 0;
}
/* 1 6 0 2 1 4 5 3 6 */

Buying a New String

略

Binary Land

经典的双栈模拟队列。
考虑没有删除的做法，显然可以维护一个$F[i][j][k]$起点在$(1,k)$，终点在$(i,j)$的路径数目，转移直接计算即可。
再考虑有删除的做法，注意到我们可以快速合并两个$DP$数组，那么我们随便选一行$mid$，维护两个DP数组$F[i][j][k]$和$G[i^{\prime }][j^{\prime }][k^{\prime }]$，分别表示起点在$(mid+1,k)$，终点在$(i,j)$和起点在$(i^{\prime },j^{\prime })$，终点在$(mid,k)$的路径数目，查询的时候可以直接合并。插入操作就在$F$最后加入一行，删除操作如果没有删空$mid$前面的就直接删，否则取$mid$为当前最后一行重构一下，容易证明每行只需要均摊计算$\mathcal{O}(1)$次。
时间复杂度为$\mathcal{O}(N^{2}Q)$。

#include <bits/stdc++.h>
#define MOD 1000000007using namespace std;typedef unsigned int ui;
typedef long long ll;char str[300005][21];
ui f[300005][20][20];int main() {
    int n,m;scanf("%d%d",&n,&m);int l=1,mid=0,r=0;for(int i=1;i<=m;i++) {
    char s[30];scanf("%s",s);if (s[0]=='a') {
    scanf("%s",str[++r]);if (mid==r-1) {
    for(int j=0;j<n;j++) f[r][j][j]=1;}else {
    for(int j=0;j<n;j++) {
    if (j&&str[r][j]==str[r-1][j-1]) {
    for(int k=0;k<n;k++) f[r][j][k]+=f[r-1][j-1][k];}if (str[r][j]==str[r-1][j]) {
    for(int k=0;k<n;k++) f[r][j][k]+=f[r-1][j][k];}if (j+1<n&&str[r][j]==str[r-1][j+1]) {
    for(int k=0;k<n;k++) f[r][j][k]+=f[r-1][j+1][k];}for(int k=0;k<n;k++) f[r][j][k]%=MOD;}}}else if (s[0]=='r') {
    if (l>mid) {
    mid=r;for(int j=l;j<=mid;j++) memset(f[j],0,sizeof(f[j]));for(int j=0;j<n;j++) f[mid][j][j]=1;for(int j=mid-1;j>=l;j--)for(int k=0;k<n;k++) {
    if (k&&str[j][k]==str[j+1][k-1]) {
    for(int t1=0;t1<n;t1++) f[j][k][t1]+=f[j+1][k-1][t1];}if (str[j][k]==str[j+1][k]) {
    for(int t1=0;t1<n;t1++) f[j][k][t1]+=f[j+1][k][t1];}if (k+1<n&&str[j][k]==str[j+1][k+1]) {
    for(int t1=0;t1<n;t1++) f[j][k][t1]+=f[j+1][k+1][t1];}for(int t1=0;t1<n;t1++) f[j][k][t1]%=MOD;}}l++;}else {
    int x,y;scanf("%d%d",&x,&y);x--;y--;if (l>mid) printf("%u\n",f[r][y][x]);else if (r==mid) printf("%u\n",f[l][x][y]);else {
    ui s=0;for(int j=0;j<n;j++)if (f[l][x][j]) {
    ui v=0;if (j&&str[mid][j]==str[mid+1][j-1]) v+=f[r][y][j-1];if (str[mid][j]==str[mid+1][j]) v+=f[r][y][j];if (j+1<n&&str[mid][j]==str[mid+1][j+1]) v+=f[r][y][j+1];s=(s+(ll)v*f[l][x][j])%MOD;}printf("%u\n",s);}}}return 0;
}

Not a Real World Problem

显然的最小割。
考虑建一个图，每个粒子作为一个点$i$，分别连边$(S,i)$和$(i,T)$，割掉$(i,T)$代表$p_i$取$+1$，否则代表$p_i$取$?1$，边的容量容易计算（按最小割的一般套路，负权直接连，正权先加入答案再连）。
对于两个相邻的粒子$i$和$j$，先对答案加上$p_i?p_j$，再连边$(i,j)$和$(j,i)$，边权均为$2p_i?p_j$，代表若$i$和$j$正负号不同要割掉。
直接跑dinic算法即可，单组数据时间复杂度为$\mathcal{O}(HW+N^3)$。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define FR first
#define SE secondusing namespace std;typedef pair<int,int> pr;struct Edge {
    int t,f,next;Edge() {
    }Edge(int a,int b,int c):t(a),f(b),next(c) {
    }
};Edge e[1000005];
int head[205],vs,vt,tot;inline void addEdge(int x,int y,int z) {
    e[++tot]=Edge(y,z,head[x]);head[x]=tot;e[++tot]=Edge(x,0,head[y]);head[y]=tot;
}namespace Flow {
    int d[205],cur[205];
queue <int> q;bool bfs() {
    while (!q.empty()) q.pop();memset(d,255,sizeof(d));d[vs]=0;cur[vs]=head[vs];q.push(vs);while (!q.empty()) {
    int x=q.front();q.pop();for(int i=head[x];i!=-1;i=e[i].next)if (e[i].f&&d[e[i].t]==-1) {
    int u=e[i].t;d[u]=d[x]+1;cur[u]=head[u];if (u==vt) return 1;q.push(u);}}return 0;
}int dfs(int x,int a) {
    if (x==vt||!a) return a;int ans=0;for(int &i=cur[x];i!=-1;i=e[i].next)if (e[i].f&&d[e[i].t]==d[x]+1) {
    int u=e[i].t;int f=dfs(u,min(a,e[i].f));if (f) {
    e[i].f-=f;e[i^1].f+=f;ans+=f;a-=f;if (!a) break;}}return ans;
}int maxflow() {
    int ans=0;while (bfs())ans+=dfs(vs,inf);return ans;
}}int val[1005][1005],num[205];
pr pos[205];int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    memset(head,255,sizeof(head));tot=-1;int n,m,k;scanf("%d%d%d",&n,&m,&k);vs=0;vt=k+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) scanf("%d",&val[i][j]);int s=0;for(int i=1;i<=k;i++) {
    int x,y,z;scanf("%d%d%d",&x,&y,&z);int v=abs(val[x][y])*z;s+=v;if (val[x][y]>=0) addEdge(vs,i,2*v);else addEdge(i,vt,2*v);pos[i]=pr(x,y);num[i]=z;}for(int i=1;i<k;i++)for(int j=i+1;j<=k;j++)if (abs(pos[i].FR-pos[j].FR)+abs(pos[i].SE-pos[j].SE)<=1) {
    int v=num[i]*num[j];s+=v;addEdge(i,j,2*v);addEdge(j,i,2*v);}printf("%d\n",s-Flow::maxflow());Flow::bfs();for(int i=1;i<=k;i++) printf("%d ",(Flow::d[i]>=0)?1:-1);printf("\n");}return 0;
} 

Chef and Rainbow Road

容易得到答案即为$({\prod }_{i=1}^N{a}_i)[x^{K?1}]\frac{1}{{\prod }_{i=1}^N(1?a_{i}x)}$。
对于$M\le 10^5$的数据，直接分治乘出分母后多项式求逆即可，时间复杂度为$\mathcal{O}(N{\log }^{2}N+M\log M+Q)$。
对于后面的测试点，可以用上次codechef月赛的A Leisurely Journey的技巧，同样将后面的生成函数分解部分分式之和，询问就可以用快速幂在$\mathcal{O}(N\log M)$的时间复杂度内完成。这里因为保证了$a_i$互不相同，所以只需要多点求值即可。
多点求值用了negiizhao等人引入的新写法，好写还跑的飞快，这里有介绍。时间复杂度为$\mathcal{O}(Nlo{g}^{2}N+QN\log M)$。

#include <bits/stdc++.h>
#define MOD 998244353using namespace std;typedef long long ll;ll pow_mod(ll x,ll k) {
    ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
} const int Maxn=1<<18;ll *w[18];void ntt_init() {
    for(int i=2,t=0;i<=Maxn;i<<=1,t++) {
    w[t]=new ll[i>>1];ll wn=pow_mod(3,(MOD-1)/i);w[t][0]=1;for(int j=1;j<(i>>1);j++) w[t][j]=w[t][j-1]*wn%MOD;}
}void rev(ll *p,int len) {
    int j=len>>1;for(int i=1;i<len-1;i++) {
    if (i<j) swap(p[i],p[j]);int k=len>>1;while (j>=k) {
    j-=k;k>>=1;}if (j<k) j+=k;}
}void ntt(ll *p,int len,int check) {
    rev(p,len);for(int i=2,t=0;i<=len;i<<=1,t++)for(int j=0;j<len;j+=i)for(int k=j;k<j+(i>>1);k++) {
    ll u=p[k];ll v=w[t][k-j]*p[k+(i>>1)];p[k]=(u+v)%MOD;p[k+(i>>1)]=(u-v)%MOD;}if (check==-1) {
    reverse(p+1,p+len);ll nev=pow_mod(len,MOD-2);for(int i=0;i<len;i++) p[i]=(p[i]+MOD)*nev%MOD;}
}void getinv(ll *p,ll *q,int len) {
    static ll t1[Maxn];if (len==1) {
    q[0]=1;return;}getinv(p,q,len>>1);memcpy(t1,p,sizeof(ll)*len);memset(t1+len,0,sizeof(ll)*len);ntt(q,len<<1,1);ntt(t1,len<<1,1);for(int i=0;i<(len<<1);i++) q[i]=q[i]*(2LL-q[i]*t1[i]%MOD)%MOD;ntt(q,len<<1,-1);memset(q+len,0,sizeof(ll)*len);
}void mul(vector<int> &a,vector<int> &b,vector<int> &c) {
    static ll t1[Maxn],t2[Maxn];int len=1;while (len<a.size()+b.size()) len<<=1;for(int i=0;i<a.size();i++) t1[i]=a[i];for(int i=0;i<b.size();i++) t2[i]=b[i];for(int i=a.size();i<len;i++) t1[i]=0;for(int i=b.size();i<len;i++) t2[i]=0;ntt(t1,len,1);ntt(t2,len,1);for(int i=0;i<len;i++) t1[i]=t1[i]*t2[i]%MOD;ntt(t1,len,-1);c.resize(a.size()+b.size()-1);for(int i=0;i<c.size();i++) c[i]=t1[i];
}void mulT(vector<int> &a,vector<int> &b,vector<int> &c,int n) {
    static ll t1[Maxn],t2[Maxn];int len=1;while (len<=a.size()||len<=((b.size()+1)<<1)) len<<=1;for(int i=0;i<a.size();i++) t1[i]=a[i];for(int i=0;i<b.size();i++) t2[b.size()-i-1]=b[i];for(int i=a.size();i<len;i++) t1[i]=0;for(int i=b.size();i<len;i++) t2[i]=0;ntt(t1,len,1);ntt(t2,len,1);for(int i=0;i<len;i++) t1[i]=t1[i]*t2[i]%MOD;ntt(t1,len,-1);c.resize(n);for(int i=0;i<c.size();i++) c[i]=t1[b.size()+i-1];
} vector <int> f[400000],g[400000];
ll num[100005],val[100005];void dfs1(int l,int r,int o) {
    if (l==r) {
    f[o].resize(2);f[o][0]=1;f[o][1]=(MOD-num[l])%MOD;}else {
    int m=((l+r)>>1);dfs1(l,m,o*2);dfs1(m+1,r,o*2+1);mul(f[o*2],f[o*2+1],f[o]);}
}void dfs2(int l,int r,int o) {
    if (l==r) val[l]=g[o][0];else {
    int m=((l+r)>>1);mulT(g[o],f[o*2+1],g[o*2],m-l+1);mulT(g[o],f[o*2],g[o*2+1],r-m);dfs2(l,m,o*2);dfs2(m+1,r,o*2+1);}
}void evaluation(int n) {
    static ll t1[Maxn],t2[Maxn];dfs1(1,n,1);for(int i=0;i<=n;i++) t1[i]=f[1][i];int len=1;while (len<=n) len<<=1;getinv(t1,t2,len);vector<int> full,inv;full.resize(n);inv.resize(n);for(int i=0;i<n;i++) {
    full[i]=(ll)(i+1)*f[1][n-i-1]%MOD;inv[i]=t2[i];}mulT(full,inv,g[1],n);dfs2(1,n,1);
} void solve1(int n,int k,int m) {
    static ll t1[Maxn],t2[Maxn];dfs1(1,n,1);for(int i=0;i<=n;i++) t1[i]=f[1][i];int len=1;while (len<=max(n,m)) len<<=1;getinv(t1,t2,len);ll s=1;for(int i=1;i<=n;i++) s=s*num[i]%MOD;for(int i=1;i<=k;i++) {
    int x;scanf("%d",&x);printf("%lld\n",s*t2[x-1]%MOD);}
}void solve2(int n,int k) {
    evaluation(n);for(int i=1;i<=n;i++) val[i]=pow_mod(val[i],MOD-2)*pow_mod(num[i],n-1)%MOD;for(int i=1;i<=k;i++) {
    ll x;scanf("%lld",&x);ll s=0;for(int i=1;i<=n;i++)s=(s+val[i]*pow_mod(num[i],x-1))%MOD;for(int i=1;i<=n;i++) s=s*num[i]%MOD;printf("%lld\n",s);}
}int main() {
    ntt_init();ll m;int n,k;scanf("%lld%d%d",&m,&n,&k);for(int i=1;i<=n;i++) scanf("%lld",&num[i]);if (m<=1e5) solve1(n,k,m);else solve2(n,k);return 0;
}

Precise Bipartite Pairing

看这篇博客最后一个算法的介绍即可。
实现的时候代入$0?N?v$作为$y$即可。后面插值和开方因为范围不大，都可以写平方的。
时间复杂度为$\mathcal{O}(N^{4}v+N^2{v}^2)$。

#include <bits/stdc++.h>
#define MOD 998244353
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<ll,ll> pr;mt19937 rnd(19260817);ll pow_mod(ll x,int k) {
    ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
}int a[105][105];ll gause(int n) {
    ll ans=1;for(int i=1;i<=n;i++) {
    if (!a[i][i]) {
    for(int j=i+1;j<=n;j++)if (a[j][i]) {
    ans=MOD-ans;for(int k=i;k<=n;k++) swap(a[i][k],a[j][k]);break;}}if (!a[i][i]) return 0;ll inv=pow_mod(a[i][i],MOD-2);for(int j=i+1;j<=n;j++)if (a[j][i]) {
    ll v=inv*a[j][i]%MOD;for(int k=i;k<=n;k++) a[j][k]=(a[j][k]-a[i][k]*v%MOD+MOD)%MOD;}}for(int i=1;i<=n;i++) ans=ans*a[i][i]%MOD;return ans;
}ll num[2005],val[2005];void lagrange(int n) {
    static ll t1[2005],t2[2005];t1[0]=1;for(int i=0;i<=n;i++)for(int j=i+1;j>=0;j--) {
    t1[j]=(MOD-i)*t1[j]%MOD;if (j) t1[j]=(t1[j]+t1[j-1])%MOD;}for(int i=0;i<=n;i++) {
    for(int j=0;j<=n+1;j++) t2[j]=t1[j];for(int j=n+1;j>0;j--)t2[j-1]=(t2[j-1]+t2[j]*i)%MOD;ll s=1;for(int j=0;j<=n;j++)if (j!=i) s=s*(i-j+MOD)%MOD;s=pow_mod(s,MOD-2)*val[i]%MOD; for(int j=0;j<=n;j++) num[j]=(num[j]+t2[j+1]*s)%MOD;}
}ll W;pr mul(pr x,pr y) {
    return pr((x.FR*y.FR+x.SE*y.SE%MOD*W)%MOD,(x.FR*y.SE+x.SE*y.FR)%MOD);
}pr pair_mod(pr x,int k) {
    pr ans(1,0);while (k) {
    if (k&1) ans=mul(ans,x);x=mul(x,x);k>>=1;}return ans;
}ll cipolla(ll x) {
    for(;;) {
    ll t=(ll)(abs(rnd()))%MOD;W=(t*t-x+MOD)%MOD;if (pow_mod(W,(MOD-1)>>1)!=MOD-1) continue;pr s=pair_mod(pr(t,MOD-1),(MOD+1)>>1);return s.FR;}
}ll ans[2005];bool getsqrt(int n) {
    int d=0;while (d<=n&&!num[d]) d++;if (d>n) return 0;assert(!(d&1));ll t=cipolla(num[d]);ans[d>>1]=t;ll inv=pow_mod(2LL*t%MOD,MOD-2);for(int i=d+1;i<=n;i++) {
    ll s=num[i];for(int j=(d>>1)+1;j<i-(d>>1);j++)s=(s-ans[j]*ans[i-j]%MOD+MOD)%MOD;ans[i-(d>>1)]=s*inv%MOD;}return 1;
}struct Edge {
    int s,t,v;Edge() {
    }Edge(int a,int b,int c):s(a),t(b),v(c) {
    }
};Edge e[10005];
int d[10005];int main() {
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {
    int x,y,z;scanf("%d%d%d",&x,&y,&z);x++;y++;e[i]=Edge(x,y,z);d[i]=(ll)(abs(rnd()))%MOD;}for(int i=0;i<=2000;i++) {
    memset(a,0,sizeof(a));ll mi[25];mi[0]=1;for(int j=1;j<=20;j++) mi[j]=mi[j-1]*i%MOD;for(int j=1;j<=m;j++) {
    ll v=d[j]*mi[e[j].v]%MOD;a[e[j].s][e[j].t]=v;a[e[j].t][e[j].s]=(MOD-v)%MOD;}val[i]=gause(n);} lagrange(2000);if (!getsqrt(2000)) {
    puts("YOU ARE IN TROUBLE");return 0;}int s=0;for(int i=0;i<=1000;i++)if (ans[i]) s++;printf("%d\n",s);for(int i=0;i<=1000;i++)if (ans[i]) printf("%d ",i);printf("\n");return 0;
}