网络设备互联课设建设企业网站,商场设计理念,wordpress最新文章插件,0基础如何快速做网站茅山道术descriptionsolutioncodedescription
题目描述 小七擅长茅山道术#xff0c;有一天他发现了 n 个排成一行的宝石#xff0c;其中第 i 个宝石 有一个颜色 ci 。 小七决定用茅山道术替换一些宝石#xff0c;具体地#xff0c;他每次施法可以选定两个满足 cl cr 的正…
茅山道术descriptionsolutioncodedescription
题目描述 小七擅长茅山道术有一天他发现了 n 个排成一行的宝石其中第 i 个宝石 有一个颜色 ci 。 小七决定用茅山道术替换一些宝石具体地他每次施法可以选定两个满足 cl cr 的正整数 l; r(1 ≤ l ≤ r ≤ n) 然后将区间 [l; r] 内的宝石全部替换为颜 色为 cl 的宝石。 小七想知道在经过若干次施法后可以一次也不施法最终能形成多少 种可能的颜色序列呢 两个序列不同等价于存在一个 i 使得位置 i 的宝石在两个序列中颜色不 同。由于答案可能很大你只需要输出答案对 109 7 取模的结果。 输入格式 输入文件 magic.in 包含 2 行。 第 1 行输入一个正整数表示 n 。 第 2 行输入 n 个正整数其中第 i 个正整数表示 ci 。 输出格式 输出文件 magic.out 包含一行仅一个非负整数表示答案对 109 7 取模 的结果。 样例输入 6 1 2 1 3 4 3 样例输出 4 数据范围及约定
测试点编号n特殊性质1 ∼ 4≤ 5无5 ∼ 10≤ 2 × 103无11 ∼ 14≤ 106ci ≤ 215 ∼ 20≤ 106无
对于 100% 的数据满足 1 ≤ k ≤ n ≤ 106; 1 ≤ ci ≤ n
solution
case 1~4 随便暴力
case 11~14 具有特殊性质1≤ci≤21\le c_i\le 21≤ci≤2
通过找规律也可以证明答案为nnn对应的斐波拉契数
case 5~10 n≤2000n\le 2000n≤2000
前面的数据点只是为了不让做不出来的人难看罢了只有这个数据点是设置的与正解有关的
显然可以承担n2n^2n2的dpdpdp设fi:[i,n]f_i:[i,n]fi:[i,n]的序列有多少种
暴力枚举iii可以和哪些j(ij)j(ij)j(ij)匹配即fi∑ji1n[cicj]fj1f_i\sum_{ji1}^n[c_ic_j]f_j1fi∑ji1n[cicj]fj1(不匹配保持原序列不变)
case 15~20 n≤106,1≤ci≤nn\le 10^6,1\le c_i\le nn≤106,1≤ci≤n
想办法在比较暴力的dpdpdp基础上优化掉一个nnn
发现对于iii有用的只有和其颜色相同的jjj每个iii都会累加后面的所有与之颜色相同的jjj的答案
这其实是个后缀和的形式后缀和优化即gc:g_c:gc: 到iii为止颜色为ccc的所有j(ij)j(ij)j(ij)的fff之和
每次求完fif_ifi后再对gcig_{c_i}gci进行更新
时间复杂度O(n)O(n)O(n)
还不用对颜色离散化代码就更简单了
code
#include cstdio
#define maxn 1000005
#define int long long
#define mod 1000000007
int n;
int c[maxn], f[maxn], g[maxn];signed main() {freopen( magic.in, r, stdin );freopen( magic.out, w, stdout );scanf( %lld, n );for( int i 1;i n;i ) {scanf( %lld, c[i] );if( c[i] c[i - 1] ) i --, n --;}f[n 1] 1;for( int i n;i;i -- ) {f[i] ( f[i 1] g[c[i]] ) % mod;g[c[i]] ( g[c[i]] f[i 1] ) % mod;}printf( %lld\n, f[1] );return 0;
}
