昨天学姐又说Day2难度是Day1两倍，反正我都无所畏惧了……

 

T1 forging

Day2果然毒瘤啊，T1就出一道期望dp，然后我期望基本忘得差不多了……

不过这道题其实不难。先考虑这个问题：抛一枚硬币，如果为反面就接着抛，求抛到正面的概率。设抛到正面的期望为x，首先要抛一次，然后有1/2的概率抛到反面，1/2的概率抛到正面，根据本题期望的定义，期望=概率 * 次数，那么就有 x = 1 + 1/2 * x + 1/2 * 0，即x  =1/2 * x + 1，得x = 2。还有另一种更好理解的方法：x = 1/2 + 1/4 * 2 + 1/8 * 3 + 1/16 * 4 + ……+ 1/2ⁿ * n。这个不难解，2 * x - x = 1 + 1/2 + 1/4 + 1/8 + …… + 1/2ⁿ,根据等比数列求和公式可知1/2 + 1/4 +1/8 + …… + 1/2ⁿ = 1,于是x = 2.

那么回到此题：令 k 表示锻造成功的概率，则k = min(c_i-1, b_i-2) / c_i-1.于是f_i + f_i-1 = k * f_i+1 + (k - 1) * f_i-1.整理一下，然后退一位得f_i = 1/k * f_i-1 + f_i-2。

用线性求逆元预处理c_i，然后递推求解。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<cctype>
 8 #include<vector>
 9 #include<stack>
10 #include<queue>
11 using namespace std;
12 #define enter puts("") 
13 #define space putchar(' ')
14 #define Mem(a) memset(a, 0, sizeof(a))
15 #define rg register
16 typedef long long ll;
17 typedef double db;
18 const int INF = 0x3f3f3f3f;
19 const db eps = 1e-8;
20 const int mod = 998244353;
21 const int maxn = 1e7 + 5;
22 inline ll read()
23 {
24     ll ans = 0;
25     char ch = getchar(), last = ' ';
26     while(!isdigit(ch)) {last = ch; ch = getchar();}
27     while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
28     if(last == '-') ans = -ans;
29     return ans;
30 }
31 inline void write(ll x)
32 {
33     if(x < 0) x = -x, putchar('-');
34     if(x >= 10) write(x / 10);
35     putchar(x % 10 + '0');
36 }
37 
38 int n, a;
39 int b[maxn], c[maxn], inv[maxn];
40 int dp[maxn];
41 
42 int main()
43 {
44     freopen("forging.in", "r", stdin);
45     freopen("forging.out", "w", stdout);
46     n = read(); dp[0] = read();
47     
48     int bx = read(), by = read(), cx = read(), cy = read(), p = read();
49     b[0]=by+1;c[0]=cy+1;
50     for(rg int i=1;i<n;i++)
51     {
52         b[i]=((long long)b[i-1]*bx+by)%p+1;
53         c[i]=((long long)c[i-1]*cx+cy)%p+1;
54     }
55     
56     inv[1] = 1;
57     for(rg int i = 2; i < maxn; ++i) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
58     dp[1] = ((ll)c[0] * inv[min(c[0], b[0])] % mod + 1) * dp[0] % mod;        //f[0]最好单独写一下 
59     for(rg int i = 2; i <= n; ++i)
60         dp[i] = ((ll)c[i - 1] * inv[min(c[i - 1], b[i - 2])] % mod * dp[i - 1] + dp[i - 2]) % mod;
61     write(dp[n]); enter;
62     return 0;
63 }

View Code

 

T2 division

这题尽管学姐说就是CRT板子，然而我不得不说是真心不会，讲完后还是不太懂……溜了……

 

T3 money

嗯……维护动态树上链的最小值，知道干啥，然后就是不会写，于是只能暴力水一发。

方法1：LCT……呵呵，等考完NOIP再说吧

方法2：兔哥自创妙法：虽然听懂了，然而就是不会写。首先我们想，如果树是静态的，那么自然可以用树剖（考试的时候我就想这么做，然而40分钟我觉得敲不完）或倍增解决。那么动态的怎么办：启发式合并。就是两棵树，然后把结点少的树往大树合并。这样的话，这些树必须改成无向的，要不然每一次合并还要想办法再找根节点或是干脆无法合并。既然无向的，那么自然要开一个数组记录每一链的方向，dir[i][j] = 1代表结点 i 像上跳2j步这个区间的这条链都是借别人钱的，2代表都是被借钱的，3代表这两种情况都有。因此合并的时候只要或起来就行了（很方便）。为此，还要有一个数组记录往上跳2j步是哪一个结点，因为合并的时候祖先会改变。当然还有最重要的记录最小值以及维护结点深度的数组了。

复杂度：启发式合并最坏复杂度为O(nlogn)，加上查询O(mlogn)，总时间复杂度O(nlogn + mlogn)。

思路就是这样，然而就是不会写……

方法3：是一个特别强的验题人想出来的，他叫wys。方法2我都不会，更别说这个了。什么用vector储存同一深度的结点，然后用链表串起来……弃疗了。