(联考)noip97
可恶，cnblogs不能往前修改发布时间了，鸽子的本质暴露了...
T1
比较简单的题。
但考场上没有想到退背包。
我的做法开了个桶，记录的是只考虑当前枚举到的 \(m\) 中的前 \(i\) 个，能拼出来的所有数的方案数。
直接枚举每一个数，然后组合数瞎jb写就行。
复杂度 \(O(nm)\)
Code
#include
#include
#include
#define re register
const int N = 53;
const int MAX = 1e4+3;
#define long long long
#define scanf oma=scanf
#define pack emplace_back
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
templateinline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int n,m;
long b[MAX];
long c[53][53];
long seq[MAX],delta[MAX];
#define debug(s) printf("%s\n",s)
}using namespace some;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
//system("./data");
debug("look here! if you want submit,please closed this");
freopen("node.in","r",stdin); //freopen("my.out","w",stdout);
#endif
freopen("subset.in","r",stdin); freopen("subset.out","w",stdout);
cin >> n >> m;
for(re int i=0; i<=m; i++)
{ cin >> b[i]; }
c[0][0] = 1;
for(re int i=1; i<=n; i++)
{
c[i][0] = 1;
for(re int j=1; j<=i; j++)
{ c[i][j] = c[i-1][j-1]+c[i-1][j]; }
}
//debug("shit");
for(re int i=1; i<=m; i++)
{
if(b[i]>0)
{
for(re int j=1; j<=b[i]; j++)
{
for(re int k=1; k<=m; k++)
{
if(!seq[k])
{ continue ; }
b[k+i*j] -= c[b[i]][j]*seq[k];
delta[k+i*j] += c[b[i]][j]*seq[k];
}
}
for(re int k=1; k<=m; k++)
{ seq[k] += delta[k],delta[k] = 0; }
seq[i] += b[i];
for(re int j=2; j<=b[i]; j++)
{ b[j*i] -= c[b[i]][j],seq[i*j] += c[b[i]][j]; }
for(re int j=1; j<=b[i]; j++) { printf("%d ",i); }
}
}
return 0;
};
};
signed main()
{ return OMA::main(); }
T2
也挺简单，考场上想了Trie树，但是不会了，于是写了个暴力走人。
但写丑了，只有20pts...
对于题目中的式子大小关系判定，只跟 \(a_{i},a_{k}\) 从高到低第一个不相同的二进制位 \(p\) 有关。
于是可以分情况讨论一下：
-
\(a_{i,p}=0,a_{k,p}=1\) 时， \(a_{j,p}=0\) 。
-
\(a_{i,p}=1,a_{k,p}=0\) 时， \(a_{j,p}=1\) 。
也就是说 \(a_{i,p}=a_{j,p}\neq a_{k,p}\) 。
把 \(a_{k}\) 依次加入Trie树中，对于 \(a_{k,p}\) ， \(a_{i,p}\) 即为 \(a_{k,p}\) 的兄弟。
那么 \(j\) 的选择有两种情况：
-
在 \(i\) 的子树中，那么 \(i,j\) 都可以在这个子树中任选，方案数即为 \(\frac{size(size-1)}{2}\) 。
-
不在 \(i\) 的子树中，那么只需要知道当前子树外，到当前位置二进制位相同的有多少个，开个桶在插入过程中就可以求出，然而对于 \(j
Code
#include
#include
#include
#include
using std::vector;
#define re register
const int log = 30;
const int MAX = 5e5+3;
#define long long long
#define scanf oma=scanf
#define push emplace_back
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
templateinline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int n;
long ans;
#define debug(s) printf("%s\n",s)
}using namespace some;
namespace Data_Structures
{
struct Trie
{
int tot;
int cnt[log][2];
struct data
{
int next[2];
long size,delta;
}trie[MAX*log];
#define size(p) trie[p].size
#define delta(p) trie[p].delta
#define son(p,i) trie[p].next[i]
void insert(int x)
{
int u = 0;
for(re int i=log-1,p1,p2; ~i; i--)
{
p1 = (x>>i)&1,p2 = p1^1;
if(!son(u,p1))
{ son(u,p1) = ++tot; }
ans += size(son(u,p2))*(size(son(u,p2))-1)/2+size(son(u,p2))*(cnt[i][p2]-size(son(u,p2)))-delta(son(u,p2));
u = son(u,p1),delta(u) += cnt[i][p1]-size(u),size(u)++,cnt[i][p1]++;
}
}
}Tree;
}using namespace Data_Structures;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
debug("look here! if you want submit,please closed this");
freopen("node.in","r",stdin); //freopen("my.out","w",stdout);
#endif
freopen("xor.in","r",stdin); freopen("xor.out","w",stdout);
cin >> n;
for(re int i=1,a; i<=n; i++)
{ Tree.insert((cin >> a,a)); }
printf("%lld\n",ans);
return 0;
};
};
signed main()
{ return OMA::main(); }
T3
暴力有50pts..
正解是推式子，异或推式子也是头一次见。
分奇偶单独考虑贡献。
对于 \(n=2k+1\) ，即 \(n\) 为奇数，有：
\[\begin{aligned} f(n) &=\sum_{i=1}^{n-1} i \oplus(n-i) \\ &=2 \sum_{i=1}^{k} 2 i \oplus(2 k-2 i+1) \\ &=2 \sum_{i=1}^{k} 2 i \oplus(2 k-2 i) +2k\\ &=4 \sum_{i=1}^{k} i \oplus(k-i)+2 k \\ &=4 f(k)+6 k \end{aligned} \]对于第二步到第三步， \(2i,2k-2i\) 都为偶数，二进制下最后一位为0，+1异或后，肯定有1的贡献，于是可以都提出来，于是就在后面加个 \(2k\) 就到了第三步。
第三步到第四步，同上，都为偶数，左移后异或，跟异或后左移是一样的，于是可以把 \(2\) 提出来，就得到了第四步的式子。
当 \(i=k\) 时， \(i\oplus(k-i)=k\oplus0=k\) ，于是可以提出来，就是个 \(4k\) ，这时 \(\sum\) 的枚举上界就变成了 \(k-1\) ，于是这个 \(\sum\) 就变成了 \(f(k)\) ，于是得到了最后的式子。
对于 \(n=2k\) ，即 \(n\) 为偶数，有：
\[\begin{aligned} f(n) &=\sum_{i=1}^{n-1} i \oplus(n-i) \\ &=\sum_{i=1}^{k-1} 2 i \oplus(2 k-2 i)+\sum_{i=1}^{k}(2 i-1) \oplus(2 k-2 i+1) \end{aligned} \]前半部分是偶数的贡献，后半部分是奇数的贡献。
偶数的可以用上面的方法变成 \(2f(k)\) ，即：
\[\begin{aligned} \sum_{i=1}^{k-1} 2 i \oplus(2 k-2 i) &=2 \sum_{i=1}^{k-1} i \oplus(k-i) \\ &=2 f(k) \end{aligned} \]对于奇数的，不好搞，可以把它往偶数身上靠，用上边的方法化简，即：
\[\begin{aligned} \sum_{i=1}^{k}(2 i-1) \oplus(2 k-2 i+1) &=\sum_{i=0}^{k-1}(2 i+1) \oplus(2 k-2 i-1) \\ &=\sum_{i=0}^{k-1}(2 i+1) \oplus[2(k-1)-2 i+1] \\ &=\sum_{i=0}^{k-1}2 i \oplus[2(k-1)-2 i] \\ &=2\left[\sum_{i=0}^{k-1} i \oplus(k-1-i)\right] \\ &=4 k-4+2 \sum_{i=1}^{k-2} i \oplus(k-1-i) \\ &=2 f(k-1)+4 k-4 \end{aligned} \]第二步到第三步中的1没了是因为， \(2i,2(k-1)-2i\) 都为偶数，最后一位都为0，加1后最后一位都变成了1，异或后相当于没加，于是直接删掉即可。
第三步到第四步同上，第四步到第五步， \(i=0,k-1\) 时异或的其中一项为0，另一项为 \(k-1\) 于是可以直接提出来，这样后边的 \(\sum\) 就变成了 \(f(k-1)\) 。
然后就有了 \(n=2k\) 时最后的式子：
\[f(n)=4k-4+2f(k)+2f(k-1) \]于是直接记忆化搜索+sb高精度即可解决。
T4
原题hdu6403
也是之前加的题，但是没写过...
每一张牌，将正面向反面连边，那么问题就转换为反转一些边的方向，使得每个点的出度不超过1。
连完边后的图肯定是个树或者基环树，树的直接换根dp，基环树枚举环的方向即可。