小菲和Fib数列

NC222110. 小菲和Fib数列

描述

小菲喜欢上了Fibonacci数列，该数列的通项公式为 $f_{1} = 1, f_{2} = 1,f_{i} = f_{i-1}+f_{i-2} ( i \geq 3)$ ，他试图对该数列进行她独特的求和方式，即对数列中所有本质不同的二元组 $(x_i,x_j)\$ 进行如下运算 $(x_i*x_j+1) \%2\$ （%为取模运算）,并对所有本质不同的二元组的运算结果进行加和。
注：本质不同的二元组为组内两个元素的下标是该数列元素下标的唯一组合。例如 $（a_{1},a_{2}）$ 和 $（a_{2},a_{1}）$ 是本质相同的二元组，而 $（a_{3},a_{1}）$ 和 $（a_{2},a_{1}）$ 则是不同的。

输入描述

输入一个正整数,表示数列元素的个数。

输出描述

输出一个正整数，表示用小菲的运算方式得到的答案。

示例1

输入:

输出:

说明:

数列为{1,1,2,3}
运算结果为 (1*1+1)%2+(1*2+1)%2+(1*3+1)%2+(1*2+1)%2+(1*3+1)%2+(2*3+1)%2 = 3;

上次编辑到这里，代码来自缓存点击恢复默认模板

C 解法, 执行用时: 5ms, 内存消耗: 440K, 提交时间: 2021-05-24 20:09:18

#include<stdio.h>
int main()
{
	int N,n,m;
	int res;
	scanf("%d",&N);
	n=N/3;
	m=2*(N/3)+N%3;
	res=n*m+(n*(n-1)/2);
	printf("%d",res);
	return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 416K, 提交时间: 2021-09-11 13:41:57

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int t=n/3;
    cout<<t*(n-t)+t*(t-1)/2<<endl;
}

Python3 解法, 执行用时: 66ms, 内存消耗: 7112K, 提交时间: 2021-10-22 15:32:17

n=int(input())
even = n//3
odd = n//3 * 2 + n%3
print(even*odd+ even*(even-1)//2)