P1762 偶數(shù)
我愛數(shù)學(xué)，但這個(gè)我沒有用數(shù)學(xué)做，數(shù)學(xué)題單里發(fā)現(xiàn)的。
題意
求楊輝三角前 \(n\) 行的偶數(shù)個(gè)數(shù)，\(n\le10^{15}\)
這個(gè)正解是找規(guī)律，可是愚蠢的我怎么能輕易找出來，所以還是去想正常的分析。
眾所周知，楊輝三角的第 \(x\) 行，第 \(y\) 列的數(shù)字是 \(\binom{x-1}{y-1}\),為了方便我們接下來將所有的行數(shù)列數(shù)統(tǒng)統(tǒng)減一。
那麼我們要求的是 \(\binom{x}{y}=0 \mod2\) 的個(gè)數(shù)。
根據(jù)盧卡斯定理我們一拆就會(huì)發(fā)現(xiàn)這個(gè)實(shí)際上就是把 \(x,y\) 進(jìn)行二進(jìn)制拆分，如果但凡有一次出現(xiàn) \(\binom{0}{1}\)，整個(gè)就是 0, 反之都是 1。
但是這個(gè)似乎不太適合直接全求出來，我們考慮能不能求 \(\binom{x}{y}=1 \mod2\)。
這個(gè)簡(jiǎn)單，上邊不都說了只有一種情況才會(huì)是 0, 我們枚舉 \(x\)，從 \(0\) 到 \(n-1\)，對(duì)于其中每一個(gè)數(shù)字求二進(jìn)制下 \(1\) 的個(gè)數(shù)，貢獻(xiàn)是 \(2^{popcount(x)}\)。
我們只需要求解 \(\sum_{i=0}^{n-1}2^{popcount(i)}\)，這個(gè)很明顯可以使用數(shù)位 dp 求解，最后總體減去這個(gè)就行了。
注意算整體的等差數(shù)列不可以直接除以2,要逆元。
代碼：
點(diǎn)擊查看代碼
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int mod=1000003;
const int inv2=(mod+1)/2;
int pow2[100], dp[100][100], bit[100], n;
int dfs(int pos, int cnt, bool limit){
if(!pos) return pow2[cnt];
if(!limit && dp[pos][cnt]!=-1) return dp[pos][cnt];
int up=limit?bit[pos]:1, res=0;
for(int i=0;i<=up;i++)
res=(res+dfs(pos-1,cnt+i,limit&&(i==up)))%mod;
if(!limit) dp[pos][cnt]=res;
return res;
}
int solve(unsigned long long x){
int len=0;
while(x){
bit[++len]=x&1;
x>>=1;}
return dfs(len,0,true);
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
memset(dp,-1,sizeof(dp)); pow2[0]=1;
for(int i=1;i<100;i++) pow2[i]=(pow2[i-1]*2)%mod;
cin>>n; int odd=solve(n-1);
int total=((__int128)n%mod*(n+1)%mod*inv2)%mod;
int even=(total-odd+mod)%mod;
cout<<even<<"\n";
}
浙公網(wǎng)安備 33010602011771號(hào)