A. Reverse
考场跑了个dijstra就跑路，然后T了。。。。
其实dij用处不大，这题用BFS说不定还快点。但是直接大力BFS显然同样会T飞，考虑如何优化，问题的关键在于这张“图”的“边数”太多了，但是在BFS或者其他算法dij中，每个点第一次被访问就是该点的答案，也就是说，虽然我们多次扫到同一个点，但真正有意义的只有第一次
维护两个set，分别存剩余奇数和偶数，每次二分查找可以到达的点，一旦到达，立即删除，这样保证每个点只被扫一次
注意二分的边界，最大距离，一个是k的两端，还有就是反转的区间靠近边界。
code
#include <cstring>
#include <cstdio>
#include<set>
#include<queue>
using namespace std;
const int maxn=1000005;
bool flag[maxn],vis[maxn];
set<int>js,os;
set<int>::iterator lt,rt,it;
queue<int>q;
int d[maxn],n,k,m,s;
void getit(int x,int l,int r){
if((x&1)==(k&1)){
lt=js.lower_bound(l);
rt=js.upper_bound(r);
}else{
lt=os.lower_bound(l);
rt=os.upper_bound(r);
}
}
void pu(int x){
int l=max(k-x+1,x-k+1);
int r=min(n+n-k+1-x,x+k-1);
getit(x,l,r);
while(lt!=rt){
int v=*lt;
d[v]=d[x]+1;
q.push(v);
if(v&1)js.erase(v);else os.erase(v);
getit(x,l,r);
}
}
int main(){
scanf("%d%d%d%d",&n,&k,&m,&s);
for(int i=1;i<=m;++i){int x;scanf("%d",&x);flag[x]=1;}
for(int i=1;i<=n;++i)if(!flag[i]){
if(i&1)js.insert(i);
else os.insert(i);
}
memset(d,0x3f,sizeof(d));
d[s]=0;
q.push(s);if(s&1)js.erase(s);else os.erase(s);
while(!q.empty()){
int x=q.front();
q.pop();pu(x);
}
for(int i=1;i<=n;++i)
if(d[i]==d[n+3])printf("-1 ");
else printf("%d ",d[i]);
return 0;
}
B. Silhouette
感谢动动学长的题解
以下内容大多是抄的
首先对AB排序，这样对结果是没有影响的
最大的A与B不相等一定无解，否则一定有解
从大到小枚举每个高度S，对不同S分别处理
先看第一个S
设\(f[i]\)为至少\(i\)行合法的方案数，这个i可以理解为钦定的，对与多于i行不合法的被多次重复计算，后面需要容斥（好像还是个二项式反演？）
\(f[i]=C_a^i\times (S^i\times ((S+1)^{a-i}-S^{a-i}))^b\)
首先在a行中选至少i行不合法，选择方案数\(C_a^i\)
然后对每一列分开考虑
对于已选的i行，每个位置有\(0\)~\((s-1)\)共\(S\)种放法，总共\(s^i\)
对于未选的a-i行，每个位置有\((s+1)\)种放法\((S+1)^{a-i}\)要保证这些行合法所以减去不合法的\(s^{a-i}\)
那么对于每一列，方案数为\((S+1)^{a-i}-S^{a-i}\),一共b列，所以是b次方
\(f[i]\)求出后我们需要容斥出合法的方案数，这里直接放柿子，请自行理解主要是我不会证
\(res=\sum \limits_{i=0}^a(-1)^i\times f[i]\)
貌似需要二项式反演，学了再回来补坑吧
然后我们来考虑一般情况，共三种
第二三种可以看成特殊的第一种，（最大的S也是），我们考虑如何处理那个L形状的东西
先放柿子
\(f[i]=C_a^i\times (S^i\times ((S+1)^{a+c-i}-S^{a+c-i}))^b\times (S^i\times (S+1)^{a-i})^d\)
按照上面的方法我们再来解释一下
首先我们需要选出i行不合法，但是c已经合法了，所以我们只能从a中选所以是\(C_a^i\)
考虑那\(b\)列，跟上面一个道理，有\(i\)行不合法，\(a+c-i\)行合法
考虑\(c\)列同理，\(i\)行不合法，\(c-i\)行合法
容斥跟上面一样
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
const int mod=1e9+7;
long long a[maxn],b[maxn];
long long c[maxn],s[maxn<<1|1];
long long inv[maxn],jc[maxn],n;
long long qp(long long x,long long y){
long long ans=1;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
void ycl(){
jc[0]=1;
for(long long i=1;i<=100000;++i)jc[i]=jc[i-1]*i%mod;
inv[100000]=qp(jc[100000],mod-2);
for(long long i=100000;i>0;--i)inv[i-1]=inv[i]*i%mod;
}
long long getc(int a,int i){
return jc[a]*inv[i]%mod*inv[a-i]%mod;
}
long long work(int a,int b,int c,int d,int s){
long long res=0;
for(int i=0;i<=a;++i){
long long now=getc(a,i)*qp(qp(s,i)*((qp(s+1,a+c-i)-qp(s,a+c-i)+mod)%mod)%mod,b)%mod*qp(qp(s,i)*qp(s+1,a-i)%mod,d)%mod;
if(i&1)res=(res-now+mod)%mod;
else res=(res+now)%mod;
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
for(int i=1;i<=n;++i)s[(i<<1)-1]=a[i],s[i<<1]=b[i];
ycl();
sort(a+1,a+n+1);sort(b+1,b+n+1);sort(s+1,s+(n<<1)+1);
if(a[n]!=b[n]){
printf("0\n");
return 0;
}
s[0]=unique(s+1,s+(n<<1)+1)-s-1;
int pa=n+1,pb=n+1,na=n,nb=n;
long long ans=1;
for(int i=s[0];i;--i){
while(a[na-1]==s[i]&&na-1)--na;
while(b[nb-1]==s[i]&&nb-1)--nb;
ans=ans*work(pa-na,pb-nb,n-pa+1,n-pb+1,s[i])%mod;
pa=na;pb=nb;
}
printf("%lld\n",ans);
return 0;
}
C. Seat
对着学长的代码和注释理解了半天，终于理解了一点
总体思路是
对于第i个人，无论坐到哪个位置，距离最近的人的距离是一样的，所以根据距离最近的人的距离来分层处理，偶数区间的选择具有对称性，所以求出一侧更新另一侧
继承学长的光荣传统(\(skyh\)大神倾情压行代码加注释)，具体内容看代码注释
code+注释（注释才是核心）
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=1055;
int mod,n;
long long qp(long long x,long long y){
long long ans=1;
while(y){if(y&1)ans=(x*ans)%mod;x=(x*x)%mod;y>>=1;}
return ans;
}
bool vis[maxn];//预处理时标记哪里坐了小G
int inv[maxn];//预处理逆元1/i
int cnt[maxn];//有多少距离最近的人距离为i的
int odd[maxn];//有多少距离最近的人距离为i的，区间长度为偶数的
int pos[maxn];//第i个小G坐的位置，（任意一个合法位置）
int ans[maxn][maxn];//记录答案
int dp[maxn][maxn];//dp[i][j]该层坐下了i个人，还剩j个偶区间没有坐的概率
int g[maxn][maxn];//辅助数组
int main(){
scanf("%d%d",&n,&mod);
for(int i=1;i<=n;++i)inv[i]=qp(i,mod-2);
vis[0]=vis[n+1]=1;
for(int i=1;i<=n;++i){
int l=0,L=0,R=0;
while(l<=n){
int r=l+1;
while(!vis[r])++r;
if(r-l>R-L)R=r,L=l;
l=r;
}//找到当前最大区间（任一），LR记录左右端点，这里是开区间
int near=R-L>>1;//距离最近的人的距离
++cnt[near];if(R-L&1)++odd[near];//计数
pos[i]=L+near;//记录位置
vis[L+near]=1;//标记位置
}
int sum=n;//剩余人数
for(int i=1;i<=n;++i)//按照距离最近的人的距离分层处理
if(cnt[i]){
int l=sum-cnt[i]+1,r=sum;//当前处理的是第l-r个小G
if(i==1){
for(int j=l;j<=r;++j)
for(int k=l;k<=r;++k)
ans[j][pos[k]]=inv[cnt[i]];
//特殊处理叶子结点，每个人坐在这些位置概率均等
}else{
for(int j=0;j<=cnt[i];++j)for(int k=0;k<=odd[i];++k)dp[j][k]=0;//清零
dp[0][odd[i]]=1;//坐下0人，剩下odd[i]个偶区间的概率为1
int end=odd[i]+l-1;//l-end为偶区间end-r为奇区间----预处理时区间长度大的在前，到最近的点距离相同的偶区间比奇区间要大
for(int j=1;j<=cnt[i];++j){
int oddw=0;//偶区间
int jddw=0;//奇区间
for(int k=0;k<=odd[i];++k){
if(dp[j-1][k]==0)continue;//剪枝
int res=cnt[i]-j+1+k;//总数-已选数==未选数 未选数+偶区间数==决策点数（偶区间两个决策点）
if(k){//如果有偶区间
int w=dp[j-1][k]*k%mod*2%mod*inv[res]%mod;//选择偶区间的概率
oddw=(oddw+w*inv[odd[i]*2])%mod;//每个偶区间是这次被选的概率
dp[j][k-1]=(dp[j][k-1]+w)%mod;//更新
}
if(cnt[i]-odd[i]){//如果有奇区间。------我对这里的写法有疑惑，总计cnt[i]个区间，坐下了j-1个人，就是选择了j-1个区间，有odd[i]个偶区间，还有k个偶区间备选，那么奇数区间应为cnt[i]-odd[i]-j+1+odd[i]-k==cnt[i]-j-k+1，实测写cnt[i]-j-k+1可以AC，题解写法貌似更新了非法状态？
int w=dp[j-1][k]*(res-k-k+mod)%mod*inv[res]%mod;//选奇区间的概率
jddw=(jddw+w*inv[cnt[i]-odd[i]])%mod;//参考偶区间
dp[j][k]=(dp[j][k]+w)%mod;//同上
}
}
for(int u=l;u<=end;++u)ans[l+j-1][pos[u]]=(ans[l+j-1][pos[u]]+oddw)%mod,ans[l+j-1][pos[u]+1]=(ans[l+j-1][pos[u]+1]+oddw)%mod;//对偶区间每个决策点更新答案
for(int u=end+1;u<=r;++u)ans[l+j-1][pos[u]]=(ans[l+j-1][pos[u]]+jddw)%mod;//奇区间
}
for(int j=l;j<=end;++j){//偶区间
int L=pos[j]-i+1,R=pos[j]+i;//区间左右端点
for(int k=L;k<=R;++k)//区间内每个点
if(pos[j]!=k)//不能是决策点
for(int u=r+1;u<=n;++u){ //后面的小G
int s=(k<pos[j]?k+i+1:k-i);//选择不同决策点造成的两种可能，这里是取他的对称点
int w=ans[u][k]*inv[2]%mod;//u放到k的概率除以2更新u和对称点s，s也更新u，需要辅助数组g
g[u][k]=(g[u][k]+w)%mod;
g[u][s]=(g[u][s]+w)%mod;
}
for(int k=L;k<=R;++k)for(int u=r+1;u<=n;++u)ans[u][k]=g[u][k],g[u][k]=0;//取平均后更新原值
}
}
sum-=cnt[i];//更新剩余人数
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
printf("%d ",ans[i][j]);
puts("");
}
return 0;
}