企业型网站制作,北京网站建设产品介绍,福州市建设局职改办门户网站,移动手机号码网站正题 题目大意
求有多少个2∗n2*n2∗n位的数字(允许有前导零)满足
只包含SSS集合内的数字前nnn位的和等于后nnn位之和或者奇数位之和和偶数位之和相等 解题思路
预处理数组fi,jf_{i,j}fi,j表示iii位数#xff0c;数字之和为jjj时的方案数。 动态转移方程 fi,j∑k1mfi,j−…正题 题目大意
求有多少个2∗n2*n2∗n位的数字(允许有前导零)满足
只包含SSS集合内的数字前nnn位的和等于后nnn位之和或者奇数位之和和偶数位之和相等 解题思路
预处理数组fi,jf_{i,j}fi,j表示iii位数数字之和为jjj时的方案数。 动态转移方程 fi,j∑k1mfi,j−akf_{i,j}\sum_{k1}^mf_{i,j-a_k}fi,jk1∑mfi,j−ak
然后我们若不考虑两种情况重合答案就是 2∗∑i1n(fn,i)22*\sum_{i1}^n(f_{n,i})^22∗i1∑n(fn,i)2
那我们考虑重合那么就是奇数位等于偶数位之和且前nnn位等于后nnn位之和的情况。我们可以转换为: 前nnn位中奇数位之和后nnn位中偶数位之和 且 前nnn位中偶数位之和后nnn位中奇数位之和
这种情况就是 (∑i1n(fn/2,i)2)∗(∑i1n(fn−n/2,i)2)(\sum_{i1}^n(f_{n/2,i})^2)*(\sum_{i1}^n(f_{n-n/2,i})^2)(i1∑n(fn/2,i)2)∗(i1∑n(fn−n/2,i)2) 最终答案 (2∗∑i1n(fn,i)2)−(∑i1n(fn/2,i)2)∗(∑i1n(fn−n/2,i)2)(2*\sum_{i1}^n(f_{n,i})^2)-(\sum_{i1}^n(f_{n/2,i})^2)*(\sum_{i1}^n(f_{n-n/2,i})^2)(2∗i1∑n(fn,i)2)−(i1∑n(fn/2,i)2)∗(i1∑n(fn−n/2,i)2) codecodecode
#pragma GCC optimize(2)
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1010,XJQ999983;
ll n,f[N][N*10],Z,ans,m,a[12];
char s[12];
ll C(int x)
{ll ans0;for(int i0;ix*9;i)if(f[x][i])ans(ans(f[x][i]*f[x][i]))%XJQ;return ans;
}
int main()
{scanf(%lld,n);scanf(%s,s1);//double starclock();mstrlen(s1);for(ll i1;im;i)a[i]s[i]-0;Z9*n;f[0][0]1;for(ll i0;in;i)for(ll j0;jZ;j)if(f[i][j])for(ll k1;km;k)f[i1][ja[k]](f[i1][ja[k]]f[i][j])%XJQ;printf(%lld,(2*C(n)%XJQ-C(n/2)*C(n-n/2)%XJQXJQ)%XJQ);
}
