2021牛客OI赛前集训营-提高组（第七场）-（重现赛）赛后总结

注：买的去年的题，本地OI赛制，排名按当年的计算。

A.依依寺

为什么给的是 $1\le a,b,c\le 10^{7}1\backslash le\; a,b,c\; \backslash le\; 10^7$ 然而样例有 $0,0,00,0,0$ 。

1. 特判掉 $b=c=0b=c=0$ 的情况后发现 $aa$ 仅仅是用来调控先后手关系的。

2. 进一步的，我们只需要知道最多能拿多少个石子，按奇偶判断先手必胜或必败。

3. 那么就会有两种取石子方案：A.先手取 $11$ ，然后 $1,2,1,\mathrm{2...}1,2,1,2...$；B.先手取 $22$ ，然后 $2,1,2,\mathrm{1...}2,1,2,1...$。

判断下是否存在一种方案使先手必胜即可。

时间复杂度 $\mathcal{O}(T)\backslash mathcal\{O\}(T)$。

代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    cin>>T;
    long long a,b,c;
    while(T--)
    {
        scanf("%lld %lld %lld",&a,&b,&c);
        if(!b && !c)
        {
            printf("Second\n");
            continue;
        }
        int lst=a&1;
        int tmp1=(1+((b-1>c)?c*2+1:(b-1)*2))&1,tmp2=(1+((c-1>b)?b*2+1:(c-1)*2))&1;
        if((b && (lst+tmp1)&1) || (c && (lst+tmp2)&1)) printf("First\n");
        else printf("Second\n");
    }
    return 0;
}

B.武义寺

考场打的 $2^{n}2^n$ 的状压然而数组开小了痛失 $10pts10pts$。

这里讲下正解公式是什么意思，然后发现考场居然没有想到（悲）。

设该数列最早在 $ii$ 位置出现 $i>a[i]i>a[i]$，令 $k=n+1-ik=n+1-i$，枚举 $a_i=ja\_i=j$，则前 $i-1i-1$ 个数的可行的方案：

既然位置 $ii$ 已经填了 $jj$，对于 $j+1i-1j+1~i-1$ 是不影响的，考虑倒着选数，位置 $i-1i-1$ 能选 $k+1k+1$ 个数（它后面全部的数和它本身），位置 $i-2i-2$ 本来能选 $k+2k+2$ 个数，但已经被位置 $i-1i-1$ 选了一个，于是也只能选 $k+1k+1$ 个数。以此类推，到了位置 $jj$ 发现它不能选本身（因为已经被位置 $ii$ 选了），只能选 $kk$ 个，它前面的数也都只能选 $kk$ 个。

因此得到前 $i-1i-1$ 个数的可行的方案（最后一步自行用等比数列求和公式推导）：

${\sum }_{j=1}^{i-1}(k+1{)}^{i-j-1}{k}^j=(k+1{)}^{n-k}\times \frac{k}{k+1}\times {\sum }_{j=0}^{n-k-1}(\frac{k}{k+1}{)}^j=k\times [(k+1{)}^{n-k}-k^{n-k}]\backslash sum\backslash limits\_\{j=1\}^\{i-1\}(k+1)^\{i-j-1\}k^j=(k+1)^\{n-k\}\backslash times\; \backslash frac\{k\}\{k+1\}\backslash times\; \backslash sum\backslash limits\_\{j=0\}^\{n-k-1\}(\backslash frac\{k\}\{k+1\})^j=k\backslash times[(k+1)^\{n-k\}-k^\{n-k\}]$

答案即为：

$\frac{{\sum }_{k=1}^n(n-k+1)\times k!\times [(k+1{)}^{n-k}-k^{n-k}]+n+1}{n!}\backslash frac\{\backslash sum\backslash limits\_\{k=1\}^n(n-k+1)\backslash times\; k!\backslash times[(k+1)^\{n-k\}-k^\{n-k\}]\backslash \; +\backslash \; n+1\}\{n!\}$

最后要加上 $n+1n+1$ 的原因是当且仅当 $ii$ 与 $a_{i}a\_i$ 一一对应时，$val(p)=n+1val(p)=n+1$。

时间复杂度 $\mathcal{O}(n\log n)\backslash mathcal\{O\}(n\backslash log\; n)$。

代码：

#include<bits/stdc++.h>
using namespace std;

#define inv(x) quick_pow(x,MOD-2)
const int MAXN=1e6+5;
const int MOD=998244353;
int fac[MAXN];
int quick_pow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=(long long)ret*a%MOD;
		a=(long long)a*a%MOD,b>>=1;
	}
	return ret;
}
int main()
{
	int n;
	cin>>n;
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=(long long)fac[i-1]*i%MOD;
	int ans=0;
	for(int k=1;k<=n;++k) (ans+=(long long)(n-k+1)*fac[k]%MOD*(quick_pow(k+1,n-k)-quick_pow(k,n-k)+MOD)%MOD)%=MOD;
	(ans+=n+1)%=MOD;
    ans=(long long)ans*inv(fac[n])%MOD;
	cout<<ans;
	return 0;
}

C.依久依久

考场想到了正解但是没时间调了（考后花了5min就过了）

预处理发现在 $10^{18}10^\{18\}$ 以内的斐波那契数只有 $8686$ 个。

于是可以预处理出第 $ii$ 个斐波那契数 $fi{b}_{i}fib\_i$ 和 $11$ 到 $fi{b}_{i}fib\_i$ 的前缀异或和。

每次对询问的区间 $[l,r][l,r]$ 分块 $[l,fi{b}_L-1],[fi{b}_L,fi{b}_R],[fi{b}_R,r][l,fib\_L-1],[fib\_L,fib\_R],[fib\_R,r]$ 中间这段已知，旁边两段继续递归下去。

当 $[l,r][l,r]$ 间不存在斐波那契数时，设 $ff$ 为第一个小于 $ll$ 的斐波那契数，递归 $[l-f,r-f][l-f,r-f]$。

时间复杂度 $\mathcal{O}(T\log len)\backslash mathcal\{O\}(T\backslash log\; len)$。

代码：

#include<bits/stdc++.h>
using namespace std;

const int n=86;
long long fib[n+1],sum[n+1];
int tmp=0;
long long work(long long l,long long r)
{
    if(l>r) return 0;
    int L=lower_bound(fib+1,fib+n+1,l)-fib,R=upper_bound(fib+1,fib+n+1,r)-fib-1;
    if(L>R)
    {
        long long ret=((r-l+1)&1)?fib[R]:0;
        ret^=work(l-fib[R],r-fib[R]);
        return ret;
    }
    long long ret=sum[R]^sum[L]^fib[L];
    ret=ret^work(l,fib[L]-1)^work(fib[R]+1,r);
    return ret;
}
int main()
{
    fib[1]=1,fib[2]=2;
    for(int i=3;i<=n;++i) fib[i]=fib[i-1]+fib[i-2];
    sum[1]=1,sum[2]=3;
    for(int i=3;i<=n;++i)
    {
        sum[i]=sum[i-1]^sum[i-2]^fib[i-2]^fib[i];
        if((fib[i-2]-1)&1) sum[i]^=fib[i-1];
    }
    int T;
    cin>>T;
    long long l,r;
    while(T--)
    {
        scanf("%lld %lld",&l,&r);
        printf("%lld\n",work(l,r));
    }
    return 0;
}

D.补幺梨

一道披着完全背包外衣的同余最短路题目……

设 $k={}_{i=1}^n{a}_{i}k=\backslash min\backslash limits\_\{i=1\}^n\; a\_i$，则构建一个 $kk$ 个点的有向图。

跑完最短路后 $di{s}_{i}dis\_i$ 表示余数为 $ii$ (模 $kk$ 意义下)最小能得到的数。

答案即为 ${}_{i=1}^{k-1}di{s}_i-k\backslash max\backslash limits\_\{i=1\}^\{k-1\}dis\_i-k$。

时间复杂度 $\mathcal{O}(\min \{n,k{\}}^2\log \min \{n,k\})\backslash mathcal\{O\}(\backslash min\backslash \{n,k\backslash \}^2\backslash log\backslash min\backslash \{n,k\backslash \})$，最坏复杂度为 $\mathcal{O}(m\log \sqrt{m})\backslash mathcal\{O\}(m\backslash log\backslash sqrt\; m)$,足以通过此题。

//后记&总结：考场心态还是蛮关键的，T2数组开小挂了10分，T3想到了正解但由于紧张没打出来，最后只能拿30分遗憾离场……应当合理分配时间，把时间留给能过的题。

笔者能力有限，有未述详尽或有误之处，欢迎指正。