清北集训Day6T1(生成函数)

听rqy说可以用生成函数做,感觉比较有意思

我们考虑在DP转移的时候,

$5,7,9$这三个数是没有限制的

因此他们出现的次数用01串表示的话就是$1111111111111111......$

$3,5$这两个数只能出现偶数次且必须出现

因此他们出现的次数用01串表示的话是$0010101010101010101....$

因为是组合计数问题,我们考虑用指数型生成函数来搞

对于第一个肯定就是$e^x$

对于第二个,我们首先用$\frac{e^x+e^{-x}}{2}$构造出$1010101010.....$

然后再减个$1$就好了

这样的话我们不难得到答案的方案实际就是

$\left( e^{x}\right) ^{3}\left( \dfrac {e^{x}+e^{-x}}{2}-1\right) ^{2}$

然后暴力推推推就可以得到

$\dfrac {1}{4}e^{5x}+\dfrac {1}{4}e+\dfrac {6}{4}e^{3x}-\dfrac {4}{4}e^{4x}-\dfrac {4}{4}e^{2x}$

然后快速幂搞一搞就好了

生成函数好神奇QWQ。。。

#include<cstdio>
#include<iostream>
#define int long long 
using namespace std;
const int MAXN=1e6+10;
const int mod=1e9+7;
int a[MAXN]={0,5,1,3,4,2};
int k[MAXN]={0,1,1,6,-4,-4};
int fastpow(int a,int p)
{
    int base=1;
    while(p)
    {
        if(p&1) base=(base*a)%mod;
        a=(a*a)%mod;
        p>>=1;
    }
    return base%mod;
}
main()
{
    int N,ans=0;
    cin>>N;
    for(int i=1;i<=5;i++)
        ans =( ans + fastpow(a[i], N) * k[i] ) %mod;
    cout<<( ans * ( (mod + 1) / 4 ) %mod + mod ) %mod;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小鄧子的技术博客专栏

为什么android API 中有很多对象的创建都是使用new关键字

首先,谢邀。 其次,是怎么找到我知乎账号的,我隐藏的这么深(脸红了) 最后,加入了自己的总结概括,让然也可以当成读书笔记来看。

11730
来自专栏C语言及其他语言

[每日一题]字符串的连接

上一次是要反序输出字符串,而这次是要连接两个字符串,难度都不大,快来试试吧! 题目描述 写一函数,将两个字符串连接 输入 两行字符串 输出 链接后的字符串 样...

32660
来自专栏CSDN技术头条

Python编程中的反模式

这篇文章收集了我在Python新手开发者写的代码中所见到的不规范但偶尔又很微妙的问题。本文的目的是为了帮助那些新手开发者渡过写出丑陋的Python代码的阶段。为...

21460
来自专栏数据结构与算法

洛谷P3871 [TJOI2010]中位数(splay)

12330
来自专栏angularejs学习篇

angularjs学习第三天笔记(过滤器第二篇---filter过滤器及其自定义过滤器)

您好,我是一名后端开发工程师,由于工作需要,现在系统的从0开始学习前端js框架之angular,每天把学习的一些心得分享出来,如果有什么说的不对的地方,请多多指...

9710
来自专栏C/C++基础

C++智能指针

C++中,动态内存的管理是通过一对运算符来完成的,new用于申请内存空间,调用对象构造函数初始化对象并返回指向该对象的指针。delete接收一个动态对象的指针,...

28710
来自专栏程序员互动联盟

【C语言系列】C语言概念--基本数据类型简介

1.概述   C 语言包含的数据类型如下图所示: ? 2.各种数据类型介绍 2.1整型   整形包括短整型、整形和长整形。 2.1.1短整形   short ...

47580
来自专栏龙首琴剑庐

Java总论及三大特性理解

1、对象(object)     万物皆为对象(根类Object类)。     程序是对象的集合(面向对象程序设计语言OOP)。     每个对象都有自己的由其...

30960
来自专栏PPV课数据科学社区

【学习】数据分析师的Python日记-第1天:谁来给我讲讲Python?

今天带来的是PYTHON,这是一篇非常有意思的文章。希望对大家有帮助。 ---- ---- 导语:或许是网上嘈嘈杂杂的关于大数据、互联网的新形势争论,或许是招聘...

21490
来自专栏angularejs学习篇

angularjs学习第三天笔记(过滤器第二篇---filter过滤器及其自定义过滤器)

您好,我是一名后端开发工程师,由于工作需要,现在系统的从0开始学习前端js框架之angular,每天把学习的一些心得分享出来,如果有什么说的不对的地方,请多多指...

10030

扫码关注云+社区

领取腾讯云代金券