傳送門(mén)

文章目錄

• 題意：
• 思路：

題意：

給一個(gè)長(zhǎng)度為$n$的二進(jìn)制，求滿(mǎn)足如下條件的$j,i$對(duì)數(shù)：
$(1)0<=j<=i<=n$
$(2)i\&n=i$
$(3)i\&j=0$

思路：

首先把條件轉(zhuǎn)化成人話(huà)，可以發(fā)現(xiàn)選出來(lái)的$i$在原二進(jìn)制串里面一定都是選$1$的位置，而且選出來(lái)的$j$選的位置一定是$i$沒(méi)選的位置+原來(lái)值為$0$的位置。讓后我們需要保證$j<=i$，那么我們就可以枚舉每次$i$選的最后一個(gè)$1$的位置，設(shè)前面有$x$個(gè)$1$，$y$個(gè)0，那么答案顯然就是$2^y?{\sum }_{i=0}^{x}C(x,i)?2^{x?i}$，由于$C(x,i)$在$[0,x]$上值是對(duì)稱(chēng)的，所以我們可以寫(xiě)成$2^y?{\sum }_{i=0}^{x}C(x,i)?2^i$，讓后到這里我就不會(huì)啦，因?yàn)槲抑粫?huì)$O(n)$求這個(gè)式子${\sum }_{i=0}^{x}C(x,i)?2^i$，讓后我就放棄這個(gè)題去搞別的啦。結(jié)果搜題解的時(shí)候發(fā)現(xiàn)一個(gè)這樣的公式$(x+1{)}^n={\sum }_{i=0}^{n}C(n,i)?x^i$，woc，還有這種公式🐎，這是我沒(méi)想到的，那么上面就變成了$2^y?3^x$，最后加上$i=0,j=0$的情況，這樣問(wèn)題就解決啦。

不過(guò)仔細(xì)一想，${\sum }_{i=0}^{x}C(x,i)?2^{x?i}$不就是個(gè)二項(xiàng)式定理的展開(kāi)式🐎，我是真滴菜。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,x,y; LL ans=0; char s[N];LL qmi(LL a,LL b) {LL ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);int _; scanf("%d",&_);while(_--){scanf("%s",s+1);int len=strlen(s+1);x=y=0; ans=0;for(int i=len;i>=1;i--){if(s[i]=='0') x++;else (ans+=qmi(2,x)*qmi(3,y)%mod)%=mod,y++;}printf("%lld\n",(ans%mod+1)%mod);}return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的2019 ICPC Asia Nanchang Regional And and Pair 组合数学的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。