2017 四川省赛 L.Nice Trick(递推 DP)


思路:


方法一:因为已经告诉你了n个取3个的乘积和,所以可以利用这个公式递推,ans[i] = ans[i-1]+S(i-1,3)*a[i]


方法二:设 f(i, j) 表示在前 i 数里面挑 j 个乘起来的总和,那么f(i, j) = f(i − 1, j) + f(i − 1, j − 1) × ai


方法一代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxn = 1e5+5;
ll a[maxn], n;

ll qmod(ll x, ll p)
{
    ll ans = 1;
    while(p)
    {
        if(p%2) ans = ans*x%mod;
        x = x*x%mod;
        p /= 2;
    }
    return ans;
}

int main(void)
{
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        ll ans = 0;
        ll sum1 = 0, sum2 = 0, sum3 = 0;
        for(int i = 1; i <= n; i++)
        {
            if(n > 3)
            {
                ll tmp = (qmod(sum1, 3)-3*sum2%mod*sum1%mod+2*sum3%mod+mod)%mod*qmod(6, mod-2)%mod*a[i]%mod;
                ans = (ans+tmp)%mod;
            }
            sum1 = (sum1+a[i])%mod;
            sum2 = (sum2+a[i]*a[i])%mod;
            sum3 = (sum3+a[i]*a[i]%mod*a[i])%mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}


方法二代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
ll a[maxn], dp[maxn][5];

int main(void)
{
    int n;
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        memset(dp, 0, sizeof(dp));
        dp[1][1] = a[1];
        for(int i = 2; i <= n; i++)
        {
            for(int j = 1; j <= 4; j++)
            {
                if(j == 1) dp[i][j] = (dp[i-1][j]+a[i])%mod;
                else dp[i][j] = (dp[i-1][j]+a[i]*dp[i-1][j-1])%mod;
            }
        }
        printf("%lld\n", dp[n][4]);
    }
    return 0;
}


版权声明:本文为CillyB原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/CillyB/article/details/75212598

智能推荐

【Sublime】使用 Sublime 工具时运行python文件

使用 Sublime 工具时报Decode error - output not utf-8解决办法   在菜单中tools中第四项编译系统 内最后一项增添新的编译系统 自动新建 Python.sublime-build文件,并添加"encoding":"cp936"这一行,保存即可 使用python2 则注释encoding改为utf-8 ctr...

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

猜你喜欢

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...

小demo:slideDown()实现二级菜单栏下拉效果

效果如下,鼠标经过显示隐藏的二级菜单栏 但是这样的时候会存在一个问题,就是鼠标快速不停移入移出会导致二级菜单栏闪屏现象,一般需要使用stop()来清除事件  ...

基于docker环境的mysql主从复制

1、安装docker 可以参考之前的博客,之前写过了~ 2、拉取mysql镜像 3、创建mysql01和mysql02实例 主: 从: 4、进入容器修改配置 1)修改主数据库配置 进入主数据库容器 切换到 etc/mysql/目录下 查看可以看到my.cnf文件,使用vim编辑器打开,但是需要提前安装 安装vim命令: 安装成功后,修改my.cnf文件 新增配置后的my.cnf: binlog 日...