1875144_ac_76ms_3940k.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
long sum[1000001];
int main()
{
 long n, i;
 sum[1] = 1; sum[2] = 2;
 scanf("%ld",&n);
 for(i = 3; i <= n; i++)
  {
    if(i%2) sum[i] = sum[i-1];
    else sum[i] = sum[i-2]+sum[i/2];
    sum[i]%=1000000000;
  }
  printf("%ld\n",sum[n]);
  return 1;
}