數學課(math)

題目描述

?

wzy又來上數學課了……?雖然他很菜，但是數學還是懂一丟丟的。老師出了一道題，給定一個包含nn個元素的集合P=1,2,3,…,nP=1,2,3,…,n，求有多少個集合A?PA?P，滿足任意x∈Ax∈A有2x?A2x?A，且對于AA在PP中的補集BB，也滿足任意x∈Bx∈B有2x?B2x?B。

wzy花費了1E100天終于算出來了這個答案，但是可惡的caoxia居然又加了一個條件！他要求AA的大小恰好為mm，這樣又有多少個AA呢？

這回wzy真的不會了，他找到了你，希望能夠得到幫助。由于答案太大，你只需要輸出答案mod10000019mod10000019即可。

?

輸入

?

第一行兩個數，為n,qn,q。接下來qq行每行一個數mm，詢問大小為mm的AA一共有多少個。

?

輸出

?

共qq行，每行一個數，表示方案數mod10000019

?

樣例解釋

對于第一個樣例，P={1,2,3}，P可以選{1},{2},{1,3},{2,3}，大小為1的兩種，大小為2的也有兩種。

對于第二個樣例，我想到了一個絕妙的解釋，可惜這里寫不下。

數據范圍及約定

subtask1：20pts，n,m,q≤20n,m,q≤20.

subtask2：30pts，n,m,q≤5,000n,m,q≤5,000.

subtask3：30pts，n,m≤10,000,000,q≤100,000n,m≤10,000,000,q≤100,000

subtask4：20pts，n,m≤1018,q≤100,000n,m≤1018,q≤100,000

?

?

來源

noip2018模擬-南外

---

solution

暴力想法，把每個奇數和他乘上2的若干倍丟進數組

可知我的集合一定要選一半

令x=num/2;

那么如果個數為奇數，可以選x/x+1

為偶數則只能選x個

假設奇數個數的數目為NA，偶數個數為NB,sum為一定得選的個數

答案即C（NA，m-sum）*2^NB

也就是選出m-sum個x+1 nb的可以瞎選（每個兩種方案）

注意到模數只有10000019，C（n,m）可以用lucas定理求

lucas忘光。。。

如果n<m可以直接return 0，因為這樣子N！一定包括mod

#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define ll long long #define mod 10000019 using namespace std; int q; ll n,m,x,h[mod+10],ny[mod+10],num[70]; ll work(ll a,ll num){ll ans=1;while(num){if(num&1)ans=ans*a;a=a*a;a%=mod;ans%=mod;num>>=1;}return ans; } ll C(int N,int M){if(N<M)return 0;return h[N]*ny[M]%mod*ny[N-M]%mod; } ll Lucas(ll N,ll M){if(!M)return 1;return Lucas(N/mod,M/mod)*C(N%mod,M%mod)%mod; } int main() {cin>>n>>q;ll x=2,la=n,cnt=0,sum=0,na=0,nb=0;if(la%2==0)la--;while(1){ll now=n/x;if(now%2==0)now++;else now+=2;num[++cnt]=(la-now)/2+1;if(cnt&1)na=na+num[cnt];else nb=nb+num[cnt];sum=sum+num[cnt]*(cnt/2);if(now==1)break;la=now-2;x<<=1;}h[0]=1;for(int i=1;i<mod;i++)h[i]=h[i-1]*i%mod;ny[mod-1]=work(h[mod-1],mod-2);for(int i=mod-2;i;i--)ny[i]=ny[i+1]*(i+1)%mod;ny[0]=1;while(q--){scanf("%lld",&m);if(m<sum||m>na+sum){puts("0");continue;}ll ans=Lucas(na,m-sum)*work(2,nb)%mod;ans=(ans+mod)%mod;printf("%lld\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/liankewei/p/10358780.html

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的数学课(math)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。