urn str sin cep java accep can man
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6076 Accepted Submission(s): 2643
题目大意:给定长度 L,由 m、f 组成的队列,如果是 fmf、fff 则是 E 队列,问长为 L 的队列中最多有多少 E 队列(mod K)
解题思路:前几个例子不难发现 F5 = F1+F3+F4。所以可以得出如下关系:
1 0 1 1 F1 F5
1 0 0 0 F2 F1
* =
0 1 0 0 F3 F2
0 0 1 0 F4 F3
所以就是计算初始矩阵 a 的 l 次幂最后 mod k 即可
代码:
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- int n,mod;
- struct matrix
- {
- long long m[4][4];
- matrix operator*(const matrix& a)const
- {
- matrix temp;
- for(int i=0;i<4;i++)
- {
- for(int j=0;j<4;j++)
- {
- temp.m[i][j] = 0;
- for(int k=0;k<4;k++)
- {
- temp.m[i][j] += m[i][k]*a.m[k][j]%mod;
- temp.m[i][j] %= mod;
- }
- }
- }
- return temp;
- }
- };
- int ks(matrix &a)
- {
- if(n<=3)
- return (2*n)%mod;
- if(n==4)
- return 9%mod;
- n -= 4;
- matrix ans;
- memset(ans.m,0,sizeof(ans));
- for(int i=0;i<4;i++)
- {
- ans.m[i][i] = 1;
- }
- while(n)
- {
- if(n%2)
- ans = ans*a;
- a = a*a;
- n /= 2;
- }
- int sum=0;
- sum+=ans.m[0][0]*9%mod;
- sum+=ans.m[0][1]*6%mod;
- sum+=ans.m[0][2]*4%mod;
- sum+=ans.m[0][3]*2%mod;
- sum %= mod;
- return sum;
- }
- int main()
- {
- matrix a;
- while(scanf("%d %d",&n,&mod)!=EOF)
- {
- memset(a.m,0,sizeof(a.m));
- a.m[0][0] = a.m[0][2] = a.m[0][3] = 1;
- a.m[1][0] = a.m[2][1] = a.m[3][2] = 1;
- printf("%d\n",ks(a));
- }
- }
HDU-2604 Queuing(矩阵快速幂)
来源: http://www.bubuko.com/infodetail-2269998.html