3113: CT5异或方程
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
⊕ 代表异或（xor）运算，运算规则为：
- 当只有一位比特参与运算时，0⊕0=00⊕0=0，0⊕1=10⊕1=1，1⊕0=11⊕0=1，1⊕1=01⊕1=0（相同为00，相异为11）；
- 当有多位比特参与运算时，对每位比特分别取异或运算，如 0101⊕1011=11100101⊕1011=1110；
给定一个正整数 �n，求 00 到 2�−12n−1 中有多少个数 �x 满足以下方程：
�⊕2�⊕3�=0x⊕2x⊕3x=0
由于满足条件的 �x 可能很多，请将方案数对 109+9109+9 取模。
输入
单个正整数：表示 �n。
- 对于 50%50% 的数据，1≤�≤101≤n≤10；
- 对于 100%100% 的数据，1≤�≤1000001≤n≤100000。
输出
单个自然数：表示方案数对 109+9109+9 取模的余数。
样例输入 复制
3样例输出 复制
5提示
满足方程的数字有：000，001，010，100，101
1. 通过小数据找到规律
2. 注意异或运算符，加上括号
3. 归纳总结：斐波那契数列
1. 通过小数据找到规律
2. 注意异或运算符，加上括号
3. 归纳总结：斐波那契数列