51nod 省选联测 R2
上场的题我到现在一道都没A，等哪天改完了再写题解吧，现在直接写第二场的。
第二场比第一场简单很多（然而这并不妨碍我不会做）。
A.抽卡大赛：http://www.51nod.com/Challenge/Problem.html#!#problemId=1850
这题非常的神仙。
考试的时候没看见数据范围...以为是1e5，觉得非常不可做。结果其实是200？
$N^4$ 的做法挺好想的，首先枚举一个人，再枚举他的牌，然后计算其他人胜过他的概率，最后做一个 $N^2$ 的DP算答案，这里就不细讲了。
让我们换一下思路，不要再枚举人了，将所有的牌按从大到小排序后直接枚举牌。
下面这部分有一点难理解...在之前的做法中，要计算“i排第j名的概率”，在这里，因为不能枚举人，所以计算的就是“如果出现了一个拿着i这种牌的人，排第j名的概率”。乍一看，这个东西意义何在...但其实还是挺有用的。假设我们可以以 $O(N)$ 的效率从背包中撤出某个物品，那么当计算 $i$ 这个人时就撤掉它自己，算完后再加进去就可以了。因为每次加入一张新牌时，只有一个人“胜过更小的牌的概率”改变了，所以这样做的复杂度是 $N^3$ 的。
最后考虑如何删除背包里的物品：
最初的状态转移：
倒序枚举j，可以消掉一维：
考虑一下边界情况：
也就是说，如果要撤掉一个数，可以直接算出原来的 $f_1$ ，由此就可以进一步推出所有 $f$ 的原值，实现了删除物品。
# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
# define R register int using namespace std; const int maxn=;
const int mod=;
int n,inv_100;
int m,f[maxn],h[maxn],p[maxn],v[maxn],cnt,ans[maxn],b[maxn];
struct card { int a,g,p,id; }k[maxn*maxn]; int qui (int a,int b)
{
int s=;
while(b)
{
if(b&) s=1LL*s*a%mod;
a=1LL*a*a%mod;
b>>=;
}
return s;
} bool cmp (card a,card b) { return a.a>b.a; } void ins (int p) { for (R i=n;i>=;--i) f[i]=(1LL*f[i-]*p+1LL*f[i]*(mod+-p))%mod; } void del (int p)
{
int inv=qui(mod+-p,mod-);
for (R i=;i<=n;++i)
{
f[i]=1LL*f[i]*inv%mod;
f[i+]=(f[i+]-1LL*p*f[i]%mod+mod)%mod;
}
} int read()
{
int x=;
char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
return x;
} int main()
{
n=read();
inv_100=qui(,mod-);
for (R i=;i<=n;++i)
{
m=read();
for (R j=;j<=m;++j)
{
k[++cnt].id=i;
k[cnt].a=read(),k[cnt].g=read(),k[cnt].p=read();
p[i]=(p[i]+k[cnt].p)%mod;
k[cnt].g=1LL*(-k[cnt].g)*inv_100%mod;
}
p[i]=qui(p[i],mod-);
}
for (R i=;i<=cnt;++i) k[i].p=1LL*k[i].p*p[ k[i].id ]%mod;
for (R i=;i<=n;++i) v[i]=read();
sort(k+,k++cnt,cmp);
f[]=;
for (R i=;i<=n;++i)
ins();
for (R i=;i<=cnt;++i)
{
int x=k[i].id;
del(b[x]);
for (R j=;j<=n;++j)
ans[x]=(ans[x]+1LL*k[i].p*k[i].g%mod*f[j]%mod*v[j])%mod;
b[x]=(b[x]+k[i].p)%mod;
ins(b[x]);
}
for (R i=;i<=n;++i) printf("%d\n",ans[i]);
return ;
}
抽卡大赛
B.异或约数和：http://www.51nod.com/Challenge/Problem.html#!#problemId=1984
这题比较简单。
首先看看每个数会被算多少次，显然是 $\frac{n}{i}$ 次，如果这个数是个奇数，它就会出现在最终答案中，否则就不用管它了。
这种分式形式显然上来先套一个除法分块。考虑如何快速计算 $1$ 到 $n$ 的异或和。可以发现 1^2^3=0,(4n)^(4n+1)^(4n+2)^(4n+3)=0，所以就根据 $n \% 4$ 分类讨论即可。
# include <cstdio>
# include <iostream>
# include <cstring>
# include <string>
# include <cmath>
# include <algorithm>
# define ll long long
# define R register int using namespace std; ll n,ans; inline ll ask (ll l)
{
if(l%==) return l;
if(l%==) return ;
if(l%==) return l+;
return ;
} int main()
{
scanf("%lld",&n);
ll l=,r;
while(l<=n)
{
r=n/(n/l);
if((n/l)%) ans^=ask(r)^ask(l-);
l=r+;
}
printf("%lld",ans);
return ;
}
异或约数和
C.小朋友的笑话：http://www.51nod.com/Challenge/Problem.html#!#problemId=2014
每个人的状态可以认为只与最后听的那个笑话有关。
这里有一个极其神奇（也有可能只是我没见过）的做法：将每个笑话的出现过的区间...维护出来！因为一开始只想到用权值线段树维护区间，但是觉得复杂度不对就弃疗了，其实换成平衡树复杂度就对了。为什么呢？觉得复杂度不对的主要原因就是觉得一种笑话的区间可能很多，如果多次全部访问就会很慢，但其实这个问题是不存在的。如果两个区间出现了重叠，那么我们就把它们删掉，合成一个新的区间再加进去。每次最多加入一个区间，却可能删掉多个，且每个区间被加入后最多被访问一次就被删了，所以复杂度极其科学。
因为Set用的很不熟练，代码几乎是照搬这份题解，就不贴了。
---shzr