牛客周赛59（A,B,C,D,E二维循环移位,F范德蒙德卷积）

比赛链接

官方讲解

很幸运参加了内测，不过牛客这消息推送天天发广告搞得我差点错过内测消息，差点进小黑屋，好在开赛前一天看到了。

这场不难，ABC都很签到，D是个大讨论，纯屎，E是需要对循环移位进行处理和转化，转化后很简单，如果看不懂我写的可以看官方的讲解，画图可能会比较好理解，F是数学，需要分开计算贡献，最后再来一步范德蒙德卷积优化，知识点不难就是比较冷门。

---

A TD

思路：

签到

code：

#include <iostream>
#include <cstdio>
using namespace std;int a,b;int main(){cin>>a>>b;cout<<1.0*a/b;return 0;
}

---

B 你好，这里是牛客竞赛

思路：

如果是以 https://www.nowcoder.com 或者 www.nowcoder.com 作为前缀开头的话，那就是牛客主站，输出 Nowcoder。如果是以 https://ac.nowcoder.com 或者 ac.nowcoder.com 作为前缀开头的话，那就是牛客竞赛，输出 Ac。剩下的就是其他网站。

找子串可以用 $string$ 自带的 $find$ 方法，它会返回第一个匹配的子串的下标，作为前缀开头的话就看 $find$ 的值是否为 $0$ 即可，是 $0$ 就说明一开始就匹配上了，也就是前缀。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int T;
string s;int main(){cin>>T;while(T--){cin>>s;if(s.find("https://ac.nowcoder.com")==0 || s.find("ac.nowcoder.com")==0)cout<<"Ac"<<endl;else if(s.find("https://www.nowcoder.com")==0 || s.find("www.nowcoder.com")==0)cout<<"Nowcoder"<<endl;else cout<<"No"<<endl;}return 0;
}

---

C 逆序数

思路：

一个序列里对任意的一对数只有正序和逆序两种关系，不是逆序就是正序。在一个序列里任取两个数的取法有 $C_n^2=\frac{n\ast (n-1)}{2}$ 种可能，也就是一共有这么多个关系，除了 $k$ 个逆序，剩下的就有 $\frac{n\ast (n-1)}{2}-k$ 个正序。

而翻转之后，正序就会变成逆序，逆序变成正序，不管你这个集合是怎么凑的，翻转之前是 $k$ 个逆序，$\frac{n\ast (n-1)}{2}-k$ 个正序，翻转之后就是 $\frac{n\ast (n-1)}{2}-k$ 个逆序，$k$ 个正序。

code：

#include <iostream>
#include <cstdio>
using namespace std;long long n,k;int main(){cin>>n>>k;cout<<n*(n-1)/2-k<<endl;return 0;
}

---

D 构造mex

思路：

我嘞个大讨论啊，屎题。我已经能预想到那好看的通过率了。

我讨论的方法如下：

1. 当 $k=0$ 时，就尽量让每个数都是 $1$，最后一个数放剩余的还没用掉的值。
   1. 当 $s<n$ 时，这时甚至做不到让每个位置都是 $1$，一定会有位置为 $0$，因此无解
   2. 当 $s\ge n$ 时，就可以用上面的思路来凑。
2. 当 $k\ne 0$ 时，先凑出 $0,1,2,\dots ,k-1$，这样 $mex$ 就等于 $k$ 了，然后再把剩余的值放在后面，剩余位置就都放 $0$。前面 $0,1,2,\dots ,k-1$ 一共 $k$ 个数，总和为 $tot=\frac{k\ast (k-1)}{2}$
   1. 有可能 $s<tot$，这时连前面的 $k$ 个数都凑不出来，因此无解。
   2. 有可能 $s=tot$，这时正好没有剩余的数，因此凑出前 $k$ 个数后后面都可以补 $0$
      1. 当位置个数 $n<k$ 时，位置不够，因此无解。
      2. $n\ge k$ 时，位置够，用上面的方法来凑。
   3. 有可能 $s-tot=k$，这时不能直接把剩余的值 $s-tot$ 放在后面，必须先拆出一个单独的 $1$ ，然后再把 $s-tot-1$ 放下，后面补 $0$。
      1. 有可能 $s-tot=k=1$，这时做不到先拆出一个单独的 $1$ ，然后再把 $s-tot-1$ 放下，因为也会冲突，这时无解。
      2. 有可能位置个数不够，即 $n<k+2$，这时无解
      3. 剩余情况，按上面的方法来凑。
   4. 按上面的方法来凑需要至少 $k+1$ 个位置，如果位置不够则无解，否则按上面的方法来凑。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;ll T,s,n,k;int main(){cin>>T;while(T--){cin>>s>>n>>k;if(k==0){if(s<n)cout<<"NO"<<endl;else {cout<<"YES"<<endl;cout<<s-n+1<<" ";for(int i=1;i<=n-1;i++)cout<<1<<" ";cout<<endl;}}else {ll tot=k*(k-1)/2;if(s<tot)cout<<"NO"<<endl;else {if(k==1 && s-tot==1)cout<<"NO"<<endl;else {if(s-tot==0){if(n<k)cout<<"NO"<<endl;else {cout<<"YES"<<endl;for(int i=0;i<k;i++)cout<<i<<" ";for(int i=k+1;i<=n;i++)cout<<0<<" ";cout<<endl;}}else if(s-tot==k){if(n<k+2)cout<<"NO"<<endl;else {cout<<"YES"<<endl;for(int i=0;i<k;i++)cout<<i<<" ";cout<<1<<" "<<s-tot-1<<" ";for(int i=k+3;i<=n;i++)cout<<0<<" ";cout<<endl;}}else {if(n<k+1)cout<<"NO"<<endl;else {cout<<"YES"<<endl;for(int i=0;i<k;i++)cout<<i<<" ";cout<<s-tot<<" ";for(int i=k+2;i<=n;i++)cout<<0<<" ";cout<<endl;}}}}}}return 0;
}

---

E 小红的X型矩阵

思路：

对一个正方形，我们可以统计出它两个对角线上有多少个 $1$，对角线上的位置总个数减去对角线上 $1$ 的个数就是对角线上 $0$ 的个数，也就是需要用操作 $1$ 把 $0$ 翻转成 $1$ 的次数。然后再统计出一共有多少个 $1$，减去对角线上 $1$ 的个数就是对角线以外其他位置上 $1$ 的个数，也就是需要需要用操作 $1$ 把 $1$ 翻转成 $0$ 的次数。这个快速统计对角线上 $1$ 的个数可以用斜着的前缀和来做。

这个循环移动我们可以看作是移动这两个对角线，但是我们对角线一旦循环移动了就会断成两段，就很难计数了，而且对于 $n$ 为奇数的情况，两个对角线还会有交点，我们交点只能算一次，但是用前缀和来快速计数就会算两次，很麻烦。

这时我们可以参考数组的循环移位，把数组复制一遍到后面。我们可以把这个正方形往 $x，y$ 轴各复制一遍，这样从 $(i,j)$ 到 $(i+n-1,j+n-1)$ 的这个矩形就相当于原矩形向左循环移位 $i-1$ 次，向上循环移位 $j-1$ 次。

我们枚举矩形的左上角坐标 $(i,j)$，这样对每一个正方形都对应一个循环移位后的正方形，统计所有正方形的答案，然后取最小值即可。

注意 $n$ 为奇数的时候，中间会有一个交点，前缀和对两个对角线计数会重复算一次，需要减掉。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1005;int n,a[maxn<<1][maxn<<1],s1[maxn<<1][maxn<<1],s2[maxn<<1][maxn<<1],tot;int main(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>a[i][j];tot+=a[i][j];a[i+n][j]=a[i][j+n]=a[i+n][j+n]=a[i][j];}for(int i=1;i<=2*n;i++)for(int j=1;j<=2*n;j++)s1[i][j]=s1[i-1][j-1]+a[i][j];for(int i=1;i<=2*n;i++)for(int j=1;j<=2*n;j++)s2[i][j]=s2[i-1][j+1]+a[i][j];int ans=1e9;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){//枚举左上角坐标 int t=0,t1=s1[i+n-1][j+n-1]-s1[i-1][j-1],t2=s2[i+n-1][j]-s2[i-1][j+n];t=t1+t2;if(n&1){t-=a[i+n/2][j+n/2];ans=min(ans,(2*n-1)-t+tot-t);}else {ans=min(ans,2*n-t+tot-t);}}cout<<ans<<endl;return 0;	
}

---

F 小红的数组回文值

思路：

内测时写了一个很神秘的暴力，结果过了，然后被加强数据卡死了。。。这个暴力其实本质上和正解差不多，就差一个范德蒙德卷积优化kuso。

这个题是求所有子序列的回文值，但是我们显然不可能枚举出所有的子序列，所以我们不妨转化一下视角，看每一对数的贡献。

当一对数不同，并且在某一个回文串中正好对应，那么它就会产生一次贡献，假设第 $i$ 个位置和第 $j$ 个位置的数在某一个回文串中对应，并且 $a_i\ne a_j$。怎么算出所有满足这两个数对应的回文串呢？

我们可以在前 $i-1$ 个位置和后 $n-j$ 个位置同时选出 $k$ 个数，在中间的 $j-i-1$ 个数中选若干个数，这样就凑出一个 $a_i$ 与 $a_j$ 对应的回文串了。

假设前后各有 $x,y$ 个数，也就是 $x=i-1,y=n-j$，那么选取的方案数就是 ∑ k = 0 m i n { x , y } C x k ∗ C y k ∗ 2 n − x − y − 2 \sum_{k=0}^{min\{x,y\}} C_x^k*C_y^k*2^{n-x-y-2} ∑k=0min{x,y}​Cxk​∗Cyk​∗2n−x−y−2。

因为 $n=2000$，所以我们可以枚举 $i,j$，算出对应的 $x,y$，然后再枚举 $k$。这样就是一个 $O(n^3)$ 的算法，会 $T$，但是如果我们如果能把枚举 $k$ 的过程优化掉，就可以压成 $O(n^2)$ 的了。

还真能，$2^{n-x-y-2}$ 和 $k$ 无关，可以提出来，前面的这个 ∑ k = 0 m i n { x , y } C x k ∗ C y k \sum_{k=0}^{min\{x,y\}} C_x^k*C_y^k ∑k=0min{x,y}​Cxk​∗Cyk​，我们不妨设 $x<y$（不然就交换 $x,y$），则 $={\sum }_{k=0}^x{C}_x^k\ast C_y^k={\sum }_{k=0}^x{C}_x^{x-k}\ast C_y^k$ 这一步可以通过范德蒙德卷积优化，得到 $=C_{x+y}^x$。范德蒙德卷积讲解可以看 OI wiki。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=2e3+5;
typedef long long ll;
const ll mod=1e9+7;int n,a[maxn];
ll qpow(ll a,ll b){ll ans=1,base=a%mod;b%=mod;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}ll fac[maxn],ifac[maxn];
ll C(ll x,ll y){//C_x^yif(x<y)return 0;return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}ll calc(ll x,ll y){if(x>y)swap(x,y);return qpow(2,n-x-y-2)*C(x+y,x)%mod;
}int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];fac[0]=1;for(int i=1;i<=2000;i++)fac[i]=fac[i-1]*i%mod;ifac[2000]=inv(fac[2000]);for(int i=2000;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;ll ans=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i]!=a[j])ans=(ans+calc(i-1,n-j));cout<<(ans%mod+mod)%mod<<endl;return 0;
}

内测时成功卡AC的 $O(n^3)$ 暴力代码（虽然最后还是被卡掉了）：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=2e3+5;
typedef long long ll;
const ll mod=1e9+7;int n,a[maxn],b[maxn];
ll qpow(ll a,ll b){ll ans=1,base=a%mod;b%=mod;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}ll fac[maxn],ifac[maxn];
ll C(ll x,ll y){//C_x^yif(x<y)return 0;return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}vector<int> c[maxn];ll calc(ll x,ll y){ll ans=0;for(int i=0;i<=min(x,y);i++)ans=(ans+C(x,i)*C(y,i))%mod;return qpow(2,n-x-y-2)*ans%mod;
}int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];memcpy(b,a,sizeof(b));sort(b+1,b+n+1);int tot=unique(b+1,b+n+1)-b-1;auto find=[&](int x)->int{return lower_bound(b+1,b+n+1,x)-b;};for(int i=1;i<=n;i++)a[i]=find(a[i]);for(int i=1;i<=n;i++)c[a[i]].push_back(i);fac[0]=1;for(int i=1;i<=2000;i++)fac[i]=fac[i-1]*i%mod;ifac[2000]=inv(fac[2000]);for(int i=2000;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;ll ans=0;for(int i=1;i<=n;i++){ans=(ans+C(n,i)*(i/2)%mod)%mod;}for(int i=1;i<=n;i++){for(int l=0;l<c[i].size();l++)for(int r=l+1;r<c[i].size();r++){ans=(ans-calc(c[i][l]-1,n-c[i][r]))%mod;}}cout<<(ans%mod+mod)%mod<<endl;return 0;
}