当前位置： 移动技术网 > IT编程>开发语言>C/C++ > POJ3734 Blocks(生成函数)

POJ3734 Blocks(生成函数)

2019年03月14日  | 移动技术网IT编程  | 我要评论

屏南二手房,郭家大院,地产江湖藏经阁

题意

长度为\(n\)的序列，用红黄蓝绿染色，其中红黄只能是偶数，问方案数

sol

生成函数入门题

任意的是\(e^x\)，偶数的是\(\frac{e^x + e^{-x}}{2}\)

最后化完是\(\frac{e^{4x} + 2e^{2x}+1}{4} = \frac{4^n+2 * 2^{n+1}}{4}\)(\(\frac{1}{4}\))相当于常数项

#include<iostream>
#include<cstdio>
using namespace std;
const int mod = 10007;
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = 1ll * base * a % mod;
        a = 1ll * a * a % mod; p >>= 1;
    }
    return base;
}
void solve() {
    int n; cin >> n;
    cout << 1ll * (fp(4, n) + 2ll * fp(2, n) % mod) % mod * fp(4, mod - 2) % mod << '\n';
}
int main() {
    int t; cin >> t;
    for(; t--; solve());
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网