P3773 [CTSC2017]吉夫特 题解


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

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

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

评论

  • ZJQ90202
    求救dalao ,为什么 C(n,m)要满足是奇数的条件? 就这里不懂...
  • ZJQ90202
    emmmmm 题目里那个式子不是很懂,那个式子化简一下最后就是组合数了是么?
  • ZJQ90202
    emmmmm 原来括号里面上下有两个数字就是组合数的意思是伐?
作者: rushcheyo 更新时间: 2017-07-21 20:17  在Ta的博客查看    6  

众所周知, $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

评论

  • 还没有评论
作者: KamijouIndex 更新时间: 2018-07-04 07:44  在Ta的博客查看    0  

广告

这里观赏体验更佳

思路

一句话题意:

给出一个长度为 n 的序列,求所有长度大于等于2的子序列个数,满足:对于子序列中任意两个相邻的数 a和 b (b 在 a 前面), $C_a^b mod 2=1$ ,答案对1e9+7取模

显然膜2余1是个非常特殊的性质,应当好好加以利用

和组合数取模有关的东西,有Lucas定理,因此我们来试着推一推

$C_n^m\;mod\;2=C_{n\;mod\;2}^{m\;mod\;2}\ast C_{n/2}^{m/2}$

这个玩意的意义,显然就是把n和m转成二进制,那么只要没有某一位上n是0m是1(此时 $C_0^1$ 无意义,视作0)就OK了

那么我们就把问题转化成了一个可以DP的问题

设dp[i]表示序列 $[i,n]$ 中可能的种类数,那么可以通过枚举 $a[i]$ 和哪些数满足上属性质

这个枚举过程可以巧妙地利用 $j=(j+1)|a[i]$ 来完成,相当于是把 $a[i]$ 的0一个个变成1

总效率不太会算,但是O(能过)还是有的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
inline ll read(){
    ll re=0,flag=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re*flag;
}
ll MOD=1e9+7; 
ll n,a[300010],dp[300010],lim=233333;
ll pl(ll a,ll b){
    return (a+b>MOD)?a+b-MOD:a+b;
}
int main(){
    n=read();ll i,j,ans=0;
    for(i=1;i<=n;i++) a[i]=read();
    for(i=n;i>=1;i--){
        for(j=a[i];j>=1;j=(a[i]&(j-1))){//注意枚举方法
            dp[a[i]]=pl(dp[a[i]],dp[j]);
        }
        ans=pl(ans,dp[a[i]]);
        dp[a[i]]=pl(dp[a[i]],1);
    }
    printf("%I64d\n",ans); 
}

评论

  • 还没有评论
作者: GoAway 更新时间: 2018-06-30 21:30  在Ta的博客查看    0  

一道不难但是拖了很久的题,我这个傻逼活该要退役.

Click here to read the problem.

令 $N= log_2(max_{a_i})$ . 网上很多 $3^N$ 的做法,不具体说了,大概就是 $dp[x]$ 代表以 $x$ 结尾的方案数.

考虑分块,把数字二进制下分成前一段和后一段. 设 $f[u][v] = \sum_{v \in x}*dp[u*2^\frac{N}{2}+x]$ .即前一半为 $u$ ,后一半 $v$ 的超集的方案数之和.(超集就是子集的补集).

每加进一个数字,枚举前一半的超集,计算答案;再枚举后一半的子集,因为这个数字结尾的答案将影响后一半子集的 $f$ 值.

时间复杂度 $O(6^\frac{N}{2})$ .

#include <bits/stdc++.h>
#define LL long long
using namespace std ;
template <class T> void Read ( T &x, char c = getchar(), bool f = 0 ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) f |= c == '-' ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
    if (f) x = -x ;
}
const int maxn = 220000, Mod = 1000000007 ;
int n, m, S, f[520][520] ;
int main() {
    int i, x, u, v, val, ans = 0 ;
    Read(n) ;
    m = 1<<9, S = m-1 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(x) ;
        u = x/m, v = x%m ;
        val = 1 ;
        for ( x = u^S ; x ; x = (x-1)&(u^S) )
            if (f[x|u][v]) (val += f[x|u][v]) %= Mod ;
        (val += f[u][v]) %= Mod ;
        for ( x = v ; x ; x = (x-1)&v ) (f[u][x] += val) %= Mod ;
        (f[u][0] += val) %= Mod ;
    }
    for ( i = 0 ; i <= S ; i ++ )
        (ans += f[i][0]) %= Mod ;
    (ans += Mod-n) %= Mod ;
    cout << ans << endl ;
    return 0 ;
}