飞(fly)(数学推导，liu_runda的神题)-白红宇

飞(fly)(数学推导，liu_runda的神题)

阅读量：5337 次

发布时间：2019-06-15

本文共 2231 字，大约阅读时间需要 7 分钟。

大概看了两三个小时的题解，思考量很大，实现简单........

20分：

明显看出，每个点的贡献是x*(x-1)/2;即组合数C(x,2)，从x个线段中选出2个的方案数，显然每次相交贡献为1，n^2枚举相交即可....

40分：

对于四十分，观察图像发现是实际就是求逆序对.....

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #define int long long10 #define MAXN 10100111 using namespace std;12 struct node{ int x,id;}e[MAXN];13 int c[MAXN];int N,A,MOD;14 int lowbit(int x){ return x&(-x);}15 void add(int x)16 {17 for(int i=x;i<=N;i+=lowbit(i))18 {19 c[i]++;20 }21 }22 int find(int x)23 {24 int ans=0;25 for(int i=x;i>=1;i-=lowbit(i))26 {27 ans+=c[i];28 }29 return ans;30 }31 bool cmp(node a,node b)32 {33 return (a.x!=b.x)?a.x

40分

部分分：

考虑a==x[1]

我们发现图像的一些性质

在x[i]的不断后移中，假设当x[j]时>MOD，

我们发现x[i]-x[j]是一段以a为公差的序列

为了避免枚举n，我们从a入手

因为公差的原因，将序列分成若干个长度为a的段，其实每次经过的点都是一定的

当x<a时

我们直接求解此时的ans=（i-1）-ask（now）now为当前值，非常明显，因为i-1是所有在它之前出现的数，ask(now)为不符合的....

之后

发现一个小性质，每次后移减少的值是一定的，即ask（a）

然后递推....

100 分：

在上述部分加入x[1]>a的情况

因为每次减的都是ask(a),但这是第一段在1-a中不存在，我们若是按上述方法求，在枚举中不会将

第一段不符合的值减去，那么......我们发现当枚举第二段时（一段就是长度大于mod后重新开始）

当此时长度now大于初始值时，需要减去1，因为这个1无法在ask(1)中得出啦啦啦....

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #define int long long10 #define MAXN 10100111 using namespace std;12 int x;13 int c[MAXN];int N,A,MOD;14 int lowbit(int x){ return x&(-x);}15 void add(int x)16 {17 for(int i=x;i<=A+1;i+=lowbit(i))18 {19 c[i]++;20 }21 }22 int find(int x)23 {24 int ans=0;25 for(int i=x;i>=1;i-=lowbit(i))26 {27 ans+=c[i];28 }29 return ans;30 }31 signed main()32 {33 scanf("%lld%lld%lld%lld",&N,&x,&A,&MOD);34 int anss=0;35 int last=x;36 int now=(x+A)%MOD;37 int cas=0;38 int now_fir=x;//printf("now_fir=%lld\n",now_fir);39 int k=0;40 for(int i=2;i<=N;++i)41 {42 //printf("i=%lld now=%lld last=%lld\n",i,now,last);43 if(now
              
               =x&&x>A&&k>=1)cas--;59 anss+=cas;60 }61 //printf("anss=%lld\n",anss);62 last=now;63 now=(now+A)%MOD;64 }65 printf("%lld\n",anss);66 }

View Code

转载于:https://www.cnblogs.com/Wwb123/p/11354911.html

你可能感兴趣的文章