给出n个人的id，有两个门，每个门有一个标号a个b，现在我们要将n个人分成两组，进入两个门中，，使得两部分人的标号的和（迭代的求，直至变成一位数）分别等于a和b，问有多少种分法，也可全进入其中的一扇门
一个数的数字根只和它之后的值有关，只要类似背包就能完成人员分配的计算。
注意处理全从a出或者全从b出的情况
#include "stdio.h"#include "string.h"const int mod=258280327;int x[100010],dp[100010][20];int main(){int t,a,k,b,n,key;scanf("%d",&t);while (t–){scanf("%d%d%d",&n,&a,&b);key=0;for(int i=1;i<=n;i++){scanf("%d",&x[i]);key=(key+x[i])%9;}memset(dp,0,sizeof(dp));dp[0][0]=1;//dp[1][x[1]]=1;for(int i=1;i<=n;i++){for(int j=0;j<=9;j++){k=(x[i]+j)%9;dp[i][j]+=dp[i-1][j];dp[i][k]+=dp[i-1][j];dp[i][j]%=mod;dp[i][k]%=mod;}}int ans=0;k=(a+b)%9;a%=9;b%=9;if(k==key){ans+=dp[n][a];if(a==key)ans–;if (a==0) ans–;}a%=9;b%=9;if(a==key)ans++;if(b==key)ans++;printf("%d\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
绊住的不仅是双脚，还有未来。
