题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=1566

思路

n个球，第i个球颜色为ai，对于颜色j，对答案的贡献为颜色为j的球的个数的平方

k^2=(1+1+1+..+1)*(1+1++1+..+1)

for (i=1; i<=n; i++) for (j=1; j<=n; j++) if (a[i]==a[j]) ans++;

感觉看起来还是有一丝丝领悟的

转化为两个人分别同时做游戏

取出相同的方案

\(f[i][a][b]\)表示第i轮一个人上面去了a个，第二个上面取了b个

下面的可以算出来

就可以dp了

难在转化上，转移还蛮简单的

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1007,mod=1024523;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int n,m,f[2][N][N];

char a[N],b[N];

inline int add(int a) {return a>=mod?a-mod:a;}

int main() {

	// freopen("1.in","r",stdin);

	n=read(),m=read();

	scanf("%s%s",a+1,b+1);

	f[0][0][0]=1;

	int cnt=1;

	for(int k=1;k<=n+m;++k,cnt^=1) { // 第i轮

		for(int i=0;i<=min(n,k);++i) { // 第一人 的 上面已经使用过的珠子的个数

			int j=k-i;// 第一人 的 下面已经使用过的珠子的个数

			for(int x=0;x<=min(n,k);++x) { //第二人 的 上面已经使用过的珠子的个数

				int y=k-x;//第二人 的 下面已经使用过的珠子的个数

				f[cnt][i][x]=0;

				if(a[i]==a[x]&&i-1>=0&&x-1>=0)

					f[cnt][i][x]=add(f[cnt][i][x]+f[cnt^1][i-1][x-1]);

				if(b[j]==b[y])

					f[cnt][i][x]=add(f[cnt][i][x]+f[cnt^1][i][x]);

				if(a[i]==b[y]&&i-1>=0)

					f[cnt][i][x]=add(f[cnt][i][x]+f[cnt^1][i-1][x]);

				if(b[j]==a[x]&&x-1>=0)

					f[cnt][i][x]=add(f[cnt][i][x]+f[cnt^1][i][x-1]);

			}

		}

	}

	// for(int i=1;i<=n+m;++i) {

	// 	cout<<i<<"\n";

	// 	for(int j=1;j<=i;++j) {

	// 		for(int k=1;k<=i;++k) {

	// 			cout<<f[i][j][k]<<" ";

	// 		}

	// 		cout<<"\n";

	// 	}

	// 	puts("");

	// }

	printf("%d\n",f[cnt^1][n][n]);

	return 0;

}