题目传送门 (内部题 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++
[CSP-S 模拟测试]: 数学课 (找规律 + 数学)
来源: http://www.bubuko.com/infodetail-3285198.html