Good bye 2018,Hello 2019------C题------个人题解
题目
Lele now is thinking about a simple function f(x).
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
输入
The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
输出
For each case, output f(k) % m in one line.
范例输入
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
范例输出
45
104
思路:
看到复杂的递推公式,第一反应就是暴力!(然后先是MLE又是WA…)
那么,只能用矩阵快速幂来做了emmmm…
0~9肯定是不用担心的,所以只要考虑10或以上的数字就好了。
问题在于,如何构造一个像样的矩阵呢?先看看递推公式:
F(x)=x——(x<10)
F(x)=a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)
似乎是要我们输入10个参数啊,这么复杂还是别做了吧…
(教练持刀赶来中…)
不过,尽管参数比较多,但是输入进来就不会变了,只不过是输入了进行快速幂的矩阵的10个参数而已。
有了矩阵,输入参数,进行快速幂,步步取模(为了不让数据溢出),那么问题就迎刃而解了。
我构造的矩阵:
通过这样的矩阵运算,计算F(10)需要快速幂1次,F(11)需要快速幂2次…
因此F(n)需要快速幂n-9次。
AC代码:
#include<iostream>
#include<cstring>
#define ffor(i, a, b) for(int i = a; i <= b; i++)
#define rfor(i, a, b) for(int i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define ll long long
using namespace std;
ll m;//求模用的m,步步求模所以开全局
struct Tab//结构体,11*11矩阵
{
ll tab[11][11];
};
ll mfpow(ll a, ll b)//矩阵快速幂
{
a %= m;
ll res = 1;
while (b)
{
if (b % 2)
res = res * a%m;
a = a * a%m;
b >>= 1;
}
return res;
}
Tab x_cal(Tab a,Tab b)//矩阵乘法
{
Tab res;
mes(res.tab, 0);
ffor(i, 1, 10)
ffor(k,1,10)
ffor(j, 1, 10)
{
res.tab[i][k] += a.tab[i][j] * b.tab[j][k];
res.tab[i][k] %= m;
}
return res;
}
Tab x_fpow(Tab a, ll b)//矩阵快速幂{
Tab res;
memset(res.tab, 0, sizeof(res.tab));
for (int i = 1; i <= 10; i++)
res.tab[i][i] = 1;
while (b)
{
if (b % 2)
res = x_cal(res, a);
a = x_cal(a, a);
b >>= 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long n;
int tab[11];
while (cin >> n >> m)
{
mes(tab, 0);
Tab a;//用来做快速幂的矩阵
mes(a.tab, 0);
rfor(i, 10, 1)//输入最后一行
cin >> a.tab[10][i];
ffor(i, 1, 9)
a.tab[i][i + 1] = 1;//对角线初始化为1
if (n < 10)
cout << n % m << endl;//小于10就直接计算输出
else
{
Tab res = x_fpow(a, n-9);
ll r = 0;
ffor(i, 1, 9)//1~9分别乘最后一行的2~10个元素并求模,就是最终答案。
{
r += i * res.tab[10][i+1];
r %= m;
}
cout << r << endl;
}
}
return 0;
}