B a Bit More Common

默认大家已经掌握A题算法。

和A题算法一样，枚举n个数最后一位为1的数量。设这个数量为i。

由于至少两个子序列不好维护，考虑用A题的答案减去只有一个子序列的情况。

如果后者成立，对于这i个数中任意一个数a，当且仅当剩下i-1个数至少有一位都是1（使得不存在两个子序列，一个是枚举的i个数，一个是剩下的i-1个数，使得&值=1），而且a的这一位等于0（否则如果i个数这一位都是1，则这一位会为答案做贡献，i个数的&值大于1）。我们称这一位是一个数的“特殊位”。

根据定义“任意一个数”，因此任意一个在i个数中间的数（末尾为1的数）都至少存在一个特殊位。

由于特殊位除了a之外对应其他数都是1，因此一个特殊位只能对应一个数。

想到大概思路：m-1位中选出i位分别匹配i个数（A(m,i)），然后剩下m-i-1为随便选择。但是如果剩下m-i-1位选择的也是特殊位，会在枚举该特殊位的时候算重。

因此在第一步枚举特殊位的时候，就应该包含所有特殊位（一个数可能对应多个特殊位）k位。剩下的m-k-1位不会包含这些特殊位。

先考虑剩下的m-k-1位。虽然有可能不止i个特殊位，但一个数对应的特殊位一致。因此i个数一定对顶i个不同的特殊位（注，位置可相同），用2^i-i-1即可（减去全1的非法情况）

再考虑特殊位的分配情况。

由于情况复杂，无法直接使用组合数表示，考虑dp。

因为一个数可以对应多个位，而一个位最多对应一个位。

也是一样考虑大概方向。dp[i][j]表示使用前i个位（这里是必须用），匹配前j个数。

1）匹配新的数 dp[i-1][j-1]

2）匹配原来j个数 j*dp[i-1][j]

仔细看会发现这么dp下去，数越靠前，第一次匹配的特殊位越靠前。如果每个数最靠前的特殊位单增，那么对于每一个方案，当且仅当对应dp中的一种计数。

因此对i个第一次匹配的特殊位做一次全排列即可。

具体实现时，处理dp，枚举末尾是1的数的个数和匹配特殊位的位数，用A的方法-dp·全排列·从m-1位中挑出匹配的位数的组合数·特殊位之外的方案数（倒序枚举匹配位数，枚举一次将乘量乘上2^i-i-1）

细节：m=1时需要特判

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll N=5e3+10;
ll dp[N][N],s[N],c[N][N],ac[N],P;
ll qp(ll a,ll b){
    ll s=1;
    while(b){
        if(b&1) s=(s*a)%P;
        a=(a*a)%P,b>>=1;
    }
    return s;
}
int main(){
    ll n,m,t=1,a=0; scanf("%lld%lld%lld",&n,&m,&P);
    for(ll i=0;i<=max(n,m);i++){
        c[i][0]=1;
        for(ll j=1;j<=i;j++){//j<m
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;}
    }
    ll b=1;  s[n+1]=1;
    for(ll i=n;i>=1;i--){
		for(ll j=1;j<m;j++) b=(b<<1)%P;
		s[i]=b;
	}
    dp[0][0]=1,ac[1]=1;//no
    for(ll i=2;i<m;i++) ac[i]=ac[i-1]*i%P;
    for(ll i=1;i<=n;i++){
        for(ll j=i;j<m;j++){
        dp[i][j]=(dp[i-1][j-1]+i*dp[i][j-1])%P;}//no i*
        t=(t<<1)%P,a=(a+c[n][i]*qp(t-1,m-1)%P*s[i+1]%P);
        ll b=0,tt=(t+P-i-1)%P,t2=1;//no tt
        if(m==1) b=(i==1);//no
        for(ll j=m-1;j>=i;j--){
        b=(b+dp[i][j]*c[m-1][j]%P*ac[i]%P*t2%P)%P,t2=(t2*tt)%P;}	
        b=b*c[n][i]%P*s[i+1]%P;//no s
        a=(a+P-b)%P;
    }
    printf("%lld",a);
    return 0;
}