[考试反思]1113csp-s模拟测试114：一梦
自闭。不废话。写一下低错。
T1：觉得信心赛T1不会很恶心一遍过样例直接没对拍（其实是想写完T2之后回来对拍的）
状态也不好，基本全机房都开始码了我还没想出来（skyh已经开T2了）。想了40多分钟。
区别不大。真是人才。
而且反向的单调栈没reverse。爆零。
T2：100多分钟打表找到了一个仅适用于n,a<=5的规律（我还以为它是普适的，但其实n<=5,a<=5也不完全对）。浪费时间太多。
这次说实在的不是故意刚它的，因为打表不断有新进展所以很开心就没看时间。
T3：最后7分钟写的暴力得了和前198分钟一样的分数。
丢30分。求lca都不会打了。
真他妈难度中等有区分度看来我女队也混不了了2333。。。
把出题人挂起来婊
对自己没话可说了。那就干脆别废话了吧。
T1：A
可以发现，他给的二次函数没有c。有什么特性？一定经过原点？这个没什么用。
是可以整体除以x得到一次函数，正负分情况讨论。那么就剩下一个单调栈维护凸包板子。
写了对拍20分钟肯定是能调出来的。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define int long long 5 struct line{ 6 int k,b; 7 friend bool operator<(line A,line B){ 8 return A.k<B.k||(A.k==B.k&&A.b<B.b); 9 } 10 }l[500005]; 11 int ans[32323],sta[500005],top,negans[32323]; 12 int cal(int o,int x){return l[o].k*x*x+l[o].b*x;} 13 long double mp(int o,int p){return (0.0L+l[o].b-l[p].b)/(l[p].k-l[o].k);} 14 main(){ 15 freopen("A.in","r",stdin);freopen("A.out","w",stdout); 16 int n,q,x;scanf("%lld%lld",&n,&q); 17 for(int i=1;i<=n;++i)scanf("%lld%lld",&l[i].k,&l[i].b); 18 sort(l+1,l+1+n); 19 for(int i=1;i<=n;++i){ 20 while(top&&l[sta[top]].k==l[i].k&&l[sta[top]].b<l[i].b)top--; 21 while(top&&mp(sta[top],i)<1)top--; 22 while(top>1&&mp(sta[top-1],sta[top])>=mp(sta[top-1],i))top--; 23 sta[++top]=i; 24 }//for(int i=1;i<=top;++i)printf("%lld %lld ",l[sta[i]].k,l[sta[i]].b);printf("%lld ",l[2].k-l[3].k); 25 int ptr=1; 26 for(int X=1;X<32323;++X){ 27 while(ptr<top&&cal(sta[ptr],X)<=cal(sta[ptr+1],X))ptr++; 28 ans[X]=cal(sta[ptr],X); 29 } 30 top=0;ptr=1; 31 for(int i=n;i;--i){ 32 while(top&&l[sta[top]].k==l[i].k&&l[sta[top]].b>l[i].b)top--; 33 while(top>1&&mp(sta[top-1],sta[top])>=mp(sta[top-1],i))top--; 34 sta[++top]=i; 35 }reverse(sta+1,sta+1+top); 36 for(int X=-1;X>-32323;--X){ 37 while(ptr<top&&cal(sta[ptr],X)<=cal(sta[ptr+1],X))ptr++; 38 negans[-X]=cal(sta[ptr],X); 39 } 40 while(q--)scanf("%lld",&x),printf("%lld ",x>=0?ans[x]:negans[-x]); 41 }
T2：B
除了第一个以外，其余的每一位是不互相影响的。
那么答案就是$a_1 + sumlimits_{i=2)^{n} f(a_1,a_i) $
关键在于计算$f$函数。可以发现这个$f$函数的含义：
第一个物品被选完了，第二个物品期望被选多少个。
枚举它选了多少个，计算出概率，特殊处理被选完的情况，概率就是1-前面没被选的概率之和。
$f(a,b)=sumlimits_{i=0}^{b-1} frac{i imes C_{a+i-1}^{i}}{2^{a+i}} + b - sumlimits_{i=0}^{b-1}frac{b imes C_{a+i-1}^{i}}{2^{a+i}}$
+b前面的部分就是没选完，后面的部分就是选完了的剩余情况。组合数就是枚举这么多次选择恰好把它选完的方案数，除总方案数就是概率。
要-1的原因是最后一步要默认选择的是a而不是b。否则会重复计数。
再看本题的特殊之处，每次调用$f$函数的时候，第一个参数$a$都是一致的。
那么只要处理出来a这一列就好了。
可以发现，b每增大1，式子的变化之处并不多，前后的和式都多了一项。线性递推预处理即可。
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define int long long 5 #define mod 323232323 6 #define S 1000005 7 int qpow(int b,int t,int a=1){for(;t;t>>=1,b=b*b%mod)if(t&1)a=a*b%mod;return a;} 8 int fac[S],inv[S],pw[S],ipw[S],F[S],G[S],ans,x; 9 int C(int b,int t){return b<t?0:fac[b]*inv[t]%mod*inv[b-t]%mod;} 10 void f(){ 11 int totpos=0; 12 for(int i=0;i<500002;++i){ 13 F[i]=((i?F[i-1]:0)+i*C(x-1+i,i)%mod*ipw[x+i])%mod; 14 totpos=(totpos+C(x-1+i,i)*ipw[x+i])%mod; 15 G[i]=(1+i)*(1+mod-totpos)%mod; 16 } 17 for(int i=S-1;i;--i)F[i]=(F[i-1]+G[i-1])%mod; 18 } 19 main(){ 20 freopen("B.in","r",stdin);freopen("B.out","w",stdout); 21 fac[0]=1; 22 for(int i=1;i<S;++i)fac[i]=fac[i-1]*i%mod; 23 inv[S-1]=qpow(fac[S-1],mod-2); 24 for(int i=S-2;~i;--i)inv[i]=inv[i+1]*(i+1)%mod; 25 pw[0]=1; 26 for(int i=1;i<S;++i)pw[i]=pw[i-1]*2%mod; 27 ipw[S-1]=qpow(pw[S-1],mod-2); 28 for(int i=S-2;~i;--i)ipw[i]=ipw[i+1]*2%mod; 29 int n,y;scanf("%lld%lld",&n,&x);n--;ans=x;f(); 30 while(n--)scanf("%lld",&y),ans=(ans+F[y])%mod; 31 printf("%lld ",ans); 32 }