/*
The Most Important Things:
ljc chat with fyh on QQ
Ta说期末考Ta数学74分感觉不好
但是我觉得fyh是地表最强的鸭~~(of course encourge her)
About Today's Training:
玄学错误,没有开longlong+没有算好空间(还不如暴力)
还是得继续加油.
本来以为今天是AK局来着呢..
*/
Problem A password
求$\sum\limits _{i=1} ^n i^2 2^i$ 的值，对于100%的数据$n\leq 10^9$
公式题，考虑答案$\sum\limits _{i=1} ^n i^2 2^i = (n^2 - 2n+3)2^{n+1}-6$
其实就两次数列错位相减就行了。
$S_n = 1 \times 2+4 \times 2^2 + 9 \times 2^3 + ... + n^2 2^n$
那么$2S_n=1 \times 2^2 + 4 \times 2^3 + 9 \times 2^4 + ... + n^2 2^{n+1}$
相减,$S_n = 2S_n-S_n= n^22^{n+1}-(1\times 2+ 3\times 2^2 + ... + (2n-1) \times 2^n)= n^22^{n+1}-T_n $
其中$T_n = 1 \times 2 + 3\times 2^2 + ... + (2n-3) \times 2^{n-1} + (2n-1) \times 2^n $
那么$2T_n = 1 \times 2^2 + 3\times 2^3 + ... + (2n-3) \times 2^{n} + (2n-1) \times 2^{n+1} $
相减,$T_n=2T_n-T_n = (2n-1)2^{n+1}-2-2-2(2^2+2^3+2^4+...+2^n)$
使用等比数列求和公式，得,$T_n = (2n-1)2^{n+1}-2-8 \times (2^{n-1}-1)= (2n-3)2^{n+1} + 6$
带入可知,$S_n= n^2 2^ {n+1}-(2n-3)2^{n+1}-6=(n^2-2n+3)2^{n+1}-6$
然后输出就行，复杂度$O(log_2 n)$
# include<bits/stdc++.h>
# define int long long
# define pow Pow
using namespace std;
const int mo=;
int pow(int x,int n)
{
int ans=;
while (n) {
if (n&) ans=ans*x%mo;
x=x*x%mo;
n>>=;
}
return ans%mo;
}
signed main()
{
int n; cin>>n;
n=((pow(,n+)*(((n*n%mo-*n%mo+)+mo)%mo)-)+mo)%mo;
cout<<n;
return ;
}
password.cpp
Problem B memory
给出一个含有n个元素的序列a，维护下列三种操作共m个：
1.add x k 给a[x]加上k。
2.ask x y 查询区间[x,y]内所有数的和。
3.goto t 回到第t 次操作之后的状态对于100%的数据n,m<=1e5,空间为8MB
为什么要强调空间呢，就是不让用可持久线段树做。（我就那么做爆0了）
对于每一个操作用二叉树来维护，把每一个时间标号当做一个节点，每一个节点一定是从之前某一个节点"转移"过来
这种转移我们就在树上连边，单向边从过去那个节点连到当前节点。
离线做的时候用BIT维护区间和，同时回溯的时候回退，保证在一个节点的时候BIT中没有当前节点子树的信息。
对于每一个询问在离线dfs中处理。
复杂度$O(n log_2 n)$
# include <bits/stdc++.h>
using namespace std;
const int N=1e5+;
char s[];
int n,m;
int head[N],tot,ans[N];
struct edge{int pre,to;}a[N];
struct rec{int id,op,x,y;}q[N];
# define lowbit(x) (x&(-x))
int c[N];
void update(int x,int y){for (x;x<=n;x+=lowbit(x)) c[x]+=y;}
int query(int x) {int ret=; for (;x;x-=lowbit(x)) ret+=c[x];return ret;}
#undef lowbit
void adde(int u,int v)
{
a[++tot].pre=head[u];
a[tot].to=v;
head[u]=tot;
}
void dfs(int u)
{
if (q[u].op==) update(q[u].x,q[u].y);
else if (q[u].op==) ans[u]=query(q[u].y)-query(q[u].x-);
for (int i=head[u];i;i=a[i].pre) dfs(a[i].to);
if (q[u].op==) update(q[u].x,-q[u].y);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) {
int t; scanf("%d",&t);
update(i,t);
}
for (int i=;i<=m;i++) {
cin>>s;
if (s[]=='s') { //ask
adde(i-,i);
int x,y; scanf("%d%d",&x,&y);
q[i]=(rec) {i,,x,y};
} else if (s[]=='o') { //goto
int t; scanf("%d",&t);
adde(t,i);
} else { //add
int x,y; scanf("%d%d",&x,&y);
adde(i-,i);
q[i]=(rec) {i,,x,y};
}
}
dfs();
for (int i=;i<=m;i++)
if (q[i].op==) printf("%d\n",ans[i]);
return ;
}
memory.cpp
Problem C graph
给出n个点的坐标，保证其中至少有$\frac{1}{3}$的点在同一直线上，
求出两个点使得一条过这两个点的直线上过了至少$\frac{n}{3}$个点
对于100%的数据，$n \leq 900000,x_i,y_i \leq 10^9$
考虑随机化算法，随机选两个点，跑n个点判断这条直线可不可行，直到可行位置。
对于最差情况只有$\frac{n}{3}$符合条件，期望是$1-(1-\frac{C_{\frac{n}{3}}^2}{C_n^2})^{log_n} $
大概是99.999233084076%
复杂度$O(kn)$
# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N=1e6+;
struct rec{double x,y;}a[N];
int n;
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
int random(int x){return 1ll*rand()*rand()%x+;}
signed main()
{
srand(time(NULL)*);
n=read();
for (int i=;i<=n;i++) a[i].x=(double)read(),a[i].y=(double)read();
while (true) {
int p1=,p2=;
while (p1==p2) p1=random(n),p2=random(n);
int x1=a[p1].x,y1=a[p1].y;
int x2=a[p2].x,y2=a[p2].y;
double k=(double)(y1-y2)/(double)(x1-x2);
double b=(double)y1-(double)k*(double)x1;
int cnt=;
for (int i=;i<=n;i++)
if (fabs((double)a[i].x*k+b-(double)a[i].y)<=1e-) {
cnt++;
if ((double)cnt/(double)n>=(double)1.0/3.0) {
cout<<p1<<' '<<p2<<'\n';
return ;
}
}
}
return ;
}
graph.cpp
Problem D volume
求$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} |a_i-a_j|$
对于100%的数据$n\leq 5\times 10^5$
排序$O(nlog_2 n)$做法：记得long long （没开long long 见祖宗）
# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N=5e5+;
int a[N],n,ans;
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
inline void write(int x)
{
if (x<) x=-x,putchar('-');
if (x>) write(x/);
putchar(x%+'');
}
inline void qsort(int l,int r)
{
if (l==r) return;
int t=rand()%(r-l)+l;
swap(a[t],a[l]);
int v=a[l]; int i=l;int j=r;
while (i<j) {
while (i<j&&a[j]>v) j--;
if (i<j) {a[i]=a[j];i++;} else break;
while (i<j&&a[i]<v) i++;
if (i<j) {a[j]=a[i];j--;} else break;
}
a[i]=v;
if (l<j) qsort(l,j-);
if (i<r) qsort(i+,r);
}
signed main()
{
n=read();
for (int i=;i<=n;i++) a[i]=read();
qsort(,n);
int ret=;
for (int i=;i<=n;i++) ret+=a[i],ans+=a[i]*i-ret;
write(ans<<);
return ;
}
volume.cpp