题解 P1494 【[国家集训队]小Z的袜子】

看了一下题解里的大佬,好像都用的莫队或者分块维护平方和…

其实用不着维护平方和。

从头开始说吧。

求什么

对于每个询问qq包含q.l,q.r),我们要求出任取两个袜子颜色相同的概率。假设在区间[l,r]取到颜色为i的袜子的概率为P(l,r,i),那么要求的就是\sum_{i=1} ^{n} P(q.l,q.r,i)

怎么求

那么对于任意的L,R,i,如何计算P(L,R,i)?假设在[L,R]i袜子的个数为n_i,根据数学知识,要取到两只i,首先要取第一只i颜色的袜子。因为有n_i只袜子都是i颜色的,所以取第一只i袜子的方案数为n_i。然后再取第二只i颜色的袜子。由于已经取了1只i颜色的袜子,就只剩下i-1只可选了。这样的排列数有n*(n-1)个。

计算概率时有顺序用排列,无顺序用组合,因为我们只关心两只袜子是否颜色相同,所以这道题中选袜子的顺序是没有影响的。而刚刚计算的只是排列数,每种组合方式被计算了2次(选第1,3只白袜和选第3,1只白袜是一样的)。所以要除以2。
即选到两只i颜色的袜子的方案数n_i(n_i-1)/2.

[L,R]内,有R-L+1只袜子,在这其中选择两只,方案总数为C_{R-L+1}^2。(都在刷国家集训队的题目了,你应该知道组合数吧….

所以P(L,R,i)=n_i*(n_i-1)/2 C_{R-L+1}^2 .

答案如前所述,为\sum_{i=1} ^{n} P(q.l,q.r,i)

怎么优化

1.分块。

如果直接对每个询问区间暴力维护n_iO(m* k n)级别的复杂度很显然过不了。(k是一个常数。其实我不太会分析复杂度所以欢迎dalao指正

以样例为例,(话说这个样例不会被敏感词拦截吗)

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

样例图解

我们发现一些询问都和其它某(几)个询问有重叠部分。那其实,我们可以把有重叠部分的询问分组,先处理每组的第一个询问,然后处理与上一个询问不同的部分。

于是我们可以先按照左端点的大小排序,然后把排序后的队列分成几个小块(一般大小取\sqrt{m})。然后再在每个块内以右端点大小排序。我们就可以以块为单位处理。

虽然左端点的单调性在第二次排序的时候打乱了,但是第一次排序保证了同一个块内相邻两个左端点的变化在\sqrt{n}内。第二排序可以保证右端点只有加操作,没有减操作。

2.统计

前面有些大佬提到了维护平方和的办法。但是其实我认为有更好的办法(每次修改三行代码变为一行)。
进入每一个块内处理的时候,我们先暴力求出第一组询问的区间内,每个袜子的个数,存在数组num里。然后在前一个询问的基础上,对num修改。
根据前面的推导,对每个询问q,我们要求的是

\sum_{i=1}^{n}P(q.l,q.r,i)=num_i*(num_i-1)/2 C_{q.r-q.l+1}^2 .

(C右上角的2不是平方的意思…)

可以看出,同一个询问的分母都是确定的。所以我们现在关心如何通过修改num来快速得到分子。

重点来了,假设原来的num_i=x

假如我们要对num_i执行增加1的操作,那么实际上跟i有关的那一部分的分子的变化为:
增加后-增加前=(x+1)x-x(x-1)=2x.所以我们直接加上原来x的两倍即可。

假如我们要对num_i执行减小1的操作,那么实际上i这一部分分子的变化为:

减少后-减少前= (x-1)(x-2)-x(x-1)=-2(x-1),所以我们直接减去减少后的num_i的两倍即可。

于是以前的更改代码为:(以增加为例)

{

    tot-=num[i]* num[i];
    num[i]++;
    tot+=num[i]* num[i]; 
}

现在只需要:

{
    tot+=2* num[i]++;
}

但是….分母不是还有一个2么,直接约分不就行了…

于是乘以2可以直接省略,得到:

{
    tot+=num[i]++;
}

不开O2 363ms

开O2 191ms

细节见代码:

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using std::sort;
const int maxn=50000;
struct que
{
    int l,r,id;
}q[maxn+5];
struct blk
{
    int l,r;
}b[333];
int col[maxn+5],num[maxn+5],ans1[maxn+5],ans2[maxn+5],c[maxn+5][3];
//依次保存 颜色,上文中的num数组,分子,分母,组合数
int n,m,bs,bn,tot;
//bs为每个块的大小 bn为块的个数
//排序后可以一边分块一边计算
inline void read(int &x){//快读
    x=0;
    char c;
    do{
        c=getchar();
    }
    while(c<'0'||c>'9');
    do{
        x=x*10+c-'0';
        c=getchar();
    }
    while(c>='0'&&c<='9');
}
inline int min(int a,int b){
    return a<b?a:b;
}
inline int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
inline bool cmpl(que a,que b){//以l排序
    return a.l<b.l;
}
inline bool cmpr(que a,que b){//以r排序
    return a.r<b.r;
}
inline void pre(){//计算组合数
    c[1][0]=c[1][1]=1;
    for(register int i=2,j;i<=n;++i){
        c[i][0]=1;
        for(j=1;j<=2;++j){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
    }
}
int main(){
    read(n);
    read(m);
    pre();
    for(register int i=1;i<=n;++i){
        read(col[i]);
    }
    for(register int i=1;i<=m;++i){
        read(q[i].l);
        read(q[i].r);
        q[i].id=i;
    }
    bs=sqrt(m);
    sort(q+1,q+1+m,cmpl);
    //整体按l排序,保证每个块内左端点的变化不会太大
    for(register int i=1,g;i<=m;i+=bs){
    //i为每个块的左边界
        b[++bn].l=i;
        b[bn].r=min(i+bs-1,m);
        sort(q+i,q+b[bn].r+1,cmpr);//块内按右端点排序 以免右边反复无用增减                    
        memset(num,0,sizeof(num));
        tot=0;//分子
        //先处理这个块里的第一个询问
        for(register int j=q[b[bn].l].l;j<=q[b[bn].l].r;++j){
            tot+=num[col[j]]++;
        }
        ans1[q[b[bn].l].id]=tot;
        ans2[q[b[bn].l].id]=c[q[b[bn].l].r-q[b[bn].l].l+1][2];
        //分母无需再乘以二,因为分子计算的时候省略了二
        if(ans1[q[b[bn].l].id]==0)ans2[q[b[bn].l].id]=1;
        else {
                g=gcd(tot,ans2[q[b[bn].l].id]);
                ans1[q[b[bn].l].id]/=g;
                ans2[q[b[bn].l].id]/=g;
         }

         //在前面的基础上,处理块内其他询问
        for(register int k,j=b[bn].l+1;j<=b[bn].r;++j){
             if(q[j-1].l<q[j].l){//处理这一次询问少了的部分(复原)
                 for(k=q[j-1].l;k<q[j].l;++k){
                    tot-=--num[col[k]];
                    //注意运算符在前(根据推导,这里使用减少后的值)
                 }
             }
             else {
                for(k=q[j].l;k<q[j-1].l;++k){//处理这一次询问多出来的部分
                    tot+=num[col[k]]++;
                    //注意运算符在后(根据推导,这里使用增加前的值)
                }
             }

             for(k=q[j-1].r+1;k<=q[j].r;++k){//处理这个询问后面多出来的部分
                tot+=num[col[k]]++;
             }
             ans1[q[j].id]=tot;
             ans2[q[j].id]=c[q[j].r-q[j].l+1][2];
             if(ans1[q[j].id]==0)ans2[q[j].id]=1;
             else {
                g=gcd(tot,ans2[q[j].id]);
                ans1[q[j].id]/=g;
                ans2[q[j].id]/=g;
             }
        }
    }
    for(register int i=1;i<=m;++i){
        printf("%d/%d\n",ans1[i],ans2[i]);
    }
    // system("pause");
    return 0;
}

祝AC..

数列分块心得

//作者过弱, 此文过水, 不建议阅读

关于标记的用法

例如,在动态维护区间和的时候(虽然很多时候用线段树或者树状数组更方便),假如每块有3个属性:add,l,rlr标记了它的左端点和右端点,但add有两种用法:

1.在查询整体和的时候使用。(李煜东的书给出的就是这种)

当要使第i块每个元素都增加c时,执行add[i]+=c,然后逐一更新该块中每一项的值a[j] ,使其增加c。//O(1)O(n)

当要查询时,如果查询该块的某部分,则逐一累加那一部分的元素然后返回;如果查询整体的和,就直接返回原始处理的sum加上add[i]*len[i]。//O(n)O(1)

2.查询部分元素的时候使用。

当要使第i块每个元素都增加c时,执行add[i]+=c,然后把sum[i]加上len[i]*c;//O(1)O(1)

当要查询时,如果查询该块的某部分,则逐一累加那一部分,然后加上add[i]*(这一部分的长度);如果查询整体的和,直接返回sum[i];//O(n)O(1)

第二种方法可以在修改的时候省掉一个O(n)

关于每块元素的个数

方法不同的话,长度为n的数列每一块的元素个数不一定是\sqrt{n},也不一定小于它。可能大于它。

例如,如果以李煜东书上的分块方法,给24个元素的数列分块,每一块的元素个数分别为:4,4,4,4,8。(就因为这个原因一道题卡了很久。不过他这种方法应该是错的吧…)

Hash

Hash表也叫散列表,可以将复杂而庞大的数据映射到一定的小范围内。缺点是可能出现冲突,但可以用链表的方法解决。

几个常用质数:99991,10007,131,13331。

10003不是质数。它等于7*1429;10007是,但100007不是,它等于97*1031;

字符串Hash

可以把字符串看做一个P进制的数,通过数的运算可以比较字符串字典序(先通过二分找到最长前缀,然后比较最长前缀的下一个数)。

例如,CH_1402 后缀数组

在结尾都相同时,可以这样写:

inline bool cmp(int a,int b){
int mid,l=0,r=min(len-a+1,len-b+1);
while(l>1;
if(eql(a,a+mid-1,b,b+mid-1)){//记得-1 求的是长度
l=mid;
}
else r=mid-1;
}
return s[a+l]<s[b+l];
}

如果结尾不同,在l等于它们其中任意一个字符串的长度时,s[a+l]s[b+l]可能访问到其它字符(如果都保存在同一个字符数组里的话)。

如果要求最长前缀的话也可以这样写,直接将返回类型bool改为int,并且返回l即可。

字符串哈希也可以用于比较两段字符串大小:

inline bool eql(int l1,int r1,int l2,int r2){
return f[r1]-f[l1-1]p[r1-l1+1]==f[r2]-f[l2-1]p[r2-l2+1];

如果要判断回文串,可以从前往后、从后往前分别开两个数组记录字符串的Hash。求最长回文串还有一个马拉车(Manacher)算法,找时间去研究一下。

随手写的,可能没有阅读体验,仅供自己学习。

以后遇到再来补充。

出栈的合法顺序

(这是一篇水贴)

在把1到n这n个数依次入栈的情况下,如何判断出栈的顺序是否合法?

如果仅仅要求顺序合法,我们可以在已经得到了一个出栈序列的情况下,以如下的方式判断。

         int A=1,B=1;
         stack s;
         while(A<=n){
             if(a[A]==B){
                 A++;B++;
             }
             else if(!s.empty()&&s.top()==a[A]){
                 s.pop();
                 A++;
             }
             else if(B<=n){
                 s.push(B++);
             }
             else {
                 break;//不合法
             }
         }

我们可以以生成全排列的方法,借用这种判断方式来暴力求出合理的出栈顺序的数量。(当然,可以数论直接求解)

也可以直接高效生成(以下代码来自SE大佬):

      inline void dfs(int s) {
      if(cnt == n) {
      num++;
      /* 
      for (int i = 1;i <= n; ++i) printf("%d", c[i]);  
      printf("\n");  
      */  
      return;  
  }
  if (top > 0) {
      int tp = a[top--];  
      c[++cnt] = tp;  
      dfs(s);  
      a[++top] = tp;
      cnt--;   
  }
  if (s <= n) { 
      a[++top] = s;  
      dfs(s+1);  
      top--;  
   }  
 }  
  int main(){  
      scanf("%d", &n);  
      dfs(1); 
      printf("%d", num);  
      return 0;  
  }  

矩阵乘法

写在最前面的话

由于自己太弱了,写这个来总结一下,方便复习。很多内容总结自维基百科(链接1链接2)和李煜东《算法竞赛进阶指南》。

适用范围

一个矩阵的列数等于另一个矩阵的行数时,它们的乘法才有意义。

运算方法

对于一个n*p的矩阵A和一个p*m的矩阵B,它们的乘积C 是一个 n*m 的矩阵。

A 矩阵和B矩阵乘积中的元素C_{[i,j]},等于A矩阵第i行的p个数和B矩阵第j列的p个数分别相乘的和。 即:

    \[C_{i,j} = \sum_{k=1}^{p} A_{i,k}*B_{k,j}\]

矩阵乘法同数的乘法一样,有结合律、分配律。但是交换因数后不一定能满足(n*p)*(p*m)的形式,即m不一定等于n,并且就算满足也不一定结果相等,所以矩阵乘法不满足乘法交换律。

纯乘法的代码实现

1.计算函数。由于自己太弱了,加上时间有限,写了一份很水的代码。

但是这里必须固定AB 的数组大小,可能vector可以解决这个问题?欢迎大佬们指教。

#include<cstdio>
int A[2][3]={
	{1,2,3},
	{4,5,6}
};
int B[3][4]={
	{1,2,3,4},
	{5,6,7,8},
	{9,10,11,12}
};
int c[2][4];
int n,m;
void mul(int a[][3],int b[][4],int n,int m,int p){
	for(int i=0;i<n;++i){//n 乘积的行数 
		for(int j=0;j<m;++j){//m 乘积的列数 
			for(int k=0;k<p;++k){//p 即共有的维 
				c[i][j]+=a[i][k]*b[k][j];
			}
			printf("c[%d][%d]=%d\n",i,j,c[i][j]);
		}
	}
}
int main(){
	mul(A,B,2,4,3);//计算A*B,并保存到c[][4]数组中 
	return 0;
}

2.有一种边读入边计算的写法:

	scanf("%lld%lld%lld",&n,&p,&m);
	for(long long i=1;i<=n;++i){
		for(long long j=1;j<=p;++j){
			scanf("%lld",&a[i][j]);
		}
	}
	for(long long i=1;i<=p;++i){
		for(long long j=1;j<=m;++j){
			scanf("%lld",&b[i][j]);
			for(long long k=1;k<=n;++k){//此处k枚举的并非是公共维
				ans[k][j]+=a[k][i]*b[i][j];
			}
		}
	}

需要注意的是,这里的k的含义与上一份代码不同。由于已经枚举了公共边(即第7行枚举的i)和列数j,这里只需要枚举乘积的行数。仍然是n*m*p三维。

我也不知道自己怎么就写了这么个没用的玩意。

用途

矩阵的一个重要用途是解线性方程组。线性方程组中未知量的系数可以排成一个矩阵,加上常数项,则称为增广矩阵。另一个重要用途是表示线性变换,即是诸如
f(x)=4x 之类的线性函数的推广。

——维基百科


1.其实蒟蒻的我并不知道怎么解线性方程组,但是对于矩阵加速线性变换有一些体会。让我们考虑一种比较特殊的矩阵乘法:1*nn*n。由定义可知,它们的乘积仍然是一个1*n的矩阵。那么有什么用呢?我们可以借助快速幂的思想,利用矩阵乘法的分配律、结合律,降低时间复杂度。

例如,POJ3070 这道题要求斐波那契数列第n项modm(给定n,m)的值。我们可以设一个1*2的矩阵A来存放F_{i},F_{i+1},然后通过设立方程,求出一个2*2的矩阵B,使得A*B得到的1*2的矩阵C,满足C=[F_{i+1},F_{i+2}]。于是,我们可以把时间复杂度由O(n)降低到O(log_{2}^{n})
我们可以通过设未知数解方程,使一个矩阵满足一定的性质。例如,当我们写快速计算矩阵乘法的函数时,函数里默认的矩阵(用于存放答案)应该初始化为什么呢?(计算快速幂时将对应变量初始化为1)如果全部初始化为0,就会导致任何符合条件的矩阵与其相乘都为0。

通过解方程,可以发现,一个2*2的矩阵

    \[  \left[  \begin{matrix}    1 & 0 \\    0 & 1 \\      \end{matrix}   \right] \]

与任何一个满足x==2x*y的矩阵相乘,结果仍然等于这个x*y的矩阵。

因此,我们可以把这个矩阵初始化为如上的矩阵,其作用等同于计算快速幂时的1;

2.以后遇到再来补充。

.

我觉得现在的喜剧电影还不如科幻甚至恐怖电影好笑,所谓笑点和煽情对白简直反智,就像是把几千个土味视频强行用一个剧情连起来一样。

又睡不着

北京时间2019年2月6日02:38,再一次睡不着的我又来翻一下手机。因为躺着等睡意除了可以突然得到一些白天再想起就会被自己否定的灵感外,还不如做点别的事情睡意来得快,只不过代价是心脏会疼两下。

垃圾短信已然突破722条,短短几天多了将近60条,可能我太受人喜欢了。

去年(或者前年)以前,光顾一些店的时候,人家都会叫我“H同学”。大概从去年(或者前年)开始,就变成了“H先生”。当时觉得自己真的老了。前几日成都行,成都人又把我叫“H同学”。也就罢了吧,今天(准确来说是昨天)去万达某店再次光顾,曾经一度叫我“H先生”的小伙伴居然再次叫起了“H同学”,甚至在另一家店买福袋还被问“你上初中还是高中啊”这样的问题——果然是这几天懒觉把我睡年轻了。

不过已经设置好7:30开始的连环闹钟,牺牲一点睡觉的时间,希望能从今天开始早睡早起。