第一届佳木斯大学程序设计校赛题解

前言

这场比赛又很多原题，总体的难度不高，但是也不是说没有难度，C题和K还是能让我学习到一些东西，B题帮我复习了一下Trie树，总之这场AK了，真不容易，由于本人比较菜如果有问题欢迎在评论区指出。

A.斐波那契数列（循环） 思路

因为数据范围很小所以我们直接使用循环去跑即可，如果数据范围很大(eg: n > 1 e 8 n>1e8 n>1e8)那么我们可以用矩阵快速幂求解，学习链接：https://www.bilibili.com/video/BV1j3411e7qh/

循环代码

#include
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
ll f[N];

int main()
{
	ll n;
	cin>>n;
	f[1]=f[2] = 1;
	for(ll i = 3;i