题解贴

此贴陆续发布题解

B. Mortis

原题是ICPC2024成都区域赛的B题，可能有人已经发现了，赛时没做出来（痛失牌子）...

由题n小，q大，鉴定为打表题，其余部分为线性dp，要记录前一个字符判断合法情况，注意到朴素做法是O(n⁴)无法通过，故考虑前缀和优化，最终时间复杂度为O(n³+q)。

这里放一下官方题解

(S=a,M=b,O=c)

代码如下：

#include<bits/stdc++.h>
#define ioss ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define int long long
using namespace std;
const int mod=1e9+7;
int n;
int ans[155][155][155],sum[155][155][155];
int dp[305][155][155][3];
string s;

inline void f() {
    if (s[0]!='?') {
        if (s[0]=='S')
            dp[0][1][0][0]=1;
        if (s[0]=='M')
            dp[0][0][1][1]=1;
        if (s[0]=='O')
            dp[0][0][0][2]=1;
    }
    else {
        dp[0][1][0][0]=dp[0][0][1][1]=dp[0][0][0][2]=1;
    }
    for (int x=1;x<n;++x) {
        for (int i=0;i<=150;++i) {
            for (int j=0;j<=150;++j) {
                if (s[x]!='?') {
                    if (s[x]=='S') {
                        if (i>0)
                            dp[x][i][j][0]=dp[x-1][i-1][j][1]+dp[x-1][i-1][j][2];
                    }
                    if (s[x]=='M') {
                        if (j>0)
                            dp[x][i][j][1]=dp[x-1][i][j-1][0]+dp[x-1][i][j-1][2];
                    }
                    if (s[x]=='O') {
                        dp[x][i][j][2]=dp[x-1][i][j][0]+dp[x-1][i][j][1];
                    }
                }
                else {
                    if (s[x-1]=='S') {
                        if (j>0)
                            dp[x][i][j][1]+=dp[x-1][i][j-1][0];
                        dp[x][i][j][2]+=dp[x-1][i][j][0];
                    }
                    if (s[x-1]=='M') {
                        if (i>0)
                            dp[x][i][j][0]+=dp[x-1][i-1][j][1];
                        dp[x][i][j][2]+=dp[x-1][i][j][1];
                    }
                    if (s[x-1]=='O') {
                        if (i>0)
                            dp[x][i][j][0]+=dp[x-1][i-1][j][2];
                        if (j>0)
                            dp[x][i][j][1]+=dp[x-1][i][j-1][2];
                    }
                    if (s[x-1]=='?') {
                        if (i>0)
                            dp[x][i][j][0]+=dp[x-1][i-1][j][1]+dp[x-1][i-1][j][2];
                        if (j>0)
                            dp[x][i][j][1]+=dp[x-1][i][j-1][0]+dp[x-1][i][j-1][2];
                        dp[x][i][j][2]+=dp[x-1][i][j][0]+dp[x-1][i][j][1];
                    }
                }
                dp[x][i][j][0]%=mod;
                dp[x][i][j][1]%=mod;
                dp[x][i][j][2]%=mod;
            }
        }
    }
    for (int i=0;i<=150;++i) {
        for (int j=0;j<=150&&i+j<=n;++j) {
            ans[i][j][n-i-j]=(dp[n-1][i][j][0]+dp[n-1][i][j][1]+dp[n-1][i][j][2])%mod;
        }
    }
    for (int i=0;i<=150;++i) {
        for (int j=0;j<=150;++j) {
            for (int k=0;k<=150;++k) {
                sum[i][j][k]=((sum[i][j][k-1]+sum[i][j-1][k]+sum[i-1][j][k]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1]+ans[i][j][k])%mod+mod)%mod;
            }
        }
    }
}

signed main() {
	ioss
    int q,x,y,z,c0,c1,c2;
    cin>>n>>q;
    cin>>s;
    c0=c1=c2=0;
    for (int i=0;i<n;++i) {
        if (s[i]=='S')
            ++c0;
        if (s[i]=='M')
            ++c1;
        if (s[i]=='O')
            ++c2;
    }
    f();
    while (q--) {
        cin>>x>>y>>z;
        x+=c0;
        y+=c1;
        z+=c2;
        if (x>150)
            x=150;
        if (y>150)
            y=150;
        if (z>150)
            z=150;
        cout<<sum[x][y][z]<<'\n';
    }
    return 0;
}

D. Amoris

原题是ICPC2024成都区域赛的G题，可能有人已经发现了，当时只有我们队在场，我做这题时就觉得是一道不错的题，不是很难，但是逻辑很清晰，所以这次选用了这题作为赛题的数学担当，欢迎讨论。

思路如下：

代码如下：

#include<bits/stdc++.h>
#define int long long
#define ioss ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int n;
int a[100005];
set<int> q;
signed main() {
	ioss
	cin>>n;
	for (int i=1;i<=n;++i) {
		cin>>a[i];
	}
	for (int i=2;i<=n;++i) {
		int x=a[i-1];
		int y=a[i];
		int x1=x^y;
		int x2=x&x1;
		int x3=y|x1;
		int x4=x^x2;
		int x5=x2^x1;
		int x6=x2&x4;
		q.insert(x);
		q.insert(y);
		q.insert(x1);
		q.insert(x2);
		q.insert(x3);
		q.insert(x4);
		q.insert(x5);
		q.insert(x6);
	}
	cout<<q.size()<<'\n';
	return 0;
}