xcpc近年铜牌题补题路

放弃幻想,准备打铁 随缘补题，学业繁重,补了就更.

45届上海站（2020）

4题铜牌,B,D,G,M G. Fibonacci 链接 鉴定为纯纯签到 给一个斐波那契数列,定义一个二元函数 g ( x , y ) g(x,y) g(x,y), x ∗ y x*y x∗y是偶数的时候,返回1,其他情况返回0 计算 ∑ i = 1 n ∑ j = 1 n g ( f i , f j ) \sum_{i=1}^n \sum_{j=1}^ng(f_i,f_j) ∑i=1n​∑j=1n​g(fi​,fj​), f i f_i fi​是斐波那契数列的第 i i i项. 观察斐波那契数列可知,第 3 ∗ i 3*i 3∗i项必定是一个偶数. 考虑所有有序二元对是 n ∗ ( n − 1 ) / 2 n*(n-1)/2 n∗(n−1)/2,再考虑只包含奇数的对 m ∗ ( m − 1 ) / 2 m*(m-1)/2 m∗(m−1)/2 二者相减就是 x ∗ y x*y x∗y是偶数的对. 只需要算出前n项斐波那契，奇数的个数m即可. 偶数有: n / 3 n/3 n/3个,奇数就有: n − n / 3 n-n/3 n−n/3个.

/*
Tonight I wanna drown in an ocean of you
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;cin>>n;
	ll m = n - n/3;
	ll ans = n*(n-1)/2 - m*(m-1)/2;
	coutn>>m;
		vector s1(n),s2(m);
		map protect;
		for(int i=0;i>s1[i];
		for(int i=0;i>s2[i];
		for(int i=0;i