题目大意
求子集斯特林数\(\left\{\begin{matrix}n\\m\end{matrix}\right\}\%2\)
方法1 数形结合
推荐一篇超棒的博客by Sdchr
就是根据斯特林的递推式，分奇偶讨论
得到一个函数\(P_{n,m}\equiv\left\{\begin{matrix}n\\m\end{matrix}\right\}\% 2\)
再根据函数递推式通过画图，数形结合
转化成图中从一点走到另一点的方案数
变成组合问题求解
做法
这是给连插板都不会的我看的
\(a_1+a_2+...+a_n=D，a_i\ge0\)
大于等于0这个条件难易插板
我们变成
\((a_1+1)+(a_2+1)+...+(a_n+1)=D+n，(a_i+1)\ge1\)
就变成\(D+n-1\)个空隙插\(n-1\)块板了
姿势
要求阶乘中有多少个二的因子
就是\(2^1\)的倍数个数+\(2^2\)的倍数个数+\(2^3\)的倍数个数
LL num(int x){
LL res=0;
for(int i=2;i<=x;i<<=1) res+=x/i;
return res;
}
solution
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Q=1000000007;
const int M=2003;
inline LL rd(){
LL x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return f?x:-x;
}
int tcas;
LL n,m,D,odd;
LL num(int x){
LL res=0;
for(int i=2;i<=x;i<<=1) res+=x/i;
return res;
}
int Calc(int x,int y){
return num(x)-num(y)-num(x-y) == 0;
}
int main(){
int i;
tcas=rd();
while(tcas--){
n=rd(),m=rd();
D=n-m;
odd=(m+1)/2;
printf("%d\n",Calc(D+odd-1,odd-1));
}
return 0;
}
方法二 斯特林数mod 2意义下与组合数关系+lucas定理
\(\left\{\begin{matrix}n\\m\end{matrix}\right\}=\dbinom {z}{w}\)
其中\(z=\lceil n-\frac {m+1} 2\rceil,w=\lfloor \frac {m-1} 2\rfloor\)
而又有结论\(\dbinom n m\%2=[n\)&\(m=m]\)
为什么，用lucas定理证一下
\(\dbinom n m\equiv \dbinom {n\%2}{m\%2}\dbinom{n/2}{m/2}(mod 2)\)
注意到这一项\(\dbinom {n\%2}{m\%2}\)
我们把n，m转为二进制
\(\binom0 1=0\),则若\(n_i=0\)，\(m_i=1\)，则\(\binom n m\equiv 0(mod 2)\)
\(\binom1 0=\binom 1 1=1\)，则若\(n_i=1\),无论\(m_i\)为0还是1对奇偶性无影响
所以有结论
\(\dbinom n m\%2=[n\)&\(m=m]\)