Fortnight Round 1 题解

ECEG · 2025-08-21 15:04:30 · 题解

T1

题意

有 a,b 两个正整数。

你需要进行 +\infty 次操作，每次操作为 a\gets a+b 或 b\gets a+b。

给出一个参数 n，在操作的过程中你应该时刻保证 a\not=n 且 b\not=n。

输出是否能完成所有操作。

数据范围：1\le T\le 10^5,0\le a,b,n\le 10^9。

题解

by XiaoShanYunPan。

首先要把 a=n 或 b=n 的情况特判掉。

感性上，我们觉得限制非常松，应该大部分情况都是有解的。

思考一下会发现，如果 a+b\gt n，那么我们一定能够经过两次操作令 a,b 均大于 n（先令 a\gets a+b，再令 b\gets a+b），此后怎么操作都一定合法。

而如果 a+b=n，无论怎么操作都会立马得到一个 n，所以一定无解。

剩下的问题是如果 a+b\lt n 怎么搞。

此时我们有结论：如果 a=b=x 且 3x=n 则无解，否则有解。

这个东西无解是显然的，我们的问题在于为什么剩下的情况一定有解。

首先，如果 a\not=b，第一步可以得到 (a,a+b) 或 (a+b,b)，这很关键。

接下来每次均对第一步未操作的那个位置操作，上述两个不同的状态一定只能有一个恰好到达 n。

为什么？注意到如果第一个状态经过若干次操作后得到 n，则 n=a+k(a+b)，同理第二个状态可得到 n=b+k(a+b)，由于 a\not=b，这俩式子显然只能成立一个。

那么接下来考虑 a=b，进行一次操作后就会直接转化为 a\not=b，所以第一次操作后除非直接撞上前面已有的无解状态 a+b=n，否则就一定有解。

直接根据上述讨论判断即可。

T2

题意

对于长度为 m 的二进制串 A,B 和长度为 m 的排列 P，我们定义 f(A,B,P)_i=A_{P_i}\oplus B_{P_i}，其中 \oplus 是按位异或运算。

现在给定 n 组串 S_i,T_i，求有多少组可能的 (X,P)，使得 T_i=f(S_i,X,P)。

答案对 10^9+7 取模。

数据范围：0\le n\le 20，1\le m\le 10^5。

题解

by XiaoShanYunPan。

考虑一个弱化问题，如果只有 P 没有 X 会怎样。

下面是这个问题的完整描述：

对于长度为 m 的二进制串 A 和长度为 m 的排列 P，我们定义 g(A,P)_i=A_{P_i}。

现在给定 n 组串 S_i,T_i，求有多少种可能的 P，使得 T_i=g(S_i,P)。

我们发现，如果 \forall i,S_{i,a}=T_{i,b}，则 P_a 可以为 b。

将其横竖倒置，令 S'_{i,j}=S_{j,i}，T' 同理，则当且仅当 S'_i=T'_j 时，P_i 可以为 j。

使用桶记录 S'_i 与 T'_i，如果数量相同则可以随意匹配，否则无解。

然后考虑加上 X，会发现其影响相当于将某个 S'_i 取反，我们只需要将 S 的反串视为和 S 相同，即可按照和上述一样的做法完成此题。

于是本题做完了，时间复杂度 \mathcal{O}(nm)，但空间复杂度是 \mathcal{O}(2^nm) 的。

如果 n 比较大，利用字符串 Hash 或一些其它方式实现桶即可，当然这没什么意思，所以本题没有这部分。

另外还要注意判断无解和 n=0 的情况，这都是简单的。

一个有趣的事实是我们特别在最后一个子任务中没有放入 n=0 的情况，如果你只考虑漏了这一种情况是有很高的部分分的，快谢谢良心出题人。

T3

题意

求 \sum\limits_{i=0}^{n}\sum\limits_{j=0}^{n}(i\oplus j)^4 对 998244353 取模的结果。

数据范围：n\lt 2^{10^6}。

题解

by ECEG。

特别鸣谢 TabEsc。

先将 n 加一，改为求 \sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}(i\oplus j)^4。

注意到：\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}(i\oplus j)^4=\sum\limits_{x=0}^{2n-2}x^4\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}[i\oplus j=x]，于是我们设 cnt_x=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}[i\oplus j=x]，接下来我们考虑 cnt。

注意到当 n=2^k 时，对于所有 x\in[0,n) 都有 cnt_x=n。那对于答案的贡献就很好算了。

这启发我们将 n 拆为许多长度为 2 的幂次的区间。

不妨设 n=2^{x_1}+2^{x_2}+\ldots+2^{x_k}，其中 x_1\gt x_2\gt\ldots\gt x_k。将第 i 段定义为 (\sum\limits^{i-1}_{j=0} 2^{x_j},\sum\limits_{j=0}^{i}2^{x_j})，其中第一段的左端点为 0。首先就有对于第 i 段，在这个段的每个数，他们的第 x_i 位只能取 0，且前 x_i 位完全相同（前是从高位开始数）。

先考虑自身段贡献，因为前 x_i 位完全相同，在异或下，可以全部当为 0，于是对 x\in[0,2^{x_i}) 的所有 cnt_x 贡献都是 2^{x_i}，那对于答案的贡献也不难算。

接下来考虑第 i 段和第 j 段，不妨假设 i\lt j。首先第 i 段是后 x_i 位随意取值（注意这里后是从低位 0 开始数的，也就是说并不包含第 x_i 位），第 j 段是后 x_j 位随意取值。

注意到对于一个 [0,2^p) 的排列异或上一个固定的 x\lt 2^p 得到的序列一定还是一个一个 [0,2^p) 的排列。我们这里先只管后 x_i 位，那第 i 段就相当于是一个 [0,2^{x_i}) 的排列，异或上 p+val（p\in[0,2^{x_j})，val 是第 i 段随便取但第 j 段已经确定的值），p+val 肯定小于 2^{x_i}。于是我们是得到了 2^{x_j} 个 [0,2^{x_i}] 的排列，那贡献就是对 [0,2^{x_i}) 的 cnt 都是 2^{x_j}。

但是这里，第 i 段的第 x_i 的值为 0，而第 j 段为 1，所以区间还需加上 x_i。而且我们上面钦定了 i\lt j，实际上反过来贡献是一样的，于是就是对 [2_{x_i},2_{x_i+1}) 的 cnt 是 2^{x_j+1}。

接下来就很简单了，用一个后缀和，就不需要枚举 j 了。总共复杂度为 O(\log n)。

其他

被猫猫偷走的提示是 \sum\limits_{i=1}^x=\frac{x^5}{5}+\frac{x^4}{2}+\frac{x^3}{3}-\frac{x}{30}。猫猫好坏，狠狠地敲猫猫的头喵喵喵喵喵！

代码

const int maxn=1e6+4,mod=998244353;int n,inv5,inv2,inv3,inv30,suf[maxn],pw[maxn],ans;char a[maxn],op[maxn];
int fast_pow(int x,int y,int res=1){for(;y;y>>=1,x=x*1ll*x%mod)if(y&1)res=res*1ll*x%mod;return res;}
int pw5(int x){return x*1ll*x%mod*x%mod*x%mod*x%mod*inv5%mod;}
int pw4(int x){return x*1ll*x%mod*x%mod*x%mod*inv2%mod;}
int pw3(int x){return x*1ll*x%mod*x%mod*inv3%mod;}
int sum(int x){return (((pw5(x)+pw4(x))%mod+pw3(x))%mod+mod-x*1ll*inv30%mod)%mod;}
signed main(){
    read(n);scanf("%s",op);
    inv5=fast_pow(5,mod-2);inv2=fast_pow(2,mod-2);inv3=fast_pow(3,mod-2);inv30=fast_pow(30,mod-2);
    int tmp=0;pw[0]=1;
    for(int i=0;i<n;++i)tmp+=(op[i]=='0');
    if(!tmp){
        n++;a[0]='1';
        for(int i=1;i<n;++i)a[i]='0';
    }
    else{
        for(int i=0;i<n;++i)a[i]=op[i];
        a[n-1]++;
        for(int i=n-1;i>=0;--i){
            if(a[i]>'1')a[i]='0',a[i-1]++;
            else break;
        }
    }
    for(int i=1;i<=n+2;++i)pw[i]=pw[i-1]*2ll%mod;
    for(int i=n-1;i>=0;--i){
        suf[i]=suf[i+1];
        if(a[i]=='1'){
            (ans+=(sum(pw[n-i]-1)-sum(pw[n-i-1]-1)+mod)%mod*1ll*suf[i]%mod)%=mod;
            (ans+=sum(pw[n-i-1]-1)*1ll*pw[n-i-1]%mod)%=mod;
            (suf[i]+=pw[n-i])%=mod;
        }
    }
    write(ans);
    return 0;
}

T4

题意

求有多少个长度为 2n 的排列的前 n 个数的乘积与后 n 个数的乘积之和为 k 的倍数，其中 1\le k\le 2n。

答案对 998244353 取模。

数据范围：1\le k\le 2n\le 2000。

题解

by Locix_Elaina_Celome，略有修改。

1\le k\le 2n\le 10

直接枚举全排列并检验。

时间复杂度 O(2n!)。

1\le k\le 2n\le 18

枚举每个数放在左边还是右边，然后检验。最后乘上一个排列数。

时间复杂度 O(2^{2n})。

1\le k\le 2n\le 50

发现这个问题可以转化为：把 1\sim 2n 分成两个集合，两个集合的乘积的和是 k 的倍数的方案数，最后再乘上 (n!)^2。

因为 k\le 2n，所以一定有一个集合的乘积是 k 的倍数，因为两边相加是 k 的倍数，所以两个集合都需要是 k 的倍数。

考虑一个 dp，设一个 dp_{i,j,x,y}，表示考虑前 i 个数，选了 j 个放在第一个集合，其余放在另一个集合，第一个集合乘积是 x，第二个集合乘积是 y。

但是发现这样复杂度 x 和 y 的范围炸了，考虑优化。

发现为 k 的倍数，意味着在模 k 意义下为 0。

那么就可以把上面的 dp 状态中的 x,y 对k取模，做 dp。

if(j)dp[i][j][x*i%k][y]=(dp[i][j][x*i%k][y]+dp[i-1][j-1][x][y])%P;
if(j<i)dp[i][j][x][y*i%k]=(dp[i][j][x][y*i%k]+dp[i-1][j][x][y])%P;

答案即为 dp_{2n,n,0,0}\times (n!)^2。

时间复杂度 O(n^2k^2)。

1\le k\le 2n\le 300

观察上面的dp，模意义不太帅气，因为有 O(k) 种情况。尝试从 k 的因数来考虑，因为 k 只有 O(\sqrt{k}) 个因数。

还是从最原始的 dp 思考，设一个 dp_{i,j,x,y}，表示考虑前 i 个数，选了 j 个放在前面，其余放在后面，前半段乘积是 x，后半段乘积是 y。

发现可以将 x,y 和 k 取 \gcd，这样状态就全都是 k 的因数。

于是就把上面的对 k 取模变为对 k 取 \gcd 就可以了。

因为 k 的因数个数是 O(\sqrt{k}) 的，所以整体复杂度 O(n^2k)。

1\le k\le 2n\le 2000

注意到 k\le 2n，所以可以钦定 k 放在其中一边。由于 1 \sim i 的遍历顺序不影响，所以可以视为先做 i=k，再做剩下的。

于是其中一个集合的乘积和 k 取 \gcd 一定是 k，所以可以省掉一维状态，也就是 dp_{i,j,x} 即可。

时间复杂度 O(n^2\sqrt n)。

更强一些

本题也许可以用生成函数等进一步优化，出题团队太懒了没搞，有大佬搞出来了踹我们一脚。