随心情补题，简单的不详细写了。
E - ABBA
对于这个题，我没有做出来是因为没看出来，对于一个串来讲，拆成AB和BA时，前n个A一定属于AB，同理B也一样，所以你可以dp这个串的选择方式了，因为构成了无后效性了，后面的选择只和前面A，B的数量有关系，是和顺序没有关系的。考虑添加A的情况：比n少的时候可以直接加A，比n大的时候，只要前面的B比较多，能和多余的A消掉就可以了，这道题不会有点尴尬啊，好多人都过了。
#include<iostream> #include<cstring> #include <string> #include<algorithm> #include<map> #include<set> #include<stack> #include<queue> #include <math.h> #include<vector> using namespace std; const int maxn=4e3+10; const int mod=1e9+7; typedef long long ll; ll dp[maxn][maxn]; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=0;i<=n+m;i++) for(int j=0;j<=m+n;j++) dp[i][j]=0; dp[0][0]=1; for(int i=0;i<=n+m;i++) for(int j=0;j<=m+n;j++) { if(i<n||(j>i-n)) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod; if(j<m||(i>j-m)) dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod; } cout<<dp[n+m][m+n]<<endl; } }
H-XOR
写这个题的时候我还不会线性基orz，看了看大佬们的博客，把线性基的基本性质补了一下，这个题很明显是在求贡献，只要知道一个元素a[i]被选中时，其他元素有多少种选法即可，题意变为，除了a[i]，用其他的元素的异或和如何构造出a[i]的数量，用数组本身构造一个线性基R，如果a[i]不是这个线性基中的关键元素（插入进去的时候有效），那么除了线性基的num个关键元素和a[i]外，其他的n-num-1个元素可以随便选择，得出的结果一定可以被线性基唯一的组合出来，这个数字的贡献为2^(n-num-1)。如果这个数字是关键元素，那么你考虑移除这个元素的线性基能不能组合出来它，如果不能，也就是说如果选了这个数，就不可能导致异或和为0，这个数没有贡献。如果移除这个数，剩余的线性基仍然可以表示它，那么情况变的和上一种情况一摸一样，仅仅是线性基的关键元素换了而已，但是线性基依然是唯一的那个线性基。对于后半段计算，因为关键元素特别少（最多64），保存一下（n-num）个非关键元素的线性基，然后去掉a[i]的线性基就是不选a[i]，把剩余的关键元素都插入线性基即可（利用了相同部分避免重复计算）。
这道题感觉还是不太好想线性基这个方法吧，感觉有点证明的过程有点离奇的感觉，没有什么可以顺着思路想下去的方式，的确很难。
#include<iostream> #include<fstream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<stack> #include<queue> #include <math.h> #include<vector> using namespace std; const int maxn=1e5+10; const int mod=1e9+7; typedef long long ll; typedef pair<ll, ll> P; ll a[maxn]; ll d[100],d2[100],t[100]; bool add(ll *dd,ll x) { for(int i=63;i>=0;i--) { if(x&(1ll<<i)) { if(dd[i]==0) { dd[i]=x; return 1; break; } else x^=dd[i]; } } return 0; } int used[maxn]; int main() { int n,num=0; while(~scanf("%d",&n)){ num=0; for(int i=0;i<=n;i++) used[i]=0; for(int i=0;i<64;i++) t[i]=d[i]=d2[i]=0; for(int i=0;i<n;i++){ scanf("%lld",&a[i]); } vector<ll> ji; for(int i=0;i<n;i++) { if(add(d,a[i])) { used[i]=1; ji.push_back(a[i]); num++; } else add(d2, a[i]); } for(int i=0;i<=63;i++) t[i]=d2[i]; ll ans=0; ll a2=1; for(int i=0;i<n-num-1;i++) a2=a2*2%mod; ans+=a2*(n-num)%mod; for(int i=0;i<ji.size();i++) { for(int j=0;j<=63;j++) d2[j]=t[j]; for(int j=0;j<ji.size();j++) if(j!=i) add(d2, ji[j]); if(add(d2, ji[i])==0) { ans=(ans+a2)%mod; } } printf("%lld ",ans); } }