AtCoder Regular Contest 077

Maybe it’s because of my recent internship, maybe not (then why do you say it)… Maybe it’s just because I’m lazy… I’ve done very few questions recently, but it feels like… I’ve reached some critical periods again (…), so I still need to do it, and then I find that my low IQ seems to have been cleared recently…

I have been thinking about questions E and F for a long time this time. I particularly like AtCoder’s messy questions because… I often can’t do it… (spreads hands and smiles bitterly)

Title link

C - pushpush

Given a sequence $a_i$, the sequence $b$ is obtained after $n$ operations.

1. The content of each operation is to put $a_i$ behind the current sequence $b$.

2.Reverse the current b sequence.

Find the $b$ sequence after $n$ operations.

Find the pattern, one left and one right.

int n;
int val[maxn];
int ans[maxn];
 
void solve()
{
	sa(n);
	repp(i,1,n)
	{
		sa(val[i]);
	}
	int left=1;
	int right=n;
	int cnt=n;
	repp(i,1,n)
	{
		if(i&1)
		{
			ans[left]=val[cnt];
			left++;
		}
		else
		{
			ans[right]=val[cnt];
			right--;
		}
		cnt--;
	}
	repp(i,1,n)
	{
		if(i>1)printf(" ");
		printf("%d", ans[i]);
	}
	puts("");
}

D-11

Given the number of $n+1$, $1$ to $n$ will appear at least $1$ times, and $1$ will appear $2$ times. Ask how many subsequences from $1$ to $n$ are extracted from this sequence.

Number of combinations, minus duplicates. The repeated part is $i-1$ that appear one after another. This part is considered repeated.

int n;
int val[maxn];
ll fac[maxn],inv[maxn];
ll ans[maxn];
 
ll C(ll x,ll y)
{
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
 
void init()
{
	fac[0]=1;
	inv[0]=1;
	repp(i,1,200005)
	{
		fac[i]=fac[i-1]*i%mod;
		inv[i]=po(fac[i],mod-2,mod);
	}
}
 
map<int,int>hax;
void solve()
{
	sa(n);
	n++;
	int st=0,en=n;
	repp(i,1,n)
	{
		sa(val[i]);
		if(hax.count(val[i]))
		{
			st=hax[val[i]];
			en=i;
		}
		hax[val[i]]=i;
	}
	//DE(st)
	//DE(en)
	repp(i,1,n)
	{
		ans[i]=C(n,i);
	}
	ll left = st-1;
	ll right = n-en;
	//DE(left)
	//DE(right)
	repp(i,1,n)
	{
		if(i-1>right+left)
		{
			printf("%lld\n", ans[i]);
			continue;
		}
		ans[i]=ans[i]-C(left+right,i-1);
		ans[i]=(ans[i]%mod+mod)%mod;
		printf("%lld\n",ans[i]);
	}
}

E - guruguru

There is a lamp with various levels of brightness. Under normal circumstances, you can press the forward button and the brightness will continue to +1. After reaching n, the brightness will become 1. Now you can set a favorite button and press f to jump directly to the brightness you set.

Now there is a brightness sequence that asks how many times you need to press the favorite button at least when you set it to n options.

This question is fun. . .

If $val[i]>val[i-1]$, then assuming that your $f$ value is on the line segment $val[i-1]$ to $val[i]$, then $f-val[i]-1$ times will be reduced. Use two arrays to maintain this value, one to maintain $-val[i]-1$, and one to maintain $+f$ (just $+1$, and finally $*i$ will be fine). If $val[i]<val[i-1]$, the same applies.

In fact, it seems better to use a line segment tree, but it is not as easy to write as this. . .

int n,m;
ll val[maxn],b[maxn],c[maxn];
ll ans;
 
void solve()
{
	ans=0;
	scanf("%d%d",&n,&m);
	repp(i,1,n)
	{
		scanf("%lld",&val[i]);
	}
	repp(i,2,n)
	{
		if(val[i-1]<val[i])
		{
			ans+=val[i]-val[i-1];
			
			b[val[i-1]+1]+=val[i-1]+1;
			b[val[i]+1]-=val[i-1]+1;
			++c[val[i-1]+1];
			--c[val[i]+1];
		}
		else
		{
			ans += m+val[i]-val[i-1];
 
			b[1]-=m-val[i-1]-1;
			b[val[i]+1]+=m-val[i-1]-1;
			b[val[i-1]+1]+=val[i-1]+1;
 
			c[1]++;
			c[val[i]+1]--;
			c[val[i-1]+1]++;
		}
	}
	for(int i=1;i<=m;i++)
	{
		b[i]+=b[i-1];
		c[i]+=c[i-1];
	}
	ll cnt=0;
	for(int i=1;i<=m;i++)
	{
		cnt=max(cnt,1LL*i*c[i]-b[i]);
 
	}
	//DE(cnt)
	printf("%lld\n", ans-cnt);
}

F-SS

There is an even sequence SS, now add at least one character after it, or in the form of SS, add the minimum number of characters. If you keep adding like this, a sequence of infinite length will be formed. Given left and right, ask the number of each letter during this period.

Assume that S is in the form of XTX. The first k characters are equal to the last k characters, which is the X, and the rest is T.

So what is the minimum number to add? You will find that it is like this, XTXXTX|TXXT, that is, TXXT is the number of characters to be added. How many characters are there? Calculate it is 2*(n-k). In this way, according to the meaning of the question, we only focus on the first half, g(S)=SG, where S=XTX and G=XT.

Then now you have XTXXTXTXXT, how many more will you add in the next operation, XTXXTXTXXT|XXTXTX, now g(SG)=SGS.

By following this recursion, we find that it is the Fibonacci of strings. . . Good God. . .

char val[maxn];
ll le, ri;
 
int len, prod;
ll pre[maxn][30];
int nxt[maxn];
 
ll fib(ll n, ll x)
{
	if (n <= len) {
		return pre[n][x];
	}
	if (n <= 2 * len) {
		return pre[len][x] + pre[n - len][x];
	}
	ll ans1 = pre[len][x] + pre[prod][x];
	ll ans2 = pre[len][x];
	ll a = len + prod;
	ll b = len;
 
	while (n > a + b)
	{
		ll tmp = ans1;
		ans1 += ans2;
		ans2 = tmp;
 
		tmp = a;
		a += b;
		b = tmp;
	}
	return ans1 + fib(n - a, x);
}
 
ll cal(ll n, ll x)
{
	if (n <= len)return pre[n][x];
	if (len%prod == 0)
	{
		ll res = 1LL * (n - len) / prod*pre[prod][x] + pre[len][x];
		n -= len;
		n %= prod;
		return res + pre[n][x];
	}
	else
	{
		return fib(n, x);
	}
}
 
void solve()
{
	memset(pre, 0, sizeof(pre));
	scanf("%s", val + 1);
 
	len = strlen(val + 1);
	len /= 2;
 
	nxt[0] = -1;
	int k = -1;
	for (int i = 0; i < len;)
	{
		if (k == -1 || val[k + 1] == val[i + 1])
		{
			k++;
			i++;
			nxt[i] = k;
		}
		else
		{
			k = nxt[k];
		}
	}
	prod = len - nxt[len];
 
	repp(i, 1, len)
	{
		for (int k = 0; k < 26; k++)
		{
			pre[i][k] = pre[i - 1][k];
		}
		pre[i][val[i] - 'a']++;
	}
	scanf("%lld%lld", &le, &ri);
 
	rep(k, 0, 26)
	{
		printf("%lld ", cal(ri, k) - cal(le - 1, k));
	}
}