此题非常好，有多种递推or找规律思路。
首先是谢尔宾斯基三角形，可以得到这种递推思路
另外是根据陈立杰的blog （2010年。。哎）。
也就是说，我们需要统计前n行（n从1开始）奇数的个数，也就是sigma(i, 1, n) 2^(f(i))
f(i)这里是i的二进制形式中的1的个数。

把上述sigma记为s(n)，那么很容易想到一个递推s(n)=2* s(n-2^k) + s(2^k)

也就是按照2^k（小于n的最大2的幂）分割。因为2^k+1~n这段的数，每个都对应着比1~n-2^k多一个“1”，于是就有乘2的关系。

import math
n = int(raw_input())
res = {}
def s(n):
    if res.get(n):
        return res[n]
    if n == 1:
        return 1
    if n == 2:
        return 3
    k = int(math.floor(math.log(n, 2)))
    mid = 2**k
    if mid == n:
        mid /= 2
    tmp = 2*s(n-mid) + s(mid)
    res[n] = tmp
    return tmp
n += 1
print n*(n+1)/2 - s(n)

来一波C++题解（写了半天高精qwq）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int C = 10000;
struct Info
{
int val[50];
};
Info New(int y)
{
Info x;
memset(x.val,0,sizeof x.val);
if(y)
{
x.val[0]=1;
x.val[1]=y;
}
return x;
}
char data[55];
Info dr()
{
Info x=New(0);
scanf("%s",data);
int n=strlen(data);
x.val[0]=(n+3)/4;
int i;
for(i=0;n-1-i>i;i++)
swap(data[i],data[n-1-i]);
for(i=0;i<n;i++)
{
int zhi=data[i]-'0';
if(i%4>0)
zhi*=10;
if(i%4>1)
zhi*=10;
if(i%4>2)
zhi*=10;
x.val[i/4+1]+=zhi;
}
return x;
}
void sc(Info x)
{
int i;
printf("%d",x.val[x.val[0]]);
for(i=x.val[0]-1;i>=1;i--)
printf("%04d",x.val[i]);
printf("\n");
}
bool da(Info x,Info y)
{
if(x.val[0]>y.val[0])
return 1;
if(x.val[0]<y.val[0])
return 0;
int i;
for(i=x.val[0];i>=1;i--)
{
if(x.val[i]>y.val[i])
return 1;
if(x.val[i]<y.val[i])
return 0;
}
return 0;
}
Info jia(Info x,int y)
{
x.val[1]+=y;
int i;
for(i=1;i<=x.val[0];i++)
{
x.val[i+1]+=x.val[i]/C;
x.val[i]%=C;
}
while(x.val[x.val[0]+1])
{
x.val[0]++;
x.val[x.val[0]+1]=x.val[x.val[0]]/C;
x.val[x.val[0]]%=C;
}
return x;
}
Info jiax(Info x,Info y)
{
int i;
x.val[0]=max(x.val[0],y.val[0]);
for(i=1;i<=x.val[0];i++)
x.val[i]+=y.val[i];
for(i=1;i<=x.val[0];i++)
{
x.val[i+1]+=x.val[i]/C;
x.val[i]%=C;
}
while(x.val[x.val[0]+1])
{
x.val[0]++;
x.val[x.val[0]+1]=x.val[x.val[0]]/C;
x.val[x.val[0]]%=C;
}
return x;
}
Info jian(Info x,int y)
{
x.val[1]-=y;
int i;
for(i=1;i<=x.val[0];i++)
{
if(x.val[i]<0)
{
x.val[i]+=C;
x.val[i+1]--;
}
else
break;
}
while(x.val[0] && !x.val[x.val[0]])
x.val[0]--;
return x;
}
Info jianx(Info x,Info y)
{
int i;
for(i=x.val[0];i>=1;i--)
x.val[i]-=y.val[i];
for(i=1;i<=x.val[0];i++)
{
if(x.val[i]<0)
{
x.val[i]+=C;
x.val[i+1]--;
}
}
while(x.val[0] && !x.val[x.val[0]])
x.val[0]--;
return x;
}
Info cheng(Info x,int y)
{
int i;
for(i=1;i<=x.val[0];i++)
x.val[i]*=y;
for(i=1;i<=x.val[0];i++)
{
x.val[i+1]+=x.val[i]/C;
x.val[i]%=C;
}
while(x.val[x.val[0]+1])
{
x.val[0]++;
x.val[x.val[0]+1]=x.val[x.val[0]]/C;
x.val[x.val[0]]%=C;
}
while(x.val[0] && !x.val[x.val[0]])
x.val[0]--;
return x;
}
Info chengx(Info y,Info z)
{
Info x=New(0);
int i,j;
for(i=1;i<=y.val[0];i++)
{
for(j=1;j<=z.val[0];j++)
{
x.val[i+j-1]+=y.val[i]*z.val[j];
}
}
x.val[0]=y.val[0]+z.val[0]-1;
for(i=1;i<=x.val[0];i++)
{
x.val[i+1]+=x.val[i]/C;
x.val[i]%=C;
}
while(x.val[x.val[0]+1])
{
x.val[0]++;
x.val[x.val[0]+1]=x.val[x.val[0]]/C;
x.val[x.val[0]]%=C;
}
while(x.val[0] && !x.val[x.val[0]])
x.val[0]--;
return x;
}
Info chu(Info x,int y)
{
int i;
int has=0;
for(i=x.val[0];i>=1;i--)
{
has*=C;
has+=x.val[i];
x.val[i]=has/y;
has%=y;
}
while(x.val[0] && !x.val[x.val[0]])
x.val[0]--;
return x;
}
Info f(Info x)
{
Info res=New(0);
if(!x.val[0])
return res;
Info now=New(1);
Info sum=New(2);
while(1)
{
now=cheng(now,2);
if(da(now,x))
break;
sum=jian(cheng(sum,3),2);
}
now=chu(now,2);
sum=jiax(sum,cheng(f(jianx(x,now)),2));
return sum;
}
int main()
{
//freopen("count.in","r",stdin);
//freopen("count.out","w",stdout);
Info n,ans;
n=dr();
ans=chu(chengx(n,jia(n,3)),2);
ans=jianx(ans,f(n));
sc(ans);
return 0;
}

终于过了...感谢curimit出了如此好题.
找规律+调试好几小时,100多行的高精度.

闲话少说,matrix67神牛在书里讲过,把杨辉三角形按奇偶性黑白染色可以得到谢尔宾斯基三角形,所以根据分形图形自相似性,可以计算总的黑白结点数.

orz各位大牛!

高精度+数学，注意i的二进制与第i行奇数个数的关系
Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
145 lines compiled, 0.1 sec , 28688 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 0 ms, mem = 980 KiB, score = 2
测试数据 #1: Accepted, time = 0 ms, mem = 980 KiB, score = 2
测试数据 #2: Accepted, time = 0 ms, mem = 980 KiB, score = 2
测试数据 #3: Accepted, time = 0 ms, mem = 976 KiB, score = 2
测试数据 #4: Accepted, time = 0 ms, mem = 980 KiB, score = 2
测试数据 #5: Accepted, time = 0 ms, mem = 984 KiB, score = 4
测试数据 #6: Accepted, time = 0 ms, mem = 980 KiB, score = 4
测试数据 #7: Accepted, time = 0 ms, mem = 980 KiB, score = 4
测试数据 #8: Accepted, time = 0 ms, mem = 980 KiB, score = 4
测试数据 #9: Accepted, time = 0 ms, mem = 980 KiB, score = 4
测试数据 #10: Accepted, time = 0 ms, mem = 980 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 984 KiB, score = 5
测试数据 #12: Accepted, time = 0 ms, mem = 980 KiB, score = 5
测试数据 #13: Accepted, time = 0 ms, mem = 984 KiB, score = 5
测试数据 #14: Accepted, time = 0 ms, mem = 980 KiB, score = 5
测试数据 #15: Accepted, time = 0 ms, mem = 984 KiB, score = 5
测试数据 #16: Accepted, time = 0 ms, mem = 984 KiB, score = 10
测试数据 #17: Accepted, time = 0 ms, mem = 984 KiB, score = 10
测试数据 #18: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #19: Accepted, time = 0 ms, mem = 984 KiB, score = 10
Accepted, time = 0 ms, mem = 984 KiB, score = 100

为何最后三个点WA，奇了怪了！恶心的高精度！我弄了半天才写出递推式！剧恶心的题目

反过来想就很容易了。。

lucas定理：设 a>=b且b>=0 a=a0*p^0+a1*p^1+.... b=b0*p^0+b1*p^1+.... 那么 C(a,b) mod p =C(a0,b0)*C(a1,b1)*...mod p

可得如果i and k=k则为奇数否则偶数

很无耻的题目……高精度巨恶心……

可以先编一个程序，考察杨辉三角中偶数的分布情况……

之后就有规律了哈~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案错误...程序输出比正确答案长

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 11：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 12：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 13：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 14：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 15：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 16：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 17：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 18：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 19：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 20：运行时错误...| 错误号: 106 | 无效数字格式

很漂亮的结果。。。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

弄了半天，搞出个递推式：

/ 0 (n == 0)

f(n) = |

\ 2^(k + 1) - n + 2 * f(n - 2 ^ k) (k = log2(n)下取整，n > 0)

先找规律（用0表示偶数，1表示奇数），可以发现是一层一层的（截止行数1，3，7，15……）

然后会发现当前层的组成是一个下三角+三个上一层的东西。

因为会有零头，所以用递归好写（类似于分治的思想……）

不带高精度的程序：

program Vijos_P1494;

var

n:int64;

function Get_Num(n:int64):int64;

begin

exit(n*(n+1) shr 1);

end;

function Cal(n:int64):int64;

var

now,last,sum,left:int64;

begin

now:=1;

last:=0;

sum:=0;

while 2*now+12 then inc(sum,2*Cal(left-1));

exit(sum);

end;

begin

readln(n);

writeln(Cal(n));

end.

咋做？？？？？？

这么简单！1次AC

PS:需要用到高精度加低精度、高精度减法、高精度乘单精度、高精度乘法、高精度除单精度、高精度比较、高精度读入、高精度输出。

单精度程序如下：

readln(a);

c:=(a*(a+3)) div 2;

inc(a);

d:=1;

while a>0 do begin

if a mod 2=1 then begin

bin[i]:=true;

d:=d*2;

end;

a:=a div 2;

inc(i);

end;

b:=1;

for j:=0 to i-1 do

if bin[j] then begin

for l:=k+1 to j do b:=b*3;

k:=j;

d:=d div 2;

c:=c-d*b;

end;

writeln(c+1);

AC了，开心！！——XsugarX

好弱的题目

program qiqi;

var a:array[1..10000,1..10000]of longint;

i,j,n,t:longint;

begin

readln(n);

n:=n+1;

a[1,1]:=1;

t:=0;

for i:=2 to n do

begin

a:=1;

a:=1;

for j:=2 to i-1 do

a:=a+a;

end;

for i:=1 to n do

for j:=1 to i do

if a mod 2=0 then t:=t+1;

writeln(t);

end.

大哥大姐们，我的为什么才22分？

http://rpoi.5d6d.com/bbs.php

解题报告这里有...

不过大家还是自己先做~

哪位大牛可以告诉我一下规律。

program p1494;

var a:array[1..100,1..10000] of longint;

i,j,n,b:integer;

begin

read(n);

b:=0;

a[1,1]:=1;

a[1,2]:=1;

for i:=2 to n do

begin

a:=1;

a:=1;

for j:=2 to i do

begin

a:=a+a;

writeln(a,a);

if a mod 2=0 then

inc(b);

end;

end;

write(b);

end.

哪个大牛告诉我错在哪里！！