在此先感谢一下hdu免费出的个人赛。官方说是铜牌题。然而蒟蒻赛场上只会一道，还被杭电的机子卡常，赛时连交15发，靠着评测机的波动才通过。

赛后除了最后一题都补了，在这里记录一下。

由于官方题解已经把做法都写好了，我就单纯随便写点我以为的细节。

强连通计数

大致思路

题解说题目是一个内向基环树森林，对于这种图形，强连通分量只有一个点和一个环两种情况。

那么根据容斥定理易得：
强连通分量数=点数+环数-环上的点数

那么显然$E(强连通分量数)=E(点数)+E(环数)-E(环上的点数)$

所以我们分开算出每个部分的期望后即可算出答案。

由于题目给的是点不在的概率$p$

所以我们要计算出点在的概率即为$1-p$（我当时在想是不是要算$mod-p$，后来仔细想了想）

我对于除法取模的理解是这样的
$$\frac{a}{b}\%mod=a \times b^{mod-2}\%mod=x$$
$$(1-\frac{a}{b})\%mod=\frac{b-a}{b}\%mod=(b-a)\times b^{mod-2}=b^{mod-1}-a\times b^{mod-2} $$
由于费马小定理我们知道$b^{mod-1}\%mod=1$
所以原式取模后也就变成
$$ (1-a\times b^{mod-2})\%mod $$
注意减法如何取模。

（也许上面在大家看来是显然的，但确实是困扰住了本蒟蒻许久。Orz）

code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+10;
const int mod=1e9+7;

int n,a[N];
int p[N];
int d[N];
int ru[N];

int st,ed;

bool v[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],ru[a[i]]++;
    for(int i=1;i<=n;i++) cin>>p[i];
    int ans=0;
    for(int i=1;i<=n;i++){
        int y=(1-p[i]+mod)%mod;
        p[i]=y;
        ans+=p[i];
        ans%=mod;
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!ru[i]){
            q.push(i);
        }
    }
    while(q.size()){
        int x=q.front();
        q.pop();
        ru[a[x]]--;
        if(!ru[a[x]]) q.push(a[x]);
    }
    vector<int> ve;
    for(int i=1;i<=n;i++){
        if(ru[i]==1) ve.push_back(i);
    }   
    int res=1;
    vector<vector<int> > vec;
    for(auto x:ve){
        if(!v[x]){
            vector<int> vecc;
            int y=x;
            vecc.push_back(y);
            v[y]=1;
            while(a[y]!=x){
                y=a[y];
                v[y]=1;
                vecc.push_back(y);
            }
            vec.push_back(vecc);
        }
    }
    for(auto x:vec){
        int ress=1;
        for(auto y:x){
            ress*=p[y];
            ress%=mod;
        }
        ans-=ress*x.size();
        ans%=mod;
        ans+=mod;
        ans%=mod;
        ans+=ress;
        ans%=mod;
    }
    ans%=mod;
    cout<<ans<<'\n';
}

子集整除

大致思路

这题呢题解的思路我没怎么看，因为我认为我的思路应该也是大致对的，就是被杭电的机子卡了一下。（当然，也有可能是我错了）

如果题目没有整除$k$的性质我们会怎么做，显然的，在所有的非空子序列中的总和，每个数被引用的次数都是相同的，我们可以很简单的计算出最后的答案。

那么加上了整除$k$之后有哪些影响呢？我们注意到，由于一些不可以被k整除的数加起来与直接除了再加的答案会是不一样的。

那么我们对于这种情况要怎么处理呢？显然，我们需要多记录一个状态目前子序列的权值和对$k$取模后的值。这样子，这题目就差不多结束了。

总的来说，用动态规划，设$dp_{i,j}$表示前$i$个数的子序列中对$k$取模为$j$的权值和，再开一个$cnt_{i,j}$记录前$i$个数的子序列中对$k$取模为$j$的子序列个数和。然后转移显然。

时间复杂度$O(NK)$

code

#pragma GCC O(2)
#pragma GCC O(3)
#include <bits/stdc++.h>

using namespace std;

const int N=5e3+10;

int n,k,p;

int a[N];

int dp[2][N];
int cnt[2][N];
bool v[2][N];

void solve(){
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        int xx=(i-1)&1;
        int yy=(i)&1;
        for(int j=0;j<k;j++){
            if(v[xx][j]){
                v[yy][j]=1;
                dp[yy][j]=(dp[yy][j]+dp[xx][j])%p;
                cnt[yy][j]=(cnt[yy][j]+cnt[xx][j])%p;
                int res=j+a[i];
                int x=res/k;
                int y=res%k;
                v[yy][y]=1;
                dp[yy][y]=(dp[yy][y]+dp[xx][j]+((long long)(x)*cnt[xx][j]%p))%p;
                cnt[yy][y]=(cnt[yy][y]+cnt[xx][j])%p;
            }
        }
        int x=a[i]/k;
        int y=a[i]%k;
        dp[yy][y]=(dp[yy][y]+x)%p;
        cnt[yy][y]+=1;
        cnt[yy][y]%=p;
        v[yy][y]=1;
        for(int j=0;j<k;j++){
            v[xx][j]=0;
            dp[xx][j]=0;
            cnt[xx][j]=0;
        }
    }
    int ans=0;
    for(int i=0;i<k;i++){
        int yy=n&1;
        if(v[yy][i]){
            ans+=dp[yy][i];
            ans%=p;
        }
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
    return 0;
}

最大平均区间

大致思路

这道题我赛场上并没有想出来，那我就照着题解的思路讲一讲。

注意到题目询问的事满足某种条件的答案最大。那么根据最大这一关键词，我们就可以考虑二分答案了。

这题我觉得题解讲得够清楚了。我直接搬题解里的图上来。

---

这题的话可能关键就是我们想到二分答案这个思路。

以及求某个区间和可以用前缀和优化，自然而然想到前缀和的比较。

但是对于前缀和的比较，如果里面带有其他的变量就不好实现，

因此我们需要考虑一种方法来使得式子中只剩下纯粹的前缀和的大小比较。
在这之后就可以用Trie树快速求解了。

---

code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+10;
const int M=4e6;
int n,k;
int a[N],s[N];
int p[N];
int a1[N];

int nex[N*30][2],root,tot;
int maxn[N*30];

int newcode(){return tot++;}

void init(){
    for(int i=0;i<=tot;i++){
        nex[i][0]=nex[i][1]=0;
        maxn[i]=-1e18;
    }
    tot=1;
    root=newcode();
}

void insert(int x,int v){
    int p=root;
    for(int i=30;~i;i--){
        int t=(x>>i)&1;
        if(!nex[p][t]) nex[p][t]=newcode();
        p=nex[p][t];
        maxn[p]=max(maxn[p],v);
    }

}

bool query(int x,int k,int val){
    int p=root;
    int res=0;
    for(int i=30;~i;i--){
        int t=(x>>i)&1;
        int res=(k>>i)&1;
        if(res==1){
            if(nex[p][t^1]){
                p=nex[p][t^1];
            }
            else return 0;
        }
        else{
            if(nex[p][t^1]){
                if(maxn[nex[p][t^1]]>=val) return 1;
            }
            if(nex[p][t]){
                p=nex[p][t];
            }
        }
    }
    return (maxn[p]>=val);
}

bool check(int x){
    init();
    for(int i=1;i<=n;i++){
        a1[i]=a[i]-x;
        s[i]=a1[i]+s[i-1];
    }
    for(int i=n;i>=1;i--){
        insert(p[i],s[i]);
        if(query(p[i],k,s[i-1])) return 1;
    }
    return 0;
}

void solve(){
    cin>>n>>k;
    for(int i=0;i<=n*30;i++) maxn[i]=-1e18;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>p[i];
    int l=-1,r=987654321;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

合法数对

大致思路

这题可以用数位dp做，但是我是一点都不会了。

找了篇纯递推的题解，我来讲讲它的思路。

首先呢，题目要求 $x \bigoplus y=x|y$即$x\&y=0$。

那么显然存在且仅存在三种合法情况

$(0,0)(1,0)(0,1)$

假设$dp_{i}$表示考虑到第$i$位时候的答案

对于一个位置，如果这个位置是$1$那么显然，三种情况都可以取。

即$dp_{i}=dp_{i-1} \times 3$

那么如果这个位置上的数是0呢？

与数位$dp$类似的，只有当$x$和$y$的数其中一个达到上限后这个位置能填的才只有$(0,0)$。为了方便讨论，我们先对于$x$进行讨论（y同理）。

---

假设这个位置前全是$1$，而这个位置是$0$，且$x$达到上限。

那么显然$x$在这个位置上也只能填$0$，与原来少了一种$(1,0)$的情况。

由于x达到上限的情况只有$1$种，所以不成立的情况也只有1种。

换成$y$的时候同理，所以不成立的情况加起来只有$2$种，也就是$2^{1}$。

在这里我们算的时候用原本该有的个数减去减少的个数即为答案的个数。

---

那么如果在这个$0$之前还有其他的$0$呢？显然我们还是先针对$x$进行讨论。

也是$x$要达到上限时会有限制，那么$x$达到上限的情况有几种呢？

我们随手模拟一下即可发现 对于前面的$0$ ，由于$x$要到达上限，所以$x$的位置只能是$0$，

但是$y$的位置可以是$0$或者$1$（由于$x$达到上限了，所以$y$一定不是上限，取$1$是没关系的）

对于前有多少个$0$，既有多少种类似情况。

---

即设到该位置一共有$cnt$个$0$，即有$2^{cnt-1}$种情况不成立，换成讨论y同理。所以不成立的综次数即为$2^{cnt}$

大致的转移如下（太严谨的我写不来，意思一下）

设$N$的第$i$位为$N_{i}$
$$dp_i = \begin{cases} dp_{i-1} \times 3 & \text{if } N_i = 1 \\ dp_{i-1} \times 3 – 2^{cnt} & \text{if } N_i = 0 \end{cases}$$

code

#include <bits/stdc++.h>

using namespace std;

const int mod=998244353;

char c;

long long ans=0;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ans=1;
    long long res=1;
    while(cin>>c){
        ans*=3;
        if(c=='0'){
            res<<=1;
            res%=mod;
            ans=ans-res+mod;
        }
        ans%=mod;
    }
    cout<<ans<<'\n';
}

参考

2024杭电ACM-个人PK赛(1) 1004合法数对 – HDU7415

异或

大致思路

这题我感觉也是挺有意思的，用到的东西比较多。

首先我们观察到题目中$b_{i,j}=b_{i-1,j}\bigoplus b_{i-1,j+1}$.

可能长得和常见的有点不一样，但是如果我们翻转一下，如果它是这种形式$b_{i,j}=b_{i-1,j-1}+b_{i,j}$呢？

是不是恍然大悟了，没错，这就是杨辉三角。

---

那么我们就可以在下面使用杨辉三角特有的公式，接下来就是题解里的东西了。

我几乎没什么新的东西，就直接贴图了。

---

题解开头的贡献系数即为杨辉三角的计算公式。

由于异或的特殊性，所以我们只考虑奇偶性。

对于题解中一般形式怎么理解呢？我们可以手动模拟一下。

$t=x \% 512$ 那么$\binom {x-t}{t}$中的$x-t$的末$10$位一定都是$0$，所以可以减少枚举子集时的个数。

最后还有一点，就是除了子集以外，还有空集也是答案的一部分。（我不知道空集算不算子集）

差不多就这样。

code

#include <bits/stdc++.h>

using namespace std;

const int N=3e5+10;

int a[N];
int n,q;
int b[520][N];

void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[0][i]=a[i];
    }
    for(int i=1;i<512;i++){
        for(int j=0;i+j<n;j++){
            b[i][j]=b[i-1][j]^b[i-1][j+1];
        }
    }
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        if(x<512){
            cout<<b[x][y]<<'\n';
        }
        else{
            int xx=x%512;
            int ans=b[xx][y];
            int xxx=x-xx;
            for(int yy=xxx;yy;yy=(yy-1)&xxx){
                if(xx+y+yy<n) ans^=b[xx][y+yy];
            }
            cout<<ans<<'\n';
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
    return 0;
}

总结

还得练。