摩天楼
摩天楼
题目描述
奶牛公司打算建造一栋摩天楼，共有B层。现在已经建好了第一层，第一层有N个房间，这N个房间从左往右排成一行，第i个房间的号码是A[i]，其中1<=A[i]<=9。为了节约成本，公司复制了第一层，然后在第一层上方粘贴了B-1次，这样就能快速完工。由于是复制粘贴的，所以这B层楼完全相同。
FJ对数字很着迷，于是它从第1层楼选择某个房间的号码，再从第2层楼选择某个房间的号码.....最后从第B层楼选择某个房间的号码。FJ把这B个数字从左往右排成一行，就构成了一个大整数，不妨设该整数是X。
请问有FJ有多少种不同的选取方案，使得X % Y = Z。其中Y和Z是输入数据给定的。
由于合法要求的方案数太多，你只需要输出模1000000007结果。
输入格式 2217.in
第一行，四个整数：N，B，Z，Y。
2 <= N <= 50000，1 <= B <= 10^9，0 <= Z < Y<=100， Y >= 2。
第二行，N个整数，第i个整数是A[i]。 1 <= A[i] <=9。
输出格式 2217.out
一个整数。
输入样例 2217.in
输入样例一：
12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5
输入样例二：
3 2 1 2
6 2 2
输入样例三：
3 2 1 2
3 1 2
输出样例 2217.out
输出样例一：
3
输出样例二：
0
输出样例三：
6
题目大意：
有B层楼，每层楼有同样的N个数，求在每层楼中取一个数组成一个大的数x，%y后为z的方案数。
样例三解释：
组成的大楼为：
3 1 2
3 1 2
6方案分别为：33 31 13 11 2321，这些数被%2都为1。
爆搜（10%）:
好吧，就是dfs每一层取什么。由于层数B一直达到10的九次方，所以很容易就会爆掉。
DP（40%）:
f[i][j]表示，在第i层，此时余数为j，的方案数。
枚举层数i，枚举上一层余数j，枚举这次要选的数k(1~9)。并且k要存在。
状态转移方程为：
f[i ][ (j*10+k)%y ]+=f[ i ][ j ]*num[k]。
时间复杂度为O（b*y*a[i]）
正解 矩阵乘法优化(100%) :
矩阵乘法的具体概念详见矩阵乘法解析总结。
这一个神奇的矩阵是由机智的wyy推出来的。大家可以去看看她的博客可能会比我讲得更清楚。
http://my.csdn.net/littlewyy
当前的第0层的矩阵f[1，0, 0, 0, 0] 表示f[0][0]，f[0][1]，f[0][2]……f[0][y]的值。（先假设y为5，而只有k=1是存在的）
当前的余数i，加上1~9(k)的某个数，都会变成一个固定的目标值：（i*10+k）%y。
举个例子：假设余数为0，加上1，y为10那么目标值则是1，那么下一层余数为1的矩阵则要变为
f[1, 1， 0, 0, 0]。
而这个矩阵是前一个矩阵乘上“？”得来的呢？因为第一层的第1列（列的编号为0~y-1），要从“？”矩阵的第1列得来。
而前一个矩阵中对应的第0列要，乘“？”矩阵第0行的数，才能达到第一层的矩阵。至于为什么，详见矩阵的性质。
这样两个条件一结合，便是第0行第1列（而把例子转换成文字，则是第 余数 行，第 目标 列）。
我觉得还是好难理解的，如样例三中的“?”矩阵是
1 1 2
1 1 2
第0行第0列表示，有1种使余数为0，下一层还是余数为0的可能，第1行第0列，有一种余数为1变为余数为0的可能。
算了，好像很难解释，迷死了，我昨天想了15分钟以上才想清楚，我理解能力有问题？？好吧，感觉矩阵乘法和容斥原理都是很迷很迷的东西。
得出这个固定的转换矩阵以后，就用类似于快速幂的东西。
但是，不知道为什么快速幂里面会炸掉。
于是问题就来了：
我们发现，在函数里面递归大概5、6层，便会爆空间，交上去只有40分，剩下的全部爆掉。一开始问jt老师，他说可能是因为只分给函数一定的空间，因此定义局部变量很容易炸掉，把它们改成全局变量应该就不会了。
结果还是爆。Zd帮我们把结构体里面的long long改成了int，再在矩阵乘法的计算中，再临时地把矩阵的类型*1LL，然后就AC了。
代码如下：
#include
#include
using namespace std;
const int maxy=105,mod=1000000007;
int n,b,z,y,aa;
long long num[15];
struct henmi
{
int a[maxy][maxy];
}news,ans,nans,ok;
void init()
{
ok.a[0][0]=1;
for(int i=0;i>n>>b>>z>>y;
for(int i=1;i<=n;i++)
{
cin>>aa;
num[aa]++;
}
init();
ans=run(b);
nans=juzhen(ok,run(b));
cout<让我们特别疑惑的是，明明在函数里面没有开任何一个结构
体，也没有开任何一点空间，可是为什么会爆呢？就连jt老师也表示没有遇到过这样的情况。
后来推测估计是因为在快速幂中把矩阵传入矩阵乘法时，会自动预留一个备份空间，然后就会炸掉。
所以，如果把传入这个结构体，改成引用，即本来传入id[c+1]改成传入c+1，就不会炸了。
#include
#include
using namespace std;
const int maxy=105,mod=1000000007;
int n,b,z,y,aa,ceng;
long long num[15];
struct henmi
{
long long a[maxy][maxy];
}news,ans,now,nans,ok,id[35];
void init()
{
ok.a[0][0]=1;
for(int i=0;i>n>>b>>z>>y;
for(int i=1;i<=n;i++)
{
cin>>aa;
num[aa]++;
}
init();
id[0]=news;
run(b,1);
id[ceng+1]=ok;
nans=juzhen(ceng+1,1);
cout<
文章最后发布于: 2017-08-18 10:44:36
相关阅读
A5创业网（公众号：iadmin5）1月15日报道，近日北京监狱与支付宝合作，上线了服刑人员综合账务管理系统，为服刑人员提供了狱内支付、家属存款
营销QQ是拥有10万好友容量的一个企业版QQ，可以每天发出1000次好友邀请，但是很多用户在购买使用之后，发现并不能达到1000次邀请量，经常
浅谈setInterval(aa,1000)与setInterval(aa(),1000)的
一直有个疑惑，在定时器上调用某个方法时，加括号和不加括号有什么区别。今天做了个实验，发现，不加括号定时器会每秒执行一次，加了括号只
图片来源图虫：已授站长之家使用声明：本文来自于微信公众号运营研究社公众号(ID：U_quan)，作者：陈维贤，授权站长之家转载发布。文章整理自
与E1000E和E1000相比，VMXNET3的网络性能更好。本文将解释虚拟网络适配器和第2部分之间的区别，并将演示通过选择半虚拟化适配器可以