Code 備忘錄►Math

TIOJ::1078 . G.陽數

http://tioj.infor.org/problems/1078

這題用到簡單的位元運算和一些枚舉的技巧，把問題切一切就會比較好解。

題目是有一個數字N，改成二進位表示之後，求 1~N(包含1和N)之間的所有數之中，1比0多的數有幾個(比如 11001 就是， 11000就不是，1和0一樣多也不是，第一位不可以是0，比如00111)。

題目感覺很複雜，最自然的做法就是FOR迴圈枚舉，但是N的範圍到10^15所以不可能這樣做。

於是就自然想到排列組合囉，我參考了”NPSC補完計畫”的題解說明，假設N等於 1001011 ，可以拆成 1~111111和 1000000~1001011，1~111111的部分，就是1、1X、1XX、1XXX、1XXXX、1XXXXX的可能數總和，以1XXX來說，因為有一個1了所以 C(3，2) +C(3，3) 就是1XXX的可能數(在三個X中挑2個或3個數是1，其他是0，可以讓這個數字的1比0多)。而另外一個部分，可以拆成1000XXX、100100X、1001011(根據1的位置，將1改成0之後剩下的都是N以下的數字，從中找出答案)，對於1000XXX因為要有4個1，已經出現一個所以剩下C(3，3)種。

所以題目就變成找出數字的最高位的1，找出第一部分和第二部分的和，第一部分(1~111111)可以預處理好。第二部分必須要掃一遍位元，對於每個1都找一次答案數。10^15大約等於2^50，所以可以先把C(0，0)~C(50，50)的表格建好，C剛好就是巴斯卡三角形，所以直接用迴圈建好就好(不會爆long long)，然後因為我們都是取後綴(C(X，Y)~C(X，X)，Y<=X，1可以比需要的數量多所以後綴都是我們要的答案)，因此可以再把後綴和預處理好。

要注意再使用<<位移運算子的時候，如果是 int 的話，最大只能位移32位，之後的數會自動循環(也就是 Y<< (X%32) )(PS.位移的位數用負數會變成0)，但是我們的題目很顯然是 long long 所以在位移前要記得改成 1ll<<X ，在數字後面加上 ll ，可以讓那個數字變成 long long型態，平常在乘法、int 轉 long long的運算上很好用，可以省去打(long long)強轉的長度，不過有時候會有點難找bug，使用的時候還是習慣把數字印出來檢查一下比較安全。

還有算後綴和的時候，我把他寫成一行，卻忘記要扣掉後面的數字了(巴斯卡加上上面的兩個數字時加成後綴和了!!!!!)，還有對於需要幾個1的運算式要想清楚，不然會出問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define Fb(i,n) for(int i=n-1;i>=0;i--)
#define LL long long
#define max(x,y) ((x)>(y)?(x):(y))
LL C[51][52],DP[51];
int main(){
    int t;
    LL n;
    scanf("%d",&t);
    C[0][0]=DP[0]=1;
    Fl(i,1,51)Fb(j,i+1)C[i][j]=(j?C[i-1][j-1]:C[i-1][j])-C[i-1][j+1]+C[i][j+1];
    Fl(i,1,51)DP[i]=DP[i-1]+C[i][(i>>1)+(i&1)];
    // printf("%lld\n",C[3][3]);
    while(t--){
        scanf("%lld",&n);
        int b=51,tag=0;
        while((1ll<<b)&(~n))b--;
        // printf("%d ",b);
        LL ans=b?DP[b-1]:0;
        Fb(i,b)if(n&(1ll<<i)){
            tag++;
            ans+=C[i][max((b+1)/2+1-tag,0)];
            // printf("DD %d %d %d\n",tag,b,max((b+1)/2+1-tag,0));
        }
        printf("%lld\n",ans+((b+1)/2-tag<=0));
    }
}