第一场比赛（事实上当你看到这篇的时候可能连最后一场都考完了
考场上顺序开题。
\(\mathrm{A.}\mathbb{简单的区间}\)：不知道
\(\mathrm{B.}\mathbb{简单的玄学}\)：不知道
\(\mathrm{C.}\mathbb{简单的填数}\)：不知道
一开始觉得 \(\mathrm{B}\) 是个数学题，于是 \(\mathrm{2h}\) 的时间就过去了（
后来开始肝 \(\mathrm{A}\)，以一种神奇的方法来记录区间最大值，真正的达到了复杂度O(1)，正确性随机。
最后连 \(\mathrm{C}\) 的暴力都没打。
估分：\(0+100+0=100\)
实际：\(0+40+0=40\)
还是说正解吧（
\(\mathrm{A.}\mathbb{简单的区间}\)
考场上想的是找每个点往两边最远能延伸到哪两个点，则在这两个点组成的区间的含当前点的子区间的最大值也为当前这个点。
正解
分治
将原式转化为 \(sum_r-sum_{l-1}-max\equiv0\pmod{k}\)
用 \(\mathrm{ST}\) 表记录区间最大值以及最大值的编号，对于当前的区间 \([l,r]\)，设区间的最大值为 \(\max\)，它的编号为 \(mid\)。处理过 \(mid\) 的区间，然后往两边递归即可。
考虑优化，如果 \(r-mid<mid-l\)，枚举右端点，否则枚举左端点，复杂度为 \(n\log_2 n\)
用链表+前缀和的方式即可，最后记得把 \(l=r\) 的情况减去。
code
#include<iostream>
#include<cmath>
using namespace std;
const int N=3e5+5;
int n,k,cnt,ans;
int a[N],f[N][21],g[N][21],sum[N],tot[N*10];
int head[N];
struct Node
{
int x,f;
int nxt;
}e[(int)11e6];
void add(int id,int x,int f)
{
if(id<0) return;
e[++cnt].nxt=head[id];
e[cnt].f=f;
e[cnt].x=x;
head[id]=cnt;
}
void solve(int l,int r)
{
if(l>=r)
{
ans+=(l==r);
return;
}
int lg=log(r-l+1)/log(2);
int mx,mxid;
if(f[l][lg]>f[r-(1<<lg)+1][lg]) mx=f[l][lg],mxid=g[l][lg];
else mx=f[r-(1<<lg)+1][lg],mxid=g[r-(1<<lg)+1][lg];
mx%=k;
if(r-mxid<mxid-l)
{
for(int i=mxid;i<=r;i++)
{
add(mxid-1,(sum[i]-mx+k)%k,1);
add(l-2,(sum[i]-mx+k)%k,-1);
}
}
else
{
for(int i=l;i<=mxid;i++)
{
add(r,(sum[i-1]+mx)%k,1);
add(mxid-1,(sum[i-1]+mx)%k,-1);
}
}
solve(l,mxid-1);
solve(mxid+1,r);
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=(sum[i-1]+a[i])%k;
f[i][0]=a[i];
g[i][0]=i;
}
int lg=log(n)/log(2)+1;
for(int j=1;j<=lg;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
if(f[i][j-1]>f[i+(1<<(j-1))][j-1]) f[i][j]=f[i][j-1],g[i][j]=g[i][j-1];
else f[i][j]=f[i+(1<<(j-1))][j-1],g[i][j]=g[i+(1<<(j-1))][j-1];
}
}
solve(1,n);
for(int i=0;i<=n;i++)
{
tot[sum[i]]++;
for(int j=head[i];j;j=e[j].nxt) ans+=tot[e[j].x]*e[j].f;
}
cout<<ans-n<<endl;
return 0;
}
\(\mathrm{B.}\mathbb{简单的玄学}\)
唯一一道想到了正解的题。
但是交之前手欠了一下，给指数模了个 \((mod-2)\)，因此挂到 \(40\) 分。（悲）
正解
考虑从反面来解，只需求出都不相同的概率即可。
先考虑约分，分母中只含有因子 \(2\)，因此只需要记录分子中 \(2\) 的个数。
很显然，除去首项的 \(2^n\) 有 \(n\) 个 \(2\) 的因子，其余 \(2^n-a\) 与 \(a\) 的因子 \(2\) 的个数相同。
因此就转变成了求 \(m!\) 的因子 \(2\) 的个数，\(O(\log_2m)\) 即可。
分母共有 \(nm\) 个因子 \(2\)，因此一定能约去。
设这个因子 \(2\) 的个数为 \(cnt\)，接着再考虑取模。
\(2^{nm}\) 这一项，快速幂即可。
对于排列数，我们不难发现
而这题的模数又是很妙的 \(10^6+3\)，对于大于模数直接消掉，小于模数直接 \(O(m)\) 计算。
code
#include<iostream>
#include<cmath>
using namespace std;
long long n,m,q,ans,mul=1;
const long long mod=1e6+3;
long long up,down;
long long p=1;
int cnt,flag;
const double eps=1e-6;
long long power(long long b,long long p)
{
long long ans=1;
while(p)
{
if(p&1) ans=ans*b%mod;
p>>=1;
b=b*b%mod;
}
return ans;
}
int main()
{
cin>>n>>m;
q=m-1;
for(cnt=1;cnt<=60;cnt++)
{
p*=2;
if(p>m) break;
if(p==m)
{
flag=1;
break;
}
}
if(cnt>n||(cnt==n&&p<m)) up=down=1;
else
{
ans=n;
while(q)
{
q/=2;
ans+=q;
}
long long invn=power(2,n),invmod=power(power(2,ans),mod-2);
up=down=power(invn,m);
if(m<mod)
{
long long left=invn;
for(int i=1;i<=m;i++)
{
mul=mul*left%mod;
left--;
if(left<0) left+=mod;
}
up=(up-mul+mod)%mod;
}
up=up*invmod%mod;
down=down*invmod%mod;
}
cout<<up<<" "<<down<<endl;
return 0;
}
\(\mathrm{C.}\mathbb{简单的填数}\)
这道题考场上完全没看，直接说正解。
正解
设二元组 \(up_i\) 为每个 \(i\) 能填的最大的数以及连续的个数，\(down_i\) 为每个 \(i\) 能填的最小的数以及连续的个数。
正常转移即可，正着扫一遍，求出最大的 \(a_n\)。
当 \(a_i>up_i(val)\) 或 \(a_i<down_i(val)\) 时，直接返回 \(-1\)。
再倒着扫一遍，求出一种合法的序列 \(a\)。
code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cstdlib>
#include<climits>
#include<bitset>
#define val first
#define cnt second
using namespace std;
const int N=2e5+5;
int n;
int a[N],ans[N],vis[N];
pair<int,int> up[N],down[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(a[1]>1)
{
cout<<-1<<endl;
return 0;
}
a[1]=1;
up[1]=down[1]=make_pair(1,1);
for(int i=2;i<=n;i++)
{
up[i]=make_pair(up[i-1].val,up[i-1].cnt+1);
down[i]=make_pair(down[i-1].val,down[i-1].cnt+1);
if(up[i].cnt>2)
{
up[i].val++;
up[i].cnt=1;
}
if(down[i].cnt>5)
{
down[i].val++;
down[i].cnt=1;
}
if(a[i])
{
if(up[i].val<a[i]||down[i].val>a[i])
{
cout<<-1<<endl;
return 0;
}
if(up[i].val>a[i]) up[i]=make_pair(a[i],2);
if(down[i].val<a[i]) down[i]=make_pair(a[i],1);
}
}
if(up[n].cnt==1)
{
up[n].val=up[n-1].val;
up[n].cnt=up[n-1].cnt+1;
}
ans[n]=up[n].val;
for(int i=n-1;i>=1;i--)
{
if(a[i]) ans[i]=a[i];
else
{
ans[i]=min(ans[i+1],up[i].val);
if(vis[ans[i]]==5) ans[i]--;
}
vis[ans[i]]++;
}
cout<<up[n].val<<endl;
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
}