A. 小学数学
20分暴力即可。40分将询问拆为 \(\leq t\) 减去 \(<s(\leq s-1)\) 的两个问题，然后将询问排序后做前缀和即可。
满分要求强制在线，将矩阵中所有元素排序，然后分成 \(\sqrt{nm}\) 个块，每个块记录二维前缀和（出现了多少次块内的数）。每次询问时先处理整块，对于整块外的数再单独判断即可。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=310;
int n,m;
int T;
int cnt[maxn][maxn];
struct node{
int x,y,v;
}d[maxn*maxn];
int f[maxn*maxn];
int num;
bool cmp(const node &A,const node &B){
return A.v<B.v;
}
int sum[maxn][maxn][maxn];
int top;
void deal(){
top++;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[top][i][j]=cnt[i][j]+sum[top][i-1][j]+sum[top][i][j-1]-sum[top][i-1][j-1];
}
bool out(int x,int y,int x1,int y1,int x2,int y2){
if(x<x1||x>x2) return 1;
if(y<y1||y>y2) return 1;
return 0;
}
int qury(int x1,int y1,int x2,int y2,int v){
int t=v/300;
int res=sum[t][x2][y2]+sum[t][x1-1][y1-1];
res=res-sum[t][x2][y1-1]-sum[t][x1-1][y2];
for(int i=t*300+1;i<=v;i++)
if(!out(d[i].x,d[i].y,x1,y1,x2,y2))
res++;
return res;
}
int main(){
freopen("bath2.in","r",stdin);freopen("bath2.out","w",stdout);
int q,tt;
scanf("%d%d%d%d",&n,&m,&q,&tt);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
d[++num]=(node){i,j,0};
scanf("%d",&d[num].v);
}
sort(d+1,d+num+1,cmp);
for(int i=1;i<=num;i++){
cnt[d[i].x][d[i].y]++;
f[i]=d[i].v;
if(i%300==0)
deal();
}
int x1,y1,x2,y2;
int s,t;
int ans1,ans2;
int ans=0;
for(T=1;T<=q;T++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
scanf("%d%d",&s,&t);
if(tt){
x1^=ans,x2^=ans;
y1^=ans,y2^=ans;
s^=ans,t^=ans;
}
x1=(x1+n-1)%n+1,x2=(x2+n-1)%n+1;
y1=(y1+m-1)%m+1,y2=(y2+m-1)%m+1;
if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1,y2);
if(s>t) swap(s,t);
s=lower_bound(f+1,f+num+1,s)-f,t=upper_bound(f+1,f+num+1,t)-f-1;
ans2=qury(x1,y1,x2,y2,t);
ans1=qury(x1,y1,x2,y2,s-1);
ans=ans2-ans1;
if(ans<0) return -1;
printf("%d\n",ans);
}
return 0;
}
B. 初中数学
首先，显然有:
\[\begin{aligned} d(i j) & =\sum_{x\mid i}\sum_{y\mid j}[(x,\frac{j}{y})=1]\\ & =\sum_{x\mid i}\sum_{y\mid j}[(x,y)=1] \end{aligned} \]特殊地，当 \((i,j)=1\) 时，\(d(i j)=d(i)\times d(j)\)。这可以说明 \(d(x)\) 是一个积性函数。于是就可以推式子了:
\[\begin{aligned} F(n,m) & =\sum_{i=1}^{n}\sum_{j=1}^{m} d(i^{2}) d(j^{2}) d(i j)\\ & =\sum_{i=1}^{n}\sum_{j=1}^{m} d(i^{2}) d(j^{2})\sum_{x\mid i}\sum_{y\mid j}[(x,y)=1]\\ & =\sum_{i=1}^{n}\sum_{j=1}^{m} d(i^{2}) d(j^{2})\sum_{x\mid i}\sum_{y\mid j}\sum_{k|x,k|y}\mu(k)\\ = &\sum_{i=1}^{n}\sum_{j=1}^{m} d(i^{2}) d(j^{2})\sum_{k|i,k|j}\sum_{x|\frac{i}{k}}\sum_{y|\frac{j}{k}}\mu(k)\\ = &\sum_{i=1}^{n}\sum_{j=1}^{m} d(i^{2}) d(j^{2})\sum_{k|i,k|j} d(\frac{i}{k}) d(\frac{j}{k})\mu(k)\\ = &\sum_{k=1}^{\min (n,m)}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor} d(i^{2} k^{2}) d(j^{2} k^{2}) d(i) d(j)\mu(k)\\ = &\sum_{k=1}^{\min (n,m)}\mu(k)(\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor} d(i^{2} k^{2}) d(i))(\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor} d(i^{2} k^{2}) d(i)) \end{aligned} \]由于 \(d(x)\) 是积性函数， 那么 \(h(x)=d(x^{2})\) 也是积性函数。
所以有:
\[F(n,m)=\sum_{d=1}^{\min (n,m)}\mu(d)(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} h(i d) d(i))(\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor} h(i d) d(i)) \]首先线性筛第出 \(d(x),h(x)\)。
暴力求是单次 \(O(n\log n)\) 的。这样就有 40 分了。
可以预处理一下前缀和， 做到预处理 \(O(n\log n)\)，单次询问 \(O(n)\)，但是需要 \(O(n\log n)\) 的辅助空间。可以拿到 50 分。
接下来 10 分的部分分， 由于 \(n=m\)，任意时刻 \(\lfloor\frac{n}{d}\rfloor=\lfloor\frac{m}{d}\rfloor\)，所以可以分块。
接下来 10 分的部分分， 由于 \(m\) 唯一， 所以可以离线出所有的答案。 因为对于所有的 \(d\)，当 \(n\) 从 1 取到 \(10^{5}\) 时， \(\lfloor\frac{n}{d}\rfloor\) 一共也只会变化 \(2\times 10^{5}\log 2\times 10^{5}\) 次， 所以复杂度一定是正确的。
由于当 \(d\) 取 \([5\times 10^{3}，2\times 10^{5}]\) 时， \(\lfloor\frac{n}{d}\rfloor\) 一共只会有 20 种取值， 所以 \(n， m\) 组合起来也不过 400 种取值， 不妨全部预处理出来， 当枚举到的 \(d\) 在 \([5\times 10^{3}，2\times 10^{5}]\) 中时，用预处理好的答案分块做，否则暴力做。暴力做的规模变为了原来的 \(\frac{1}{20}\)，可以接受。模数是 \(2^{30}\) ，自然溢出即可。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<ctime>
using namespace std;
void read(int &x)
{
char c=getchar(); x=0;
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}
const int maxn=2e5+10;
int n,m,last,col[maxn],Rr[maxn];
set<int> S0[maxn];
namespace SegTree{
int tr[maxn<<2];
#define Lc (nd<<1)
#define Rc (nd<<1|1)
#define mid ((s+t)>>1)
void update(int nd,int s,int t,int l,int r)
{
if (l<=s&&t<=r) {tr[nd]=l; return;}
if (tr[nd]) tr[Lc]=tr[Rc]=tr[nd],tr[nd]=0;
if (l<=mid) update(Lc,s,mid,l,r);
if (r> mid) update(Rc,mid+1,t,l,r);
tr[nd]=tr[Lc]==tr[Rc]?tr[Lc]:0;
}
int query(int nd,int s,int t,int id)
{
return tr[nd]?tr[nd]:id<=mid?query(Lc,s,mid,id):query(Rc,mid+1,t,id);
}
}
namespace Splay{
int son[maxn][2],fa[maxn],sz[maxn],val[maxn];
#define lc (son[x][0])
#define rc (son[x][1])
inline void update(int x)
{
sz[x]=sz[lc]+sz[rc]+val[x];
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
int d=son[y][1]==x;
int c=son[x][d^1];
if (c) fa[c]=y;
fa[y]=x; fa[x]=z;
if (z) son[z][son[z][1]==y]=x;
son[x][d^1]=y;
son[y][d]=c;
update(y); update(x);
}
void splay(int x,int f)
{
while (fa[x]!=f)
{
int y=fa[x],z=fa[y];
if (z==f) {rotate(x); break;}
if ((son[z][1]==y)^(son[y][1]==x))
rotate(x),rotate(x);
else
rotate(y),rotate(x);
}
}
int build(int l,int r,int f)
{
if (l>r) return 0;
int x=(l+r)>>1;
fa[x]=f;
lc=build(l,x-1,x);
rc=build(x+1,r,x);
update(x);
return x;
}
void init()
{
for (int i=1;i<=n;i++)
read(val[i<<1]);
build(1,n<<1,0);
}
void move(int f,int l,int r)
{
int tmp;
if (last) tmp=last;
else
{
set<int>::iterator it;
it=S0[f].lower_bound(l);
if (it==S0[f].begin()) tmp=(f<<1)-1;
else tmp=Rr[*(--it)]<<1;
}
l=(l<<1)-1; r<<=1;
splay(l,0);
splay(r,l);
int u=son[l][0],v=son[r][1];
son[l][0]=son[r][1]=0;
fa[u]=fa[v]=0;
update(r);
update(l);
if (u&&v)
{
for (;son[u][1];u=son[u][1]);
splay(u,0);
son[u][1]=v;
fa[v]=u;
update(u);
}
splay(tmp,0);
u=tmp; v=son[tmp][1];
if (!v)
{
fa[l]=u;
son[u][1]=l;
update(u);
}
else
{
fa[v]=r;
fa[l]=u;
son[u][1]=l;
son[r][1]=v;
update(r);
update(l);
update(u);
}
}
void modify(int x,int v)
{
splay(x<<1,0);
val[x<<1]=v;
update(x);
}
int size(int x)
{
splay((x<<1)-1,0);
splay(x<<1,(x<<1)-1);
return val[x<<1]+sz[son[x<<1][0]];
}
}
inline void Add(int l,int r,int fa)
{
Rr[l]=r;
col[l]=fa;
SegTree::update(1,1,n,l,r);
S0[fa].insert(l);
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
int op,x,l,r,v,pos,c;
read(n); read(m);
Splay::init();
Rr[n+1]=n+1;
Add(2,n,1);
Splay::move(1,2,n);
while (m--)
{
read(op);
if (op==0)
{
read(x); read(l); read(r); last=0;
int tmp=SegTree::query(1,1,n,l);
if (tmp!=l)
{
pos=tmp; c=col[pos]; tmp=Rr[pos]+1;
if (c-x) Splay::move(x,l,min(r,Rr[pos]));
last=Rr[pos]<<1;
if (Rr[pos]>r) Add(r+1,Rr[pos],c);
Rr[pos]=l-1; col[pos]=c;
}
for (pos=tmp;Rr[pos]<=r;pos=Rr[pos]+1)
{
c=col[pos];
if (c-x) Splay::move(x,pos,Rr[pos]);
last=Rr[pos]<<1;
S0[c].erase(pos);
}
if (pos<=r)
{
c=col[pos];
if (c-x) Splay::move(x,pos,r);
Add(r+1,Rr[pos],c);
S0[c].erase(pos);
}
Add(l,r,x);
}
if (op==1)
{
read(x); read(v);
Splay::modify(x,v);
}
if (op==2)
{
read(x);
printf("%d\n",Splay::size(x));
}
}
}
C. 高中数学
注意到 \(n>m\) 时，不存在合法的操作序列，答案为 \(0\)。又因为有\(nm\leq 10^5\) ，可以认
为 \(n<\sqrt{10^5}\) 。
我们可以将区间 \([l,r)\)看成一对括号（左括号在 \(l\) ，右括号在 \(r\)），位置 \(i\) 最终的值就是这个位置左边的左括号数量减去右括号数量。
设 \(dp[i][l][r]\) 表示在位置 \(i\) ，左边有 \(l\) 个左括号， \(r\) 个右括号的方案数，\(f[i][l][r]\) 表示这些方案当前的贡献和。每次先令 \(f[i][l][r] +=(l-r)^kdp[i][l][r]\)，再进行转移即可。转移只需要讨论 \(i+1\) 上是否放左括号以及右括号。复杂度为 \(O(n^2m)\) 。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define P puts("lala")
#define cp cerr<<"lala"<<endl
#define ln putchar('\n')
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
inline int read()
{
char ch=getchar();int g=1,re=0;
while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();
return re*g;
}
typedef long long ll;
typedef pair<int,int> pii;
const int M=100050;
const int mod=998244353;
ll qpow(ll a,int n)
{
ll ans=1;
for(;n;n>>=1,a=a*a%mod) if(n&1) ans=ans*a%mod;
return ans;
}
int f[55][55][55],n,m,k,a[M],sum=0;
void dfs(int roun,int l,int r)
{
if(roun==n+1)
{
for(int i=1;i<=m;++i) sum=(sum+qpow(a[i],k))%mod;
return ;
}
for(int l1=l+1;l1<=m;l1++) for(int r1=r+1;r1<=m;r1++)
{
for(int i=l1;i<r1;++i) a[i]++;
dfs(roun+1,l1,r1);
for(int i=l1;i<r1;++i) a[i]--;
}
}
void wj()
{
freopen("segment.in","r",stdin);
freopen("segment.out","w",stdout);
}
int main()
{
wj();
int i,j,opt,T;
n=read(); m=read(); k=read();
if(n>=m&&m>6) {puts("0");return 0;}
if(m<=6)
{
dfs(1,0,0);
printf("%d\n",sum);
return 0;
}
else if(k==1)
{
//memset(f,-1,sizeof(f));
for(int l=1;l<=m;++l) for(int r=l;r<=m;++r) f[n+1][l][r]=0;
int ans=0;
for(i=n;i;--i) for(int l=0;l<=m;++l) for(int r=l;r<=m-(n-i+1);++r)
{
for(int l1=l+1;l1<=m;++l1) for(int r1=max(r+1,l1);r1<=m-(n-i);++r1)
{
//if(f[i+1][l1][r1]==-1) continue;
//if(f[i][l][r]==-1) f[i][l][r]=0;
f[i][l][r]=((ll)f[i][l][r]+f[i+1][l1][r1]+r1-l1)%mod;
}
//if(i==1) ans=(ans+f[i][l][r])%mod;
}
printf("%d\n",f[1][0][0]);
return 0;
}
else if(k==mod-1)
{
for(int l=1;l<=m;++l) for(int r=l;r<=m;++r) f[n+1][l][r]=0;
int ans=0;
for(i=n;i;--i) for(int l=0;l<=m;++l) for(int r=l;r<=m;++r)
{
for(int l1=l+1;l1<=m;++l1) for(int r1=r+1;r1<=m;++r1)
f[i][l][r]=((ll)f[i][l][r]+f[i+1][l1][r1]+r1-max(r-1,l1))%mod;
//if(i==1) ans=(ans+f[i][l][r])%mod;
}
printf("%d\n",f[1][0][0]);
return 0;
}
else if(n==1)
{
int ans=0;
for(int l=1;l<=m;++l)
ans=((ll)ans+(ll)(l+1+m)*(m-l)/2-1ll*(m-l)*l)%mod;
printf("%d\n",ans);
return 0;
}
return 0;
}