Educational Codeforces Round 62 (Rated for Div. 2) - E.Palindrome-less Arrays(dp)

제목 대의: 열을 하나 드리겠습니다. 이 열은 -1 또는 1~k의 수로 구성되어 있습니다. -1의 위치가 확정되지 않았으니 1~k의 수를 그 안에 기입할 수 있습니다.이 열에 회문열을 포함하지 않도록 몇 가지 작성 방안이 있느냐고 물었다
 
사고방식: 이 문제를 볼 때 dp인 것 같았는데 오랫동안 풀지 못했다(요리 울음).cf 공식 문제풀이를 보고 문득 깨달았다.
우선 길이가 3인 열이 회문열이 아니라면 이 길이가 3인 열을 포함하는 긴 열은 회문열이 아니라는 것을 알아야 한다(이것은 이해하기 쉽다)
그래서 우리는 길이가 3인 회문열만 없애면 된다.관찰을 통해 아래에 기수로 표시된 숫자와 아래에 짝수로 표시된 숫자는 서로 영향을 주지 않기 때문에 이 수열을 기수열과 짝수열로 나눌 수 있다. 마지막 답안은 두 답안의 곱셈이다
우리는 모든 문자(i곳) 뒤에 있는 첫 번째 숫자가 -1이 아닌 숫자를 찾아내서 Nx[i]로 기록해야 한다. 만약에 뒤에 모두 -1이 있다면 Nx[i]=n(n은 수열 길이이다. 여기에 아래 표시가 1부터 시작하고 내 코드는 0부터 시작한다고 가정한다)
dp[i][0/1]를 연속된 i개-1의 양쪽 수가 -1의 열이 아니라 양쪽의 수가 같다(1) 또는 같지 않다(0)로 구성된 방안수로 설정하다
예를 들어 3-1-12는 dp[3][0]이고 4-1-14는 dp[2]이다[1]
이 문제는 주로 다음과 같은 몇 가지 상황으로 나뉜다(아래의 x대표-1)
1.xxxxxxxx(총 i - 1)
한 개의 문자열은 모두 -1로 구성되어 있다.
방안수 = k*dp[i-2][1]+k*k-1*dp[i-2][0]
또는 k*pow(k-1, i-1)
2.axxxxxx(총 i개-1)
즉 이 꼬리의 한쪽은 -1이고, 다른 한쪽은 -1이 아니다.
방안수 = dp[i-1][1]+k-1*dp[i-1][0]
또는 Pow(k-1, i)
3.xxxxxxx (총 i - 1)
동상
4.axxxxxxxb(i개-1)
여기서 i가 홀수인지 짝수인지 구분해야 돼요.
i는 홀수:
dp[i][1]=dp[i/2][1]*dp[i/2][1])+k-1*dp[i/2][0]*dp[i/2][0] dp[i][0]=2*dp[i/2][1]*dp[i/2][0]+(k-2)*dp[i/2][0]*dp[i/2][0]
i 는 짝수:
dp[i][1]=(k-1)*dp[i-1][0] dp[i][0]=dp[i-1][1]+(k-2)*dp[i-1][0]
이 문제는 여기까지 하면 기본적으로 완성된다. 다음은 각 단락의 결과를 위의 이 공식들로 구하고 그들을 곱하면 된다. 한 걸음 한 걸음 연산할 때마다 모범을 보여야 한다는 것을 잊지 마라
제목 대의: 열을 하나 드리겠습니다. 이 열은 -1 또는 1~k의 수로 구성되어 있습니다. -1의 위치가 확정되지 않았으니 1~k의 수를 그 안에 기입할 수 있습니다.이 열에 회문열을 포함하지 않도록 몇 가지 작성 방안이 있느냐고 물었다
 
사고방식: 이 문제를 볼 때 dp인 것 같았는데 오랫동안 풀지 못했다(요리 울음).cf 공식 문제풀이를 보고 문득 깨달았다.
우선 길이가 3인 열이 회문열이 아니라면 이 길이가 3인 열을 포함하는 긴 열은 회문열이 아니라는 것을 알아야 한다(이것은 이해하기 쉽다)
그래서 우리는 길이가 3인 회문열만 없애면 된다.관찰을 통해 아래에 기수로 표시된 숫자와 아래에 짝수로 표시된 숫자는 서로 영향을 주지 않기 때문에 이 수열을 기수열과 짝수열로 나눌 수 있다. 마지막 답안은 두 답안의 곱셈이다
우리는 모든 문자(i곳) 뒤에 있는 첫 번째 숫자가 -1이 아닌 숫자를 찾아내서 Nx[i]로 기록해야 한다. 만약에 뒤에 모두 -1이 있다면 Nx[i]=n(n은 수열 길이이다. 여기에 아래 표시가 1부터 시작하고 내 코드는 0부터 시작한다고 가정한다)
dp[i][0/1]를 연속된 i개-1의 양쪽 수가 -1의 열이 아니라 양쪽의 수가 같다(1) 또는 같지 않다(0)로 구성된 방안수로 설정하다
예를 들어 3-1-12는 dp[3][0]이고 4-1-14는 dp[2]이다[1]
이 문제는 주로 다음과 같은 몇 가지 상황으로 나뉜다(아래의 x대표-1)
1.xxxxxxxx(총 i - 1)
한 개의 문자열은 모두 -1로 구성되어 있다.
방안수 = k*dp[i-2][1]+k*k-1*dp[i-2][0]
또는 k*pow(k-1, i-1)
2.axxxxxx(총 i개-1)
즉 이 꼬리의 한쪽은 -1이고, 다른 한쪽은 -1이 아니다.
방안수 = dp[i-1][1]+k-1*dp[i-1][0]
또는 Pow(k-1, i)
3.xxxxxxx (총 i - 1)
동상
4.axxxxxxxb(i개-1)
여기서 i가 홀수인지 짝수인지 구분해야 돼요.
i는 홀수:
dp[i][1]=dp[i/2][1]*dp[i/2][1])+k-1*dp[i/2][0]*dp[i/2][0] dp[i][0]=2*dp[i/2][1]*dp[i/2][0]+(k-2)*dp[i/2][0]*dp[i/2][0]
i 는 짝수:
dp[i][1]=(k-1)*dp[i-1][0] dp[i][0]=dp[i-1][1]+(k-2)*dp[i-1][0]
이 문제는 여기까지 하면 기본적으로 완성된다. 다음은 각 단락의 결과를 위의 이 공식들로 구하고 그들을 곱하면 된다. 한 걸음 한 걸음 연산할 때마다 모범을 보여야 한다는 것을 잊지 마라
 
코드:

#include
using namespace std;
typedef long long ll;
const ll MOD=998244353;
ll n,k;
ll a[200010];
ll Nxb[200010];
ll Nxc[200010];
ll dp[200010][2];
vector b;
vector c;
int lenb,lenc;
ll ansb,ansc;
ll Mul(ll a,ll b)
{
	return (a*b)%MOD;
}
ll powermod(ll x,ll n)
{
	ll res=1;
	while(n>0)
	{
		if(n&1)
		{
			res=(res*x)%MOD;
		}
		x=(x*x)%MOD;
		n>>=1;
	}
	return res;
}
void init()
{
	dp[0][1]=0;
	dp[0][0]=1;
	for(int i=1;i<200010;i++)
	{
		if(i%2==1)
		{
			dp[i][1]=(Mul(dp[i/2][1],dp[i/2][1])+Mul(k-1,Mul(dp[i/2][0],dp[i/2][0])))%MOD;
			dp[i][0]=(Mul(Mul(2,dp[i/2][1]),dp[i/2][0])+Mul(k-2,Mul(dp[i/2][0],dp[i/2][0])))%MOD;
		}
		else
		{
			dp[i][1]=Mul(k-1,dp[i-1][0]);
			dp[i][0]=(dp[i-1][1]+Mul(k-2,dp[i-1][0]))%MOD;
		}
	}
}
ll cal(int s,int e,vector &v)
{
	int len;
	if(s==e)
	{
		if(v[s]==-1)
		return k;
		else
	    return 1;	
	}
	if(v[s]==-1&&v[e]==-1)
	{		
	    len=e-s+1;
		return (Mul(k,dp[len-2][1])+Mul(Mul(k,k-1),dp[len-2][0]))%MOD;
//        return Mul(k,powermod(k-1,len-1));
	}
	if(v[s]==-1&&v[e]!=-1)
	{
		len=e-s;
		return (dp[len-1][1]+Mul(k-1,dp[len-1][0]))%MOD;
//        return powermod(k-1,len);
	}
	if(v[s]!=-1&&v[e]==-1)
	{
		len=e-s;
		return (dp[len-1][1]+Mul(k-1,dp[len-1][0]))%MOD;
//        return powermod(k-1,len);
	}
	if(v[s]!=-1&&v[e]!=-1)
	{
		 len=e-s-1;
		 if(v[s]==v[e])
		 return dp[len][1];
		 else
		 return dp[len][0];
	}
}
void solveb()
{
	int u=0;
	int ls=0;
	ansb=1;
	if(b.size()==1)
	{
		if(b[0]==-1)
		ansb=k;
		else
	    ansb=1;
	}
	while(u<=lenb-1)
	{
		if(u==lenb-1&&u==Nxb[u])
		break;
		ls=Nxb[u];
		ansb=Mul(ansb,cal(u,ls,b));
		u=ls;
	}
}
void solvec()
{
	int u=0;
	int ls=0;
	ansc=1;
	if(c.size()==1)
	{
		if(c[0]==-1)
		ansc=k;
		else
	    ansc=1;
	}
	while(u<=lenc-1)
	{
		if(u==lenc-1&&u==Nxc[u])
		break;
		ls=Nxc[u];
		ansc=Mul(ansc,cal(u,ls,c));
		u=ls;
	}
}
int main()
{
	cin >> n >> k;
	init();
	for(int i=1;i<=n;i++)
	cin >> a[i];
	for(int i=1;i<=n;i+=2)
	b.push_back(a[i]);
	for(int i=2;i<=n;i+=2)
	c.push_back(a[i]);
	lenb=b.size();
	lenc=c.size();
	for(int i=lenb-1;i>=0;i--)
	{
		if(i+1>lenb-1)
		Nxb[i]=lenb-1;
		else
		{
			if(b[i+1]==-1)
			{
				Nxb[i]=Nxb[i+1];
			}
			else
			{
				Nxb[i]=i+1;
			}
		}
	}
	for(int i=lenc-1;i>=0;i--)
	{
		if(i+1>lenc-1)
		Nxc[i]=lenc-1;
		else
		{
			if(c[i+1]==-1)
			{
				Nxc[i]=Nxc[i+1];
			}
			else
			{
				Nxc[i]=i+1;
			}
		}
	}
	solveb();
	solvec();
//	cout << ansb << " "<