[CSP-S模拟测试]:数学课（找规律+数学）

题目传送门（内部题145）

输入格式

　　从$math.in$读入数据。
　　第一行两个数，为$n,q$。接下来$q$行每行一个数$m$，询问大小为$m$的$A$一共有多少个。

输出格式

　　输出答案到$math.out$。
　　共$q$行，每行一个数，表示方案数$\mod 10000019$。

样例

样例输入1：

3 3
0
1
2

样例输出1：

0
2
2

样例输入2：

100 4
45
50
60
70

样例输出2：

2085406
6657572
7844331
0

数据范围与提示

样例解释：

　　对于第一个样例，$P=\{1,2,3\}$，$A$可以选$\{1\},\{2\},\{1,3\},\{2,3\}$，大小为$1$的两种，大小为$2$的也有两种。对于第二个样例，我想到了一个绝妙的解释，可惜这里写不下。

数据范围：

$subtask1:20pts,n,m,q\leqslant 20$。
$subtask2:30pts,n,m,q\leqslant 5,000$。
$subtask3:30pts,n,m\leqslant 10,000,000,q\leqslant 100,000$。
$subtask4:20pts,n,m\leqslant 10^{18},q\leqslant 100,000$。

题解

又是找规律，但是我为什么总是找不出来。

先说一下我考场上的做法，因为$x$和$2x$不能在一个集合，所以$x$和$4x$就必须在一个集合，以此类推，$\Theta(n^2)DP$就有了。

然后发现相同的$n$其实就是杨辉三角中的一行乘上一个系数，二分找到是哪一行就好了……

时间复杂度：$\Theta(q\log_{mod} n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

const int mod=10000019;

long long n,m;

int q;

long long fac[mod],inv[mod];

long long cnt,base,val=1;

long long qpow(long long x,long long y)

{

	long long res=1;

	if(y<0)return 0;

	while(y)

	{

		if(y&1)res=res*x%mod;

		x=x*x%mod;y>>=1;

	}

	return res;

}

void pre_work()

{

	fac[0]=1;

	for(int i=1;i<mod;i++)fac[i]=fac[i-1]*i%mod;

	inv[mod-1]=qpow(fac[mod-1],mod-2);

	for(int i=mod-1;i;i--)inv[i-1]=inv[i]*i%mod;

}

long long lucas(long long x,long long y)

{

	if(x<y)return 0;

	return fac[x]*inv[y]%mod*inv[x-y]%mod;

}

long long C(long long x,long long y)

{

	if(!y)return 1;

	return lucas(x%mod,y%mod)*C(x/mod,y/mod)%mod;

}

int main()

{

	pre_work();

	scanf("%lld%d",&n,&q);

	for(long long i=1,j=2;j<=n*2;i++,j<<=1)

	{

		long long L=1,R=n+1;

		long long l=1,r=n+1;

		while(l<r)

		{

			long long mid=(l+r)>>1;

			if(ceil(log2(n/mid+1))>i)l=mid+1;

			else r=mid;

		}

		while(L<R)

		{

			long long mid=(L+R)>>1;

			if(ceil(log2(n/mid+1))>=i)L=mid+1;

			else R=mid;

		}

		long long x;

		if(L&1)x=(L-l)/2;

		else x=(L-l+1)/2;

		base+=i/2*x;

		if(i&1)cnt+=x;

		else val=val*qpow(2,x%(mod-1))%mod;

	}

	while(q--)

	{

		scanf("%lld",&m);

		m-=base;

		if(m<0||cnt<m)puts("0");

		else printf("%lld\n",val*C(cnt,m)%mod);

	}

	return 0;

}

rp++

巴特西