题意

自己去看

前言

我好菜啊。。感觉现在看到计数题就怂。。一点干的欲望都没有
然后这题是有部分分的，然后我部分分都没有拿到

题解

%beginend
我感觉我连问题模型都没有转化。。直接看着原题做，于是毫无头绪。。
转化了问题以后就好搞了
一种朴素的做法是枚举一个i，表示有多少位为0，然后枚举一个j，表示有多少位只有1个，可以得到，然后再枚举一个k表示这j个1存在于多少个数里面
$2^{2^{n-i-j}}*S(j,k)*(2^{n-i-j})^k*C(n,i+j)*C(i+j,i)$
然后这样是可以做到$n^3logn$的，可以拿到60分
然后我们发现，$n-i-j$出现了很多次，我们考虑一下能不能把这个提出来
于是我们可以直接枚举i表示有多少个不合法的
然后再枚举k，k和上面的定义一样，然后j的枚举放在最后面
$2^{2^{n-i}}*(2^{n-i})^k*C(i,k)*\sum{C(i,j)*S(j,k)}$
然后
$\sum{C(i,j)*S(j,k)}=S(i+1,k+1)$
然后就可以了
时间复杂度$O(n^2logn)$
CODE:

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const LL N=3005;
LL n,m;
LL JC[N],inv[N];
LL s[N][N];
LL pow (LL x,LL y,LL MOD)
{if (y==0) return 1;if (y==1) return x;LL lalal=pow(x,y>>1,MOD);lalal=lalal*lalal%MOD;if (y&1) lalal=lalal*x%MOD;return lalal;
}
LL C (LL x,LL y)
{if (x<y) return 0;return JC[x]*inv[y]%m*inv[x-y]%m;
}
int main()
{//printf("%lld\n",123456791LL*123456791LL);scanf("%lld%lld",&n,&m);JC[0]=1;for (LL u=1;u<=n;u++) JC[u]=JC[u-1]*u%m;inv[n]=pow(JC[n],m-2,m);for (LL u=n-1;u>=1;u--) inv[u]=inv[u+1]*(u+1)%m;inv[0]=1;s[0][0]=1;for (LL u=1;u<=n+1;u++)for (LL i=1;i<=u;i++)s[u][i]=(s[u-1][i-1]+s[u-1][i]*i%m)%m;LL ans=0;
//  printf("%lld\n",JC[n]);for (LL u=0;u<=n;u++)//有多少个不和法的 {LL w=0;for (LL i=0;i<=u;i++)   w=(w+pow(pow(2,n-u,m),i,m)*s[u+1][i+1]%m)%m;//  printf("%lld %lld\n",u,w);w=w*C(n,u)%m*pow(2,pow(2,n-u,m-1),m)%m;if (u&1) ans=ans-w;else ans=ans+w;/* printf("%lld %lld\n",u,w);system("pause");*/ans=(ans%m+m)%m;}printf("%lld\n",ans);return 0;
}