问题 C: 飞(fly)
时间限制: 1 Sec 内存限制: 32 MB题目描述
liu_runda决定提高一下知识水平,于是他去请教郭神.郭神随手就给了liu_runda一道神题,liu_runda并不会做,于是把这个题扔到联考里给高二的做.
郭神有n条位于第一象限内的线段,给出每条线段与x轴和y轴交点的坐标,显然这样就可以唯一确定每一条线段.
n条线段和y轴交点的纵坐标分别为1,2,3,4...n.我们记和y轴交点纵坐标为i的线段和x轴交点的横坐标为x[i]+1,x[i]按这样的方式生成:
x[1]由输入给出.
x[i]=(x[i-1]+a) % mod,2<=i<=n.
即:如果x[3]=4,则与y轴交点纵坐标为3的抛物线,和x轴交点的横坐标为4+1=5.
我们保证给出的n,x[1],a,mod使得所有的x[i]互不相同.
对于第一象限内的所有点(点的横纵坐标可以是任意实数),如果一个点被x条线段经过,它的鬼畜值就是x*(x-1)/2.
求第一象限内的所有点的鬼畜值之和.
【输入格式】
一行4个整数n,x[1],a,mod
【输出格式】
1行一个整数表示鬼畜值之和.
【样例输入1】(即sample1.in)
5 2 4 7
【样例输出1】(即sample1.ans)
5
【样例输入2】
见sample2.in,数据范围同第3,4个测试点
【样例输出2】
见sample2.ans
【样例输入3】
见sample3.in,数据范围同第5,6个测试点
【样例输出3】
见sample3.ans
【样例输入4】
见sample4.in,数据范围同第5,6个测试点
【样例输出4】
见sample4.ans
【样例输入5】
见sample5.in,数据范围同第5,6个测试点
【样例输出5】
见sample5.ans
【数据范围】
第1,2个测试点,n<=100.
第3,4个测试点,n<=10^5.
第5,6个测试点的数据,a<=10.
第7,8个测试点,x[1]=a.
第9,10个测试点,无特殊限制.
对于全部数据,1<=n<=1e7,1<=a<=1e5,1<=mod<=1e8,a,mod互质,n<mod,给出的n,x[1],a,mod使得所有的x[i]互不相同.
请选手注意,1e7个int类型的变量将占用大约40mb的内存,导致内存超限,本题得0分.
这道题当时一读完题根据之前做完的两道题就可以知道这道题绝对不简单，是用来区分省队和省一的，不过个人当前策略是以稳为重，所以权衡之后先打了O(n^2)的暴力，顺便输出一下样例，还好20分到手。其实到这里才发现自己这次考试有一点小失误，虽然第二题已经拿到70分，第三题也拿到20分，但我留给自己打正解的时间只剩下了一个小时，然后就尴尬了，这意味着我必须在第二道题可能很好得30分和第三题很可能很难得的80分之间做出抉择，于是乎我默默的选择了30分（虽然最后也没拿到，但个人认为这种策略没什么问题）。
由于在这道题上对于正解话费的时间不是太多，我就简单说一下了。当时看到前两道题的内存限制是512MB时松了一口气，然而这道题很幽默的只给了32MB，很明显，他要卡我们内存，虽然当时连题都没读，但是已经知道这道题不好打。
然后我就开始思考，很明显只有交点才会对答案造成贡献，然后我的注意力就全在交点上，忽视了鬼畜值的本质这一重要条件，然后就傻傻的蒙逼了。
现在说正解。
我们可以注意到每一个点的鬼畜值实际为有多少对直线在这个点相交，那么我们总的答案就变成了有多少对直线是相交的。通过高考知识我们可以很轻易的得知只有i<j,x[i]>x[j]时直线i,j才会对答案产生贡献。我们可以注意到一个很有趣的限制：所有x[i]互不相同。这说明了什么呢？如果说我们知道了一个位于0~a的点，那么他之后的点一直到x被mod模掉都是可知且唯一的。让我们接着观察，我们就会发现，每一组（从0~a中某个点开始一直到x[i]被模掉）都会在0～a,a~2a……中只出现一次，这就很有意思了。这道题固然x很大但我们似乎是可以接受O(n)左右的算法的。那我们就可以接着上面我们的分析想到如果我们从小到大枚举i那么一个边的贡献就是所有x[i]在他之后的点的个数。而又由我们之前发现各组织间的关系我们就可以发现如果说上一个点对于答案的贡献是x，那么这个点对于答案的贡献就是当前0~a中（不算当前组）有多少个x[i]。那么对于单个组我们就完全可以实现O(1)转移了。
对于组内对答案的贡献我们已经知道，那么我们要求的就是对于每组第一个数对于答案的贡献是多少以及0～a中有多少个点，让我们回到最初最让我们头疼的东西上来，内存。
我们可以发现a是三个数据中最小的，也是唯一可针对他开数组的。对于第一个数对于答案的贡献我们可以把它看作一共有多少条线段-0～x[start]一共有多少个线段。我们可以利用树状数组快速求出这个值，对于第二个数也是如此。然后将这组计算完毕后我们再把它们加到树状数组中去。这样，这道题我们就解决75%了。
还有25%是什么呢？就是对于x1>a的处理，我们可以把问题分为两步，先把x1减为比a小，然后在减去他对于答案的贡献，前半部分同上。对于后半部分，我们可以借鉴之前的思路，我们每个多出来的点对于答案的贡献是在他之前的点的个数，因此我们只要把上面的对于答案的贡献反过来求一下就好了。值得注意的是，我们最后一个点可能位于真正的起始点和假的起始点之间，但在他之后假的起始点对于他并没有贡献，我们应把它减去。但是我们又又要注意如果说我们刚好结束完一组，那么我们的起始点其实并未对答案做出贡献，还要在特判一下。
1 #include<iostream>View Code
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cstring>
5 #include<queue>
6 #include<algorithm>
7 #include<cmath>
8 #include<map>
9 #define N 100005
10 using namespace std;
11 int n,x1,a,mod,st,st2;
12 long long s1[N],s2[N],ans;//s1 qs, s2 sum
13 int lowbit(int x)
14 {
15 return x&(-x);
16 }
17 void add(int x,long long z)
18 {
19 for(int i=x;i<=a;i+=lowbit(i))
20 {
21 s1[i]++;
22 s2[i]+=z;
23 }
24 }
25 void get(int x,long long &aa,long long &bb)
26 {
27 long long sum1=0,sum2=0,sum3=0;
28 for(int i=x;i>0;i-=lowbit(i))
29 sum1+=s1[i];
30 for(int i=a;i>0;i-=lowbit(i))
31 {
32 sum2+=s2[i];
33 sum3+=s1[i];
34 }
35 aa=sum2-sum1;
36 bb=sum3;
37 return;
38 }
39 void work()
40 {
41 long long js=1,tt=st;
42 long long sum1,sum2;
43 get(st+1,sum1,sum2);
44 while(n)
45 {
46 ans+=sum1;
47 sum1-=sum2;
48 st+=a;
49 n--;
50 if(st>=mod)break;
51 js++;
52 }
53 st%=mod;
54 add(tt+1,js);
55 }
56
57 void find()
58 {
59 while(st>=a)
60 {
61 st-=a;
62 n++;
63 }
64 }
65 void re()
66 {
67 if(st<a)st=mod+2;
68 long long sum1=0,sum2=0;
69 for(int i=st2;i>0;i-=lowbit(i))
70 sum1+=s1[i];
71 for(int i=a;i>0;i-=lowbit(i))
72 sum2+=s1[i];
73 sum2--;
74 while(st2!=x1)
75 {
76 ans-=sum1;
77 sum1+=sum2;
78 if(st<st2&&st+a>st2)sum2--;
79 st2+=a;
80 }
81 }
82 int main()
83 {
84 scanf("%d%d%d%d",&n,&x1,&a,&mod);
85 if(x1<a)
86 {
87 st=x1;
88 while(n) work();
89 printf("%lld\n",ans);
90 }
91 else
92 {
93 st=x1;
94 find();
95 st2=st;
96 while(n)
97 work();
98 re();
99 printf("%lld\n",ans);
100 }
101 return 0;
102 }