P3773 [CTSC2017]吉夫特 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 还没有评论
作者: rushcheyo 更新时间: 2017-07-21 20:17  在Ta的博客查看    5  

众所周知, $C_n^m$ 是奇数时,有 (n&m)==m。所以我们设 f[i] 表示以 i 这个数字结尾的方案数(包括长度为1的),记下每个数的位置,然后再穷举每个数二进制1的子集(这样就保证前面的条件而且肯定比其小),如果这个子集数是存在的而且在当前数的后面就 f[j]+=f[a[i]],最后减掉所有长度为1的就做完了。

#include<cstdio>
const int mo=1000000007;
int n,i,j,a[211986],p[233334],f[233334];
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d",a+i);
        p[a[i]]=i;
        f[a[i]]=1;
    }
    for(i=1;i<=n;++i)
        for(j=(a[i]-1)&a[i];j;j=(j-1)&a[i])
            if(p[j]>i)
                f[j]=(f[j]+f[a[i]])%mo;
    for(i=0,j=1;j<=n;++j)
        i=(i+f[a[j]]-1)%mo;
    printf("%d\n",i);
    return 0;
}

评论

  • 还没有评论
作者: litble 更新时间: 2018-05-02 21:58  在Ta的博客查看    2  

点击就送屠龙刀 个人博客安利

解题思路:B君出的题,不可做

如何判断组合数是否是奇数?

首先, $C_n^k=\frac{n!}{k!(n-k)!}$ ,假设 $n!$ 的2因子数为 $a$ , $k!$ 的2因子数是 $b$ , $(n-k)!$ 的2因子数为 $c$ ,那么如果 $C_n^k$ 是奇数,则 $a=b+c$

怎么求出 $x!$ 的2因子个数呢?首先我们可以将x除以2,相当于一个提取公因数的过程,而那些不能被2整除的项就会被丢掉,于是剩下来的是 $2*(\frac{x}{2}!)$ ,一直这样处理下去,得到答案为

$$f(x)=\sum_{i=1}^{ \infty} \frac{x}{2^i}$$

我们设 $g(x)=x$ ,那么 $g(x)=g(\frac{x}{2})+\frac{x}{2}+(x\bmod 2)=\sum_{i=1}^{ \infty} \frac{x}{2^i}+$ (x在二进制下1的个数) 所以 $x!$ 的2因子个数就是(x-x在二进制下1的个数)

那么 $C_n^k$ 是奇数的条件即为:n在二进制下1的个数=k在二进制下1的个数+(n-k)在二进制下1的个数。

假设二进制下,n拥有的某一个1,k并没有,那么:

n: ...0...

k: ...1...

n-k: ...11....

会发现k和(n-k)二进制下1的个数和一定会大于n,所以必须k所有的1 n都拥有才能符合条件,综上, $C_n^k$ 是奇数的条件为:(n&k)=k

那么后面的事情就简单了,设 $f_i$ 表示以 $a_i$ 开头的子序列个数,用桶存每一个 $a_i$ 出现的位置 $i$ 。计算 $f_i$ 时,考虑下一个放什么,也就是枚举 $a_i$ 的子集,判断这个数是否在 $i$ 后面,然后统计方案即可。

复杂度是 $O(3^{\log maxa})$ 的

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=240000,mod=1000000007;
int a[N],T[N],f[N];
int n,ans;
int qm(int x) {return x>=mod?x-mod:x;}
int main()
{
    n=read();
    for(RI i=1;i<=n;++i) a[i]=read(),T[a[i]]=i;
    for(RI i=n;i>=1;--i) {
        f[i]=1;
        for(RI j=a[i]&(a[i]-1);j;j=a[i]&(j-1))
            if(T[j]>i) f[i]=qm(f[i]+f[T[j]]);
        ans=qm(ans+f[i]);
    }
    ans=(ans-n+mod)%mod;
    printf("%d\n",ans);
    return 0;
}

评论

  • 还没有评论
作者: 金爷爷哈哈 更新时间: 2017-12-23 18:34  在Ta的博客查看    1  

楼下说的这个结论估计很多像我一样的蒟蒻会懵掉吧。。。

那么为了帮助大家理解我就来证明一下这个结论吧

我们假设(n&m)==m,那么先假设这个结论是对的,看能不能找到反例推翻它。

1.当m的二进制最右位是1时:

这时n的二进制最右位肯定是1,所以((n-1)&(m-1))==m-1,可以递归证明C(n-1,m-1)是奇数;

又因为((n-1)&m)!=m,因为n-1的二进制最右位没有1了,所以可以递归证明 C(n-1,m)是偶数,

进而可以证明 C(n,m)是奇数。

2.m二进制最右位不是1时:

这样(m-1)的二进制最右端显然会有一排1(长度>=1)。

(1):如果此时n的二进制最右位的1和m是相同的位置,那么依然满足((n-1)&(m-1))==m-1。

有因为n的二进制最右位的1在n减去1之后被消去了,所以此时((n-1)&m)!=m,仍可证明C(n,m)是奇数。

(2):如果n二进制最右位的1在m二进制最右位1的右边,那么减去1后,m右端连续的变成1的序列会长于n,比如m=10100(2),n=10110(2),那么m-1=10011,n-1=10101,2^1这位m-1是1而n-1不是1,所以此时((n-1)&(m-1))!=m-1;又因为n减去1之后并不影响最右端1左边那些1,所以可以证明((n-1)&m)==m,这样又证明了C(n,m)是奇数。

代码楼上的就比较好了,我就不贴我的丑代码了hhh