博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CodeForces - 1105C (dp)
阅读量:6974 次
发布时间:2019-06-27

本文共 1306 字,大约阅读时间需要 4 分钟。

这道题是一道dp题,给出数组的个数n,上下边界l和r(包括l,r),要求满足所有数组中元素之和满足被3整除的情况有多少种,

我们可以知道l到r中被3整除的数有mod0个,被3整除余1的有mod1个,被3整除余2的有mod2个。

dp[i][j]表示数组中前i个数的和被3整除余j的个数,我们要求的就是dp[n][0];

dp[i][0]=dp[i][0]*mod0+dp[i][1]*mod2+dp[i][2]*mod1,依次类推

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 using namespace std;13 14 int mod = 1000000007;15 typedef long long ll;16 typedef unsigned long long ull;17 ll dp[200005][3];18 19 int main()20 {21 ll n,l,r;22 while (cin >> n >> l >> r)23 {24 25 ll mod0 = r/3-l/3;26 if (l % 3 == 0)27 mod0+=1;28 ll mod1 = (r + 2) / 3 - (l + 2) / 3;29 if ((l + 2) % 3 == 0)30 mod1 += 1;31 ll mod2 = r-l+1-mod0-mod1;32 memset(dp, 0, sizeof(0));33 dp[1][0] = mod0;34 dp[1][1] = mod1;35 dp[1][2] = mod2;36 for (int i = 2; i <= n; i++)37 {38 dp[i][0] = (dp[i - 1][0] * mod0 + dp[i - 1][1] * mod2 + dp[i - 1][2] * mod1)%mod;39 dp[i][1] = (dp[i - 1][0] * mod1 + dp[i - 1][1] * mod0 + dp[i - 1][2] * mod2) % mod;40 dp[i][2]= (dp[i - 1][0] * mod2 + dp[i - 1][1] * mod1 + dp[i - 1][2] * mod0) % mod;41 }42 cout << dp[n][0] % mod << endl;43 }44 return 0;45 }

 

转载于:https://www.cnblogs.com/QingFengDaHui/p/10485380.html

你可能感兴趣的文章
Win7/Win8 系统下安装Oracle 10g 提示“程序异常终止,发生未知错误”的解决方法...
查看>>
获得PMP证书的这一年
查看>>
大型网站架构演变和知识体系
查看>>
jQuery EasyUI 表单插件 - Datebox 日期框
查看>>
要哭了,模拟器键盘一直不显示
查看>>
获取下个月的今天
查看>>
elasticsearch简介
查看>>
文件分区格式化及挂载
查看>>
Centos运行级别和开机过程
查看>>
Linux 装B之作酷炫小工具
查看>>
Citrix Avalon安装实验手册之一----Avalon概述及实验环境准备
查看>>
动态表单构建器——建造者模式
查看>>
Android 自动化测试
查看>>
MySQL 5.5 服务器变量详解(二)
查看>>
bootstrap table
查看>>
CentOS 7 yum 安装 MySQL5.7
查看>>
企业网络翻译官——DNS
查看>>
RocketMQ3.2.2生产者发送消息自动创建Topic队列数无法超过4个
查看>>
USG防火墙telnet实验
查看>>
[给12306支招]取消车票预订-采用全额预售(充值)
查看>>