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$ 的原值，实现了删除物品。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <algorithm>
 5 # define R register int
 6 
 7 using namespace std;
 8 
 9 const int maxn=202;
10 const int mod=1000000007;
11 int n,inv_100;
12 int m,f[maxn],h[maxn],p[maxn],v[maxn],cnt,ans[maxn],b[maxn];
13 struct card { int a,g,p,id; }k[maxn*maxn];
14 
15 int qui (int a,int b)
16 {
17     int s=1;
18     while(b)
19     {
20         if(b&1) s=1LL*s*a%mod;
21         a=1LL*a*a%mod;
22         b>>=1;
23     }
24     return s;
25 }
26 
27 bool cmp (card a,card b) { return a.a>b.a; }
28 
29 void ins (int p) { for (R i=n;i>=1;--i) f[i]=(1LL*f[i-1]*p+1LL*f[i]*(mod+1-p))%mod; }
30 
31 void del (int p)
32 {
33     int inv=qui(mod+1-p,mod-2);
34     for (R i=1;i<=n;++i)
35     {
36         f[i]=1LL*f[i]*inv%mod;
37         f[i+1]=(f[i+1]-1LL*p*f[i]%mod+mod)%mod;
38     }
39 }
40 
41 int read()
42 {
43     int x=0;
44     char c=getchar();
45     while (!isdigit(c)) c=getchar();
46     while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
47     return x;    
48 }
49 
50 int main()
51 {
52     n=read();
53     inv_100=qui(100,mod-2);
54     for (R i=1;i<=n;++i)
55     {
56         m=read();
57         for (R j=1;j<=m;++j)
58         {
59             k[++cnt].id=i;
60             k[cnt].a=read(),k[cnt].g=read(),k[cnt].p=read();
61             p[i]=(p[i]+k[cnt].p)%mod;
62             k[cnt].g=1LL*(100-k[cnt].g)*inv_100%mod;
63         }
64         p[i]=qui(p[i],mod-2);
65     }
66     for (R i=1;i<=cnt;++i) k[i].p=1LL*k[i].p*p[ k[i].id ]%mod;
67     for (R i=1;i<=n;++i) v[i]=read();
68     sort(k+1,k+1+cnt,cmp);
69     f[1]=1;
70     for (R i=1;i<=n;++i)
71         ins(0);
72     for (R i=1;i<=cnt;++i)
73     {
74         int x=k[i].id;
75         del(b[x]);
76         for (R j=1;j<=n;++j)
77             ans[x]=(ans[x]+1LL*k[i].p*k[i].g%mod*f[j]%mod*v[j])%mod;
78         b[x]=(b[x]+k[i].p)%mod;
79         ins(b[x]);
80     }
81     for (R i=1;i<=n;++i) printf("%d
",ans[i]);
82     return 0;
83 }

抽卡大赛

　　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$ 分类讨论即可。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <string>
 5 # include <cmath>
 6 # include <algorithm>
 7 # define ll long long
 8 # define R register int
 9 
10 using namespace std;
11 
12 ll n,ans; 
13 
14 inline ll ask (ll l)
15 {
16     if(l%4==0) return l;
17     if(l%4==1) return 1;
18     if(l%4==2) return l+1;
19     return 0; 
20 }
21 
22 int main()
23 {
24     scanf("%lld",&n);
25     ll l=1,r;
26     while(l<=n)
27     {
28         r=n/(n/l);
29         if((n/l)%2) ans^=ask(r)^ask(l-1);
30         l=r+1;
31     }
32     printf("%lld",ans);
33     return 0;
34 }

异或约数和

　　C.小朋友的笑话：http://www.51nod.com/Challenge/Problem.html#!#problemId=2014

　　每个人的状态可以认为只与最后听的那个笑话有关。

　　这里有一个极其神奇（也有可能只是我没见过）的做法：将每个笑话的出现过的区间...维护出来！因为一开始只想到用权值线段树维护区间，但是觉得复杂度不对就弃疗了，其实换成平衡树复杂度就对了。为什么呢？觉得复杂度不对的主要原因就是觉得一种笑话的区间可能很多，如果多次全部访问就会很慢，但其实这个问题是不存在的。如果两个区间出现了重叠，那么我们就把它们删掉，合成一个新的区间再加进去。每次最多加入一个区间，却可能删掉多个，且每个区间被加入后最多被访问一次就被删了，所以复杂度极其科学。

　　因为Set用的很不熟练，代码几乎是照搬这份题解，就不贴了。

---shzr