正文 

当前位置： 首页 > 技术 > java教程

cf1140epalindrome-lessarrays(巧妙的递推)(代码片段)

issue是fw issue是fw     2023-01-16     166

关键词：

LINK

题意

一个数组有些位置是 ? ? ?,你可以使用 [ 1 , k ] [1,k] [1,k]填充

满足最后对于 i ∈ [ 1 , n − 2 ] i\\in[1,n-2] i∈[1,n−2]有 a i ! = a i + 2 a_i!=a_i+2 ai​!=ai+2​,求方案数

我们分成奇数索引构成的数组和偶数索引构成的数组分别考虑

现在设奇数索引构成的数组为 a a a,条件限制相当于相邻元素值不能相同.

考虑到 ? ? ?可能连成一块,这就变得非常麻烦,其实可以把连续的 ? ? ?缩成一个块

设 f [ i ] [ 0 ] f[i][0] f[i][0]表示 ? ? ?块长度为 i i i,且问号块左右两端的数字不相等的方案, f [ i ] [ 1 ] f[i][1] f[i][1]表示两端相等

(注意这里的两端不是问号,是最左边问号左边那个确定的数字)

当从 f [ i − 1 ] [ 0 ] f[i-1][0] f[i−1][0]转移来时,形如a -1 -1 -1…c ,在c前面插入一个数字 b b b变成 f [ i ] [ 0 ] f[i][0] f[i][0]

形如a -1 -1 -1 … b c,此时 b b b有 k − 2 k-2 k−2种取值

当从 f [ i − 1 ] [ 1 ] f[i-1][1] f[i−1][1]转移来时,形如a -1 -1 -1 … a.在最右边插入最右端的数字 b b b(已经被确定)变成a -1 -1 -1 … a b

那么倒数第一个问号只能取 a a a

f [ i ] [ 0 ] = f [ i − 1 ] [ 0 ] ∗ ( k − 2 ) + f [ i − 1 ] [ 1 ] f[i][0]=f[i-1][0]*(k-2)+f[i-1][1] f[i][0]=f[i−1][0]∗(k−2)+f[i−1][1]

f [ i ] [ 1 ] f[i][1] f[i][1]表示两端问号相等的方案

此时 f [ i − 1 ] [ 0 ] f[i-1][0] f[i−1][0]形如a -1 -1 -1… b

考虑在最右边添上一个 a a a变成a -1 -1 -1… b a就变成了 f [ i ] [ 1 ] f[i][1] f[i][1]的方案

f [ i ] [ 1 ] = f [ i − 1 ] [ 0 ] ∗ ( k − 1 ) f[i][1]=f[i-1][0]*(k-1) f[i][1]=f[i−1][0]∗(k−1)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5+10;
const int mod = 998244353;
int n,k,a[maxn],b[maxn],f[maxn][2];
int quick(int x,int n)

	int ans = 1;
	for( ; n ; n>>=1,x=x*x%mod )
		if( n&1 )	ans = ans*x%mod;
	return ans;

int solve(int a[],int n )

	if( !n )	return 1;
	int l = 1, r = n, ans = 0;
	while( l<=n && a[l]==-1 )	l++;
	while( r>=1 && a[r]==-1 )	r--;
	if( l>n )	return quick( k-1,n-1 )*k%mod;
	ans = quick( k-1,l-1 )*quick( k-1,n-r )%mod;
	int las = l;
	for(int i=l+1;i<=r;i++)
	
		if( a[i]==-1 )	continue;
		else
		
			ans = ans*f[i-las-1][a[las]==a[i]]%mod;
			las = i;
		
		
	return ans;

signed main()

	cin >> n >> k;
	f[0][0] = 1, f[0][1] = 0;
	for(int i=1;i<=n;i++)
	
		f[i][1] = f[i-1][0]*(k-1)%mod;
		f[i][0] = ( f[i-1][0]*(k-2)+f[i-1][1] )%mod;
	
//	cout << f[2][0] << " --- " << f[2][1] << endl;
	for(int i=1;i<=n;i++)
	
		int x; cin >> x;
		if( i&1 )	a[++a[0]] = x;
		else	b[++b[0]] = x;
	
	cout << solve( a,a[0] )*solve( b,b[0] )%mod;

cf1140cplaylist(优先队列)(代码片段)

LINK每首歌形存成一个形如ti,bi\\t_i,b_i\\ti​,bi​的pairpairpair,按照bib_ibi​的大小进行小到大排序考虑现在我们枚举bnb_nbn​作为最小的好听程度,显然只有第nnn首歌满足条件接下来我们枚举bn−1b_n-1bn−1​作为最小的好听程度,显然[n... 查看详情

cf1140epalindrome-lessarrays(代码片段)

(DP)没有长度为奇数的回文串，必定满足没有长度为(3)的回文串我们要避免(x,y,x)的情况即(a[i]≠a[i+2])根据这一规律，我们把序列拆成下标分别为奇数和偶数的两个序列分别处理可以发现，一段(-1)的区间的可能性只与其两端的数是... 查看详情

cf1140epalindrome-lessarrays(巧妙的递推)(代码片段)

LINK题意一个数组有些位置是???,你可以使用[1,k][1,k][1,k]填充满足最后对于i∈[1,n−2]i\\in[1,n-2]i∈[1,n−2]有ai!=ai+2a_i!=a_i+2ai​!=ai+2​,求方案数我们分成奇数索引构成的数组和偶数索引构成的数组分别考虑现在设奇... 查看详情

cf1140epalindrome-lessarrays(巧妙的递推)(代码片段)

LINK题意一个数组有些位置是???,你可以使用[1,k][1,k][1,k]填充满足最后对于i∈[1,n−2]i\\in[1,n-2]i∈[1,n−2]有ai!=ai+2a_i!=a_i+2ai​!=ai+2​,求方案数我们分成奇数索引构成的数组和偶数索引构成的数组分别考虑现在设奇... 查看详情

cf1140fextendingsetofpoints(代码片段)

题目链接题目大意：每次给你一个点，如果这个点已经存在，那么就删除这个点，如果这个点不存在，那么就加入这个点。每次询问当前集合的扩展集合中点的个数。扩展集合是这么得到的，如果当前集合中存在矩形的3个点，... 查看详情

codeforces1140f线段树分治并查集

题意及思路：https://blog.csdn.net/u013534123/article/details/89010251之前cf有一个和这个相似的题，不过那个题只有合并操作，没有删除操作，直接并查集搞一搞就行了。对于这个题，因为有删除操作，我们对操作序列建一颗线段树，记录... 查看详情

luogu1140相似基因

链接：https://www.luogu.org/problem/P1140思路：设$f[i][j]$表示第一个串前$i$位与第二个串前$j$位匹配后的最大值。可以将第$i$位与第$j$位直接匹配，或者分别用一个原字母匹配另一个空格。代码：#include<bits/stdc++.h>constintb[6][6]={{0,0,0... 查看详情

MySQL #1140 - GROUP 列的混合

】MySQL#1140-GROUP列的混合【英文标题】：MySQL#1140-MixingofGROUPcolumns【发布时间】：2009-08-0711:07:01【问题描述】：您好，想知道是否有人可以对以下错误有所了解。sql在本地工作正常，但我远程收到以下错误。SQL查询：SELECTCOUNT(node.ni... 查看详情

xdoj_1140_kmp

http://acm.xidian.edu.cn/problem.php?id=1140 KMP效率真心低，cstring中的strstr快多了。 #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;intm 查看详情

语法错误或访问冲突：1140 GROUP 列混合 laravel

】语法错误或访问冲突：1140GROUP列混合laravel【英文标题】：Syntaxerrororaccessviolation:1140MixingofGROUPcolumnslaravel【发布时间】：2018-09-2513:58:29【问题描述】：我已经写了这个带有分页的查询$items=Item::select(\'items.*\',\'sub_category_name\',\'cat... 查看详情

lightoj1140howmanyzeroes?(代码片段)

Jimmywritesdownthedecimalrepresentationsofallnaturalnumbersbetweenandincluding m and n,(m≤n).Howmanyzeroeswillhewritedown?InputInputstartswithaninteger T(≤11000),denotingthenumbero 查看详情

xidianoj1140寻找万神

--正文直接用strstr就过了....#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>usingnamespacestd;charstr[10000000];charstr2[10000000];intmain( 查看详情

lightoj1140_数位dp

题目链接：http://lightoj.com/volume_showproblem.php?problem=1140给出区间[m,n]，求区间内的所有数共有多少个0。 设dp[i][j]表示处理到第i位时，它前面共有j个0（除了前导零）。注意：前导01#include<algorithm>2#include<iostream>3#include<... 查看详情

[暑假集训--数位dp]lightoj1140howmanyzeroes?

Jimmywritesdownthedecimalrepresentationsofallnaturalnumbersbetweenandincludingmandn,(m≤n).Howmanyzeroeswillhewritedown?InputInputstartswithanintegerT(≤11000),denotingthenumberoftestcases.Eachcaseconta 查看详情

hrbust1140

.../acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=11402、题目Description定义一种操作为：已知一个数字，对其各位数字反复求和，直到剩下的数是一位数不能求和为止。例如：数字2345，第一次求和得到2+3+4+5=14，再对14的各... 查看详情

1140:零起点学算法47——求平均值

1140:零起点学算法47——求平均值TimeLimit:1Sec  MemoryLimit:64MB  64bitIOFormat:%lldSubmitted:1408  Accepted:873[Submit][Status][WebBoard]Description输入一些整数，求平均值 Input多组测试数据首先输入1个 查看详情

p1140相似基因

P1140相似基因题目背景大家都知道，基因可以看作一个碱基对序列。它包含了4种核苷酸，简记作A,C,G,T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。在一个人类基因工作组的任务中，生物学家研究的... 查看详情

jobdu1140八皇后

题目1140：八皇后时间限制：1秒内存限制：32兆特殊判题：否提交：1064解决：665题目描述：会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8*8个方格），使它们谁... 查看详情