luoguU50590 数字

我们可有用DP很快地求出用x个数字构成y的方案数

f[i][j]=f[i-1][m-a[k]]

其中a()为数字集合S中的数。

主要难点在于题目中条件3：前后和相等或奇偶和相等。考虑容斥。

我们可以很快地求出前后和相等+奇偶和相等的方案数，再减去既是前后和相等又是奇偶和相等的方案数即可。

我们已知用x个数字构成y的方案数，如何快速求前后和相等的方案数？

前后和相等时，这个数字可以表示为【 A 】【 B 】，由两端长度为n的数字构成，且他们的和相等。

首先显然要枚举前后和，假设为i。则A有f(n,i)种取法，B也有f(n,i)种取法，因此前后和相等且为i的方案数为\(sqr(f(n,i))\)

对于所有的前后和，答案为\(\sum sqr(f[n][i])\)

如何快速求奇偶和相等的方案数？

脑补把上文的A和B的每个数字穿插。新构成的数就是A1B1A2B2A3B3...AnBn，这时新构成的数奇偶和相等。

因此方案数和前后和相等的方案数相等，为\(\sum sqr(f[n][i])\)

如何快速求奇偶和相等且前后和相等的方案数？

考虑一个数x我们可以把它分成【A】【B】前后长度各位n的两部分，记A0为A中偶数位的和，A1为A中奇数位的和，B0为B中偶数位的和，B1为B中奇数位的和。

要使得前后和相等且奇偶和相等，则

A0+A1=B0+B1
A0+B0=A1+B1

解得

A0=B1
A1=B0

分别求出A0=B1 A1=B0的对数，相乘即为答案。

下文中A0 A1 B0 B1分别表示处于这些位置的数字的个数，而非处于这些位置的数字的和

如果n是偶数，例如n=4

位数	1	2	3	4	5	6	7	8
奇偶	1	0	1	0	1	0	1	0
属于	A1	A0	A1	A0	B1	B0	B1	B0

A0=2 A1=2 B0=2 B1=2

重复答案：\(\sum (f[A0][i]·f[B1][i])·\sum (f[A1][i]·f[B0][i])=\sum (f[2][i]·f[2][i])·\sum (f[2][i]·f[2][i])\)

如果n是奇数，例如n=5

位数	1	2	3	4	5	6	7	8	9	10
奇偶	1	0	1	0	1	0	1	0	1	0
属于	A1	A0	A1	A0	A1	B0	B1	B0	B1	B0

A0=2 A1=3 B0=3 B1=2

重复答案：\(\sum ( f[A0][i] · f[B1][i] ) · \sum ( f[A1][i] · f[B0][i] ) = \sum ( f[2][i] · f[2][i] ) · \sum ( f[3][i] · f[3][i] )\)

可以发现\(A0=B1<=A1=B0\)

设\(t1=A0=B1，t2=A1=B0\)，则重复的答案为\(\sum sqr(f[t1][i]) · \sum sqr(f[t2][i])\)

容斥一下，最终答案为

\(2·\sum sqr(f[n][i])-\sum sqr(f[t1][i]) · \sum sqr(f[t2][i])\)

code

#include<bits/stdc++.h>
#define ll long long
#define mo 999983
#define md(a) (((a)%mo+mo)%mo)
#define md2(a) ((a)%mo)
#define N 1010
#define SUM 9010
#define sqr(a) ((a)*(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define fsb(a,b,c) for(ll a=b;a<=(c);a++)
#define fbs(a,b,c) for(ll a=b;a>=(c);a--)
using namespace std;
ll n,vis[20],a[20],m=0,f[N][SUM],mx=0,maxx=0,ans=0,sum1=0,sum2=0;
char s[20];
template<typename qw>inline void rll(qw &x){
 x=0;qw f=1;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
int main(){
 freopen("num.in","r",stdin);freopen("num.out","w",stdout);
// ll T=clock();
 rll(n);scanf("%s",s+1);s[0]='!';
 fbs(i,strlen(s)-1,1)
  if(vis[s[i]-'0']==0){
   vis[s[i]-'0']=1;a[++m]=s[i]-'0';maxx=max(maxx,a[m]);
  }
 f[0][0]=1;
 fsb(i,1,n){
  fsb(j,1,m)
   fbs(k,mx+a[j],a[j])
    f[i][k]=md2(f[i][k]+f[i-1][k-a[j]]);
  mx+=maxx;
 }
// fsb(i,0,mx)printf("%10d %d\n",i,f[n][i]);
// printf("%d\n",clock()-T);
 ll t1=n/2,t2=n-t1;
 fsb(i,0,mx){
  ans=md2(ans+md2(2*sqr(f[n][i])));
  sum1=md2(sum1+md2(sqr(f[t1][i])));
  sum2=md2(sum2+md2(sqr(f[t2][i])));
 }
 printf("%lld\n",md(ans-md2(sum1*sum2)));
 return 0;
}

code

Social