网站安装不了wordpress,企业如何网络营销推广,给彩票网站做排名违法吗,宜选科技就是帮人做网站传送门:洛谷
解题思路:
考虑设 f ( i ) f(i) f(i)为和为 i i i的拆分权值和,那么我们可以得到一个递推关系式 f ( i ) ∑ i 1 n f ( n − i ) ∗ f i b ( i ) f(i)\sum_{i1}^nf(n-i)*fib(i) f(i)i1∑nf(n−i)∗fib(i)这个表达式的含义就是枚举一个数的值,由于分配率,我们…传送门:洛谷
解题思路:
考虑设 f ( i ) f(i) f(i)为和为 i i i的拆分权值和,那么我们可以得到一个递推关系式 f ( i ) ∑ i 1 n f ( n − i ) ∗ f i b ( i ) f(i)\sum_{i1}^nf(n-i)*fib(i) f(i)i1∑nf(n−i)∗fib(i)这个表达式的含义就是枚举一个数的值,由于分配率,我们给每一个和乘上一个数,相当于给整体乘上一个数 此时我们发现, f ( 0 ) f(0) f(0)应该为 1 1 1,但是光光的由上面的式子,我们并不能得到 f ( 0 ) f(0) f(0)为1,所以我们考虑补充定义 f ( 0 ) 1 f(0)1 f(0)1 也就是说此时 f ( i ) [ n 1 ] ∑ i 1 n f ( n − i ) ∗ f i b ( i ) f(i)[n1]\sum_{i1}^nf(n-i)*fib(i) f(i)[n1]i1∑nf(n−i)∗fib(i) 发现很像一个卷积式子,但是下标不为 1 1 1,因为 f i b ( 0 ) 0 fib(0)0 fib(0)0(这意味着常数项一定为0,不会影响 f ( 0 ) f(0) f(0)的值),所以我们不妨考虑临时扩展上述式子,可以得到: f ( i ) [ n 1 ] ∑ i 0 n f ( n − i ) ∗ f i b ( i ) f(i)[n1]\sum_{i0}^nf(n-i)*fib(i) f(i)[n1]i0∑nf(n−i)∗fib(i) 所以我们可以得到, F F ∗ F I B 1 FF*FIB1 FF∗FIB1 化解一下可以得到 F 1 1 − F I B F\frac{1}{1-FIB} F1−FIB1,对于 F I B FIB FIB数列,我们有一个生成函数的结论(限于篇幅,此处不证) F I B x 1 − x − x 2 FIB\frac{x}{1-x-x^2} FIB1−x−x2x 所以此时我们可以很轻易的写出 F F F的生成函数, F 1 x 1 − 2 ∗ x − x 2 F1\frac{x}{1-2*x-x^2} F11−2∗x−x2x 我们现在需要做的事就是将 F F F展开回去,因为 F [ 1 ] 1 F[1]1 F[1]1,所以1可以直接分开拿出来,现在考虑后面的那一个分式. 根据套路,这应该是一个可以裂项的式子,考虑待定系数法来裂项, 我们可以得到 x 1 − 2 ∗ x − x 2 2 4 ∗ ( 1 1 − ( 1 2 ) x − 1 1 − ( 1 − 2 ) x ) \frac{x}{1-2*x-x^2}\frac{\sqrt{2}}{4}*(\frac{1}{1-(1\sqrt{2})x}-\frac{1}{1-(1-\sqrt{2})x}) 1−2∗x−x2x42 ∗(1−(12 )x1−1−(1−2 )x1) 根据一些生成函数的小结论, ∑ i 0 ∞ x i 1 1 − x \sum_{i0}^{\infty}x^i\frac{1}{1-x} ∑i0∞xi1−x1
我们对上述式子进行展开,可以得到: F 1 ∗ x 0 2 4 ∗ ∑ i 0 ∞ ( ( 1 2 ) i − ( 1 − 2 ) i ) x i F1*x^0\frac{\sqrt{2}}{4}*\sum_{i0}^\infty((1\sqrt{2})^i-(1-\sqrt{2})^i)x^i F1∗x042 ∗i0∑∞((12 )i−(1−2 )i)xi
不难看出,我们最终的答案就是 ( 1 2 ) i − ( 1 − 2 ) i (1\sqrt{2})^i-(1-\sqrt{2})^i (12 )i−(1−2 )i 此时还需要考虑 2 \sqrt{2} 2 的二次剩余,也就是考虑这样的一个同余方程: x 2 ≡ 2 m o d p x^2\equiv2\;mod\;p x2≡2modp 因为我们现在并不是解决二次剩余问题,我们只需要求出一个数的二次剩余,所以我们大可以在本地跑出这个式子的答案.
至此,本题解决. 下面是本题的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
inline void print(__int128 x){if(x0) {putchar(-);x-x;}if(x9) print(x/10);putchar(x%100);
}
#define maxn 1000000
#define int long long
const int mod1e97;
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int qpow(int a,int b) {int ans1;while(b) {if(b1) ansans*a%mod;b1;aa*a%mod;}return ans;
}
int sqrt259713600;
void init() {for(int i1;imod;i) {if(i*i%mod2) {sqrt2i;break;}}
}
signed main() {int n0;string s;cins;for(int i0;is.length();i) n(n*10s[i]-0)%(mod-1);
// init();cout(qpow(1sqrt2,n)-qpow((1-sqrt2mod)%mod,n)%modmod)%mod*qpow(2*sqrt2%mod,mod-2)%modendl;return 0;
}
