轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年12月14日 星期日

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的運算式要想清楚,不然會出問題。


#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));
    }
}