关键词：
题意：
一个整数数组，满足：
1. 长度为n
2. 所有元素都在[l, r]范围内
3. 所有元素的和能被3整除
给出n, l, r (1 ≤ n ≤ 2*10^5,1 ≤ l ≤ r ≤ 10^9)
请找出符合条件的数组的个数，答案对 10^9 + 7取模
首先我们要处理出[l, r]中对3取模得结果分别为0，1，2的数的个数，在一个合乎要求的数组中，结果为1和2的数的个数必然一样，由此就可以很方便地得到所有可能的组合的个数。但新的问题来了，由于可以选用相同的数，求出这些组合的排列数几乎是一个不可能完成的任务（对我这种蒟蒻来说）。
换一种思路，我们一个数一个数地添，并把所有可能的情况都考虑进去：
设dp[i][j]表示有i个数，且它们的和对3取模结果为j的数组个数，数组num[i]中记录了[l, r]中对3取模得结果为i的数的个数
显然dp[1][j] = num[j]，随后，向已有的数组的尾部添加新的数字，例如：
dp[i][0] = dp[i - 1][0] * num[0] + dp[i - 1][1] * num[2] + dp[i - 1][2] * num[1]
dp[i][1]和dp[i][2]的情况同理，递推到n，dp[n][0]就是我们要的答案。
为什么是添加到尾部？不能插入到某个数字前吗？这样做会不会漏情况？
实际上，插入到某个数字之前会带来重复（会有另一个数被顶到尾部），举个例子：现在前i - 1个数的和对3取模结果为1，要添加一个结果为2的数，即dp[i - 1][1] * num[2]，如果把它插入到前面，使一个对3取模结果为1的数被顶到了前面的话，显然就与dp[i - 1][2] * num[1]的情况重复了，另外两种情况同理。
附关键部分代码，欢迎纠错。
const int mod = 1e9 + 7; const int maxn = 2e5 + 5; ll dp[maxn][3];//有i个数，且它们的和对3取模结果为j的数组个数 int main() //num[i]记录了对3取模结果为i的数的个数 dp[1][0] = num[0], dp[1][1] = num[1], dp[1][2] = num[2]; for(int i = 2; i <= n; i++) dp[i][0] = (dp[i - 1][0] * num[0]) % mod + (dp[i - 1][1] * num[2]) % mod + (dp[i - 1][2] * num[1]) % mod; dp[i][0] %= mod; dp[i][1] = (dp[i - 1][0] * num[1]) % mod + (dp[i - 1][1] * num[0]) % mod + (dp[i - 1][2] * num[2]) % mod; dp[i][1] %= mod; dp[i][2] = (dp[i - 1][0] * num[2]) % mod + (dp[i - 1][1] * num[1]) % mod + (dp[i - 1][2] * num[0]) % mod; dp[i][2] %= mod; cout << dp[n][0] << endl;
codeforces1105cayoubandlostarray
题目大意： 一个长度为$n$的数组，其和能被$3$整除，且每一个数字满足$a_iin[l,r]$，问有多少种可以满足上述三个条件的数组分析： $dp$。$dp[i][j]=$前$i$个数构成余数为$j$的方案数，然后通过这个$dp$的定义，可以推出递推... 查看详情
cf1105dkilaniandthegame(代码片段)
思路：模拟多源bfs。实现：1#include<bits/stdc++.h>2usingnamespacestd;3typedefpair<int,int>pii;4chara[1005][1005];5constintdx[4]=1,0,-1,0;6constintdy[4]=0,1,0,-1;7ints[10],ans[10],l[10],d[1005][100 查看详情
$cf1105ehelpinghiasat$最大团
正解:$meet-in-the-middle/BornKerbosch$解题报告:传送门.本来总结了下最大团的几个算法写了蛮多,都写完了然后忘保存被拉电闸全没了我好难,,,,所以懒得写了也懒得总结对比了,直接港$meet-in-the-middle$就完事,,,另一个可以去$tt$的博客看$Qw... 查看详情
codeforcesround533div2cayoubandlostarray[dp](代码片段)
一道思维题不仅是和这道题在战斗，我和编译器也进行了一场激烈的角逐因为编译器出了点小问题...对于dev或者codeblocks我的方法是卸载了重新装/重启电脑但是对于vscode我的方法是，对着它掉眼泪，看它能不能可怜可怜我，赶紧... 查看详情
PCF 调度作业
...作业【英文标题】：PCFSchedulingjobs【发布时间】：2018-05-1105:43:12【问题描述】：我一直在尝试通过PCF调度程序安排SpringCloud任务，但是我无法从应用程序/任务创建作业（按照网站上的此文档-http://docs.pivotal.io/pcf-scheduler/1-1/using-jobs... 查看详情
1105.spiralmatrix(25)
ThistimeyourjobistofillasequenceofNpositiveintegersintoaspiralmatrixinnon-increasingorder.Aspiralmatrixisfilledinfromthefirstelementattheupper-leftcorner,thenmoveinaclockwisespiral.Thematrixhasmrowsan 查看详情
pat1105:spiralmatrix
1105.SpiralMatrix(25)时间限制150ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueThistimeyourjobistofillasequenceofNpositiveintegersintoa spiralmatrix innon-increasingorder.A spiralmatrixisfi 查看详情
pat1105spiralmatrix(代码片段)
1105 SpiralMatrix（25 分）Thistimeyourjobistofillasequenceof N positiveintegersintoa spiralmatrix innon-increasingorder.Aspiralmatrixisfilledinfromthefirstelementattheupper- 查看详情
51nod1105(二分)
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1105 题意：中文题诶～ 思路：直接二分答案，再通过二分找有多少组合大于等于当前值，确定答案； 代码：1#include<iostream>2#include<stdio.h>3#include<algo 查看详情
为啥我在 Azure Sql 数据库中看到 Sql 错误 1105？
】为啥我在AzureSql数据库中看到Sql错误1105？【英文标题】：WhyamIseeingSqlError1105inmyAzureSqlDatabase?为什么我在AzureSql数据库中看到Sql错误1105？【发布时间】：2020-08-1912:08:48【问题描述】：我有一个托管在AzureSql中的数据库，并看到一... 查看详情
pat_a1105#spiralmatrix(代码片段)
Source:PATA1105 SpiralMatrix (25 分)Description:Thistimeyourjobistofillasequenceof N positiveintegersintoa spiralmatrix innon-increasingorder.Aspiralmatrixisfilledinf 查看详情
pat1105
#include<iostream>#include<string>#include<map>#include<vector>#include<algorithm>#include<queue>#include<set>#include<stack>usingnamespacestd;intmain() 查看详情
1105判断友好数对
题目来源：https://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1105Description输入两个正整数m和n，顺序输出m到n之间的所有友好数对。如果两个整数的所有正因子之和（包括1，不包括自身）等于对方，就称这对数是友好的。例如：1184和1210是友... 查看详情
1105spiralmatrix(25分)(代码片段)
1105SpiralMatrix(25分)ThistimeyourjobistofillasequenceofNpositiveintegersintoaspiralmatrixinnon-increasingorder.Aspiralmatrixisfilledinfromthefirstelementattheupper-leftcorner,thenmoveinaclockwisespiral.Thematrixhasmrowsandncolumns,wheremandnsatisfythefollowing:m×nmustbeequaltoN;m≥n;andm?nisthem... 查看详情
1105.spiralmatrix(25)模拟——pat(advancedlevel)practise
题目信息1105.SpiralMatrix(25)时间限制150ms内存限制65536kB代码长度限制16000BThistimeyourjobistofillasequenceofNpositiveintegersintoaspiralmatrixinnon-increasingorder.Aspiralmatrixisfilledinfromthefirstelementattheupper- 查看详情
1105spiralmatrix（25分）(代码片段)
Thistimeyourjobistofillasequenceof N positiveintegersintoa spiralmatrix innon-increasingorder.Aspiralmatrixisfilledinfromthefirstelementattheupper-leftcorner,thenmoveinaclockwisesp 查看详情
pat1105spiralmatrix(代码片段)
Thistimeyourjobistofillasequenceof N positiveintegersintoa spiralmatrix innon-increasingorder.Aspiralmatrixisfilledinfromthefirstelementattheupper-leftcorner,thenmoveinaclockwisesp 查看详情
codevs1105过河
1105过河 2005年NOIP全国联赛提高组 时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解题目描述 Description在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌... 查看详情