A. matrix
分析
对于一个串，我们只在它第一次出现在某个矩形时计算答案，这样就可以去重
如果矩形的 \(l,r\) 确定了
那么对于第 \(i\) 行的字符串，它的贡献就是 \((n-i+1)(i-last[i])\)
\(last[i]\) 表示 \(i\) 这个字符串上一次是在第几行出现的
可以在 \(trie\) 的每一个节点上维护一个 \(set\) 来记录这个东西
假如我们已经有了 \(l=1\) 时的答案
那么将左端点向右移动实际上就相当于把根的所有儿子合并成新的根
用启发式合并，把 \(set\) 中元素较少的扔到元素较多的里面
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<map>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=5e5+5;
int n,m,rt,cnt,a[maxn];
std::map<int,int> mp[maxn];
std::set<int> s[maxn];
long long ans,tot;
#define sit std::set<int>::iterator
#define mit std::map<int,int>::iterator
void insert(rg int id){
rg int now=0;
rg sit it;
for(rg int i=1;i<=m;i++){
if(!mp[now][a[i]]) {
mp[now][a[i]]=++cnt;
s[cnt].insert(0);
}
now=mp[now][a[i]];
it=s[now].end();
++it;
tot+=1LL*(n-id+1)*(id-*it);
s[now].insert(id);
}
}
void xg(rg int now,rg int val){
if(s[now].find(val)!=s[now].end()) return;
s[now].insert(val);
rg sit it1,it2,it3;
it1=it2=it3=s[now].lower_bound(val);
if(it3==s[now].begin()) return;
else if(++it3==s[now].end()){
--it1;
tot+=1LL*(n-*it2+1)*(*it2-*it1);
} else {
++it2,--it1;
tot-=1LL*(n-*it2+1)*(*it2-*it1);
--it2;
tot+=1LL*(n-*it2+1)*(*it2-*it1);
++it1,++it2;
tot+=1LL*(n-*it2+1)*(*it2-*it1);
}
}
void del(rg int now){
rg int lat=0;
for(rg sit it=s[now].begin();it!=s[now].end();++it){
tot-=1LL*(n-*it+1)*(*it-lat);
lat=*it;
}
s[now].clear();
}
int bing(rg int aa,rg int bb){
if(!aa || !bb) return aa+bb;
if(s[aa].size()<s[bb].size()) std::swap(aa,bb);
for(rg sit it=s[bb].begin();it!=s[bb].end();++it) xg(aa,*it);
del(bb),s[bb].clear();
for(rg mit it=mp[bb].begin();it!=mp[bb].end();++it) mp[aa][it->first]=bing(mp[aa][it->first],it->second);
mp[bb].clear();
return aa;
}
void solve(){
del(rt);
ans+=tot;
rg int tmp=rt;
rg mit it=mp[tmp].begin();
rt=it->second;
++it;
for(;it!=mp[tmp].end();++it){
rt=bing(rt,it->second);
}
}
int main(){
n=read(),m=read();
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=m;j++) a[j]=read();
insert(i);
}
for(rg int i=1;i<=m;i++) solve();
printf("%lld\n",ans);
return 0;
}
B. sequence
分析
对于一个位置 \(i\)，以它为右端点的区间按位与值最多变化 \(log\) 次
所以将询问离线，按照右端点从大到小排序
记录一下变化的 \(log\) 个位置即可
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
int a[maxn],n,q,k,lat[maxn][35];
struct trr{
int l,r,laz,siz;
long long sum;
}tr[maxn<<2];
void push_up(rg int da){
tr[da].sum=tr[da<<1].sum+tr[da<<1|1].sum;
}
void push_down(rg int da){
if(tr[da].laz){
tr[da<<1].laz+=tr[da].laz,tr[da<<1|1].laz+=tr[da].laz;
tr[da<<1].sum+=1LL*tr[da].laz*tr[da<<1].siz,tr[da<<1|1].sum+=1LL*tr[da].laz*tr[da<<1|1].siz;
tr[da].laz=0;
}
}
void build(rg int da,rg int l,rg int r){
tr[da].l=l,tr[da].r=r,tr[da].siz=r-l+1;
if(l==r) return;
rg int mids=(l+r)>>1;
build(da<<1,l,mids),build(da<<1|1,mids+1,r);
push_up(da);
}
void xg(rg int da,rg int l,rg int r){
if(tr[da].l>=l && tr[da].r<=r){
tr[da].laz++,tr[da].sum+=tr[da].siz;
return;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) xg(da<<1,l,r);
if(r>mids) xg(da<<1|1,l,r);
push_up(da);
}
long long cx(rg int da,rg int l,rg int r){
if(tr[da].l>=l && tr[da].r<=r) return tr[da].sum;
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
rg long long nans=0;
if(l<=mids) nans+=cx(da<<1,l,r);
if(r>mids) nans+=cx(da<<1|1,l,r);
return nans;
}
struct jie{
int l,r,id;
}b[maxn*5];
bool cmp(rg jie aa,rg jie bb){
return aa.r<bb.r;
}
long long ans[maxn*5];
int sta[maxn],tp;
void updat(rg int id){
tp=0;
for(rg int i=1;i<=31;i++){
if(a[id]&(1<<(i-1))) sta[++tp]=lat[id][i];
}
std::sort(sta+1,sta+tp+1);
rg int sum=a[id],lat=id;
for(rg int i=tp;i>=1;i--){
if(sum%k==0 && sta[i]!=lat) xg(1,sta[i]+1,lat);
lat=sta[i];
sum&=a[sta[i]];
}
if(sum%k==0 && lat) xg(1,1,lat);
}
int main(){
n=read(),q=read(),k=read();
for(rg int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=31;j++){
if(a[i]&(1<<(j-1))) lat[i][j]=lat[i-1][j];
else lat[i][j]=i;
}
}
for(rg int i=1;i<=q;i++) b[i].l=read(),b[i].r=read(),b[i].id=i;
std::sort(b+1,b+q+1,cmp);
rg int head=1;
for(rg int i=1;i<=n;i++){
updat(i);
while(b[head].r==i && head<=q) ans[b[head].id]=cx(1,b[head].l,b[head].r),head++;
}
for(rg int i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}
C. permutation
分析
设 \(f[i][j]\) 为前 \(i\) 个元素从左到右有 \(j\) 个 \(lm\) 数的方案
强制让每一次加的元素是最小的
那么 \(f[i][j]=f[i-1][j-1]+(i-1)f[i-1][j]\)
含义是只有加在最前面的位置才能作出贡献，否则插在其它 \(i-1\) 个元素的后面都不会作出贡献
这个转移和第一类斯特林数是一样的
那么答案就是
\(ans=\sum\limits_{i=1}^{n}\begin{bmatrix}i-1\\A-1\end{bmatrix}\begin{bmatrix}n-i\\B-1\end{bmatrix}\binom{n-1}{A-1}\)
考虑组合意义
把 \(n − 1\) 个元素任意涂成黑白色,将黑色元素塞入 \(A − 1\) 个无区别的环,将
白色元素塞入 \(B-1\) 个无区别的环
等价于:把 \(n − 1\) 个元素塞入 \(A − 1 + B − 1\) 个无区别的环,将其中 \(A − 1\) 个环涂成白色, \(B − 1\) 个涂成黑色
\(ans=\begin{bmatrix}n-1\\A+B-2\end{bmatrix}\binom{A+B-2}{A-1}\)
\(nlogn\) 预处理出一行的第一类斯特林数即可
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=524288,mod=998244353,G=3;
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
inline int ksm(rg int ds,rg int zs){
rg int nans=1;
while(zs){
if(zs&1) nans=mulmod(nans,ds);
ds=mulmod(ds,ds);
zs>>=1;
}
return nans;
}
int w[23][maxn],wz[maxn],n,le,ri,ans;
void ntt(rg int A[],rg int lim,rg int typ){
for(rg int i=0;i<lim;i++) if(i<wz[i]) std::swap(A[i],A[wz[i]]);
for(rg int len=1,t0=0;len<lim;len<<=1,t0++){
for(rg int j=0,now=len<<1;j<lim;j+=now){
for(rg int k=0;k<len;k++){
rg int x=A[j+k],y=mulmod(A[j+k+len],w[t0][k]);
A[j+k]=addmod(x,y),A[j+k+len]=delmod(x,y);
}
}
}
if(typ==-1){
std::reverse(A+1,A+lim);
rg int ny=ksm(lim,mod-2);
for(rg int i=0;i<lim;i++) A[i]=mulmod(A[i],ny);
}
}
int ny[maxn],jc[maxn],jcc[maxn];
void pre(){
ny[1]=1;
for(rg int i=2;i<=n;i++) ny[i]=mulmod(mod-mod/i,ny[mod%i]);
jc[0]=jcc[0]=1;
for(rg int i=1;i<=n;i++) jc[i]=mulmod(jc[i-1],i),jcc[i]=mulmod(jcc[i-1],ny[i]);
}
int getC(rg int nn,rg int mm){
return mulmod(jc[nn],mulmod(jcc[mm],jcc[nn-mm]));
}
int a[maxn],b[maxn],c[maxn],d[maxn];
void solve(rg int l,rg int r){
if(l==r){
a[0]=0,a[1]=1;
return;
}
rg int mids=(l+r)>>1,len=r-l+1;
if(len&1) mids--;
solve(l,mids);
len=mids+1;
rg int lim=1,bit=0;
for(;lim<=len+len;lim<<=1) bit++;
for(rg int i=0;i<lim;i++) wz[i]=(wz[i>>1]>>1)|((i&1)<<(bit-1));
for(rg int i=0;i<=len;i++) b[i]=mulmod(ksm(len,i),jcc[i]);
for(rg int i=0;i<=len;i++) c[i]=mulmod(a[i],jc[i]);
for(rg int i=len+1;i<lim;i++) b[i]=c[i]=0;
ntt(b,lim,1),ntt(c,lim,-1);
for(rg int i=0;i<lim;i++) b[i]=mulmod(b[i],c[i]);
ntt(b,lim,1);
for(rg int i=len+1;i<lim;i++) b[i]=0;
for(rg int i=0;i<=len;i++) b[i]=mulmod(b[i],jcc[i]);
ntt(b,lim,1),ntt(a,lim,1);
for(rg int i=0;i<lim;i++) a[i]=mulmod(a[i],b[i]);
ntt(a,lim,-1);
for(rg int i=r+2;i<lim;i++) a[i]=0;
if((r-l+1)&1){
for(rg int i=0;i<=r;i++) d[i]=a[i],a[i]=0;
for(rg int i=1;i<=r+1;i++) a[i]=addmod(d[i-1],mulmod(d[i],r));
a[0]=mulmod(d[0],r);
}
}
int main(){
n=read(),le=read(),ri=read();
if(n==1){
if(le==1 && ri==1) printf("1\n");
else printf("0\n");
return 0;
}
rg int lim=1;
for(;lim<=n+n;lim<<=1);
for(rg int len=1,t0=0;len<lim;len<<=1,t0++){
w[t0][0]=1,w[t0][1]=ksm(G,(mod-1)/(len<<1));
for(rg int j=2;j<len;j++) w[t0][j]=mulmod(w[t0][1],w[t0][j-1]);
}
pre();
solve(0,n-2);
if(le+ri-2>n-1) ans=0;
else ans=mulmod(a[le+ri-2],getC(le+ri-2,le-1));
printf("%d\n",ans);
return 0;
}