CC

题目链接:点我

题意:

给你a + b 和 a * b 让你计算 $ a ^{n}$ + $ b ^{n}$

题目链接:点我

题目

题意:

给你一个矩阵 A, 让你求 A + $A^{2}$ + $A^{3}$ + $A^{4}$ + $A^{5}$ + … $A^{n}$,

思路:

矩阵倍增,那么怎么倍增呢, 令矩阵 S = A + $A^{2}$ + $A^{3}$ + $A^{4}$ + $A^{5}$ + … $A^{n}$ = A + $A^{2}$ + $A^{3}$ + $A^{4}$ + $A^{5}$ + $A^{n /2 }$ + $ A^{n/2}$ * ( A + $A^{2}$ + $A^{3}$ + $A^{4}$ + $A^{5}$ + … $A^{n/2} $)
于是,我们这样不断的重复下去,就能算出答案了.

题目链接:点我

题目

题意:

求f(n) mod m 的值,

思路:

类似与求斐波那契数列(Fibonacci)数列的第n项那样,快速幂即可.
构造递推矩阵为:$ \begin{pmatrix} 1 & 1 \ 1 & 0\end{pmatrix}$

题目链接:点我

题意:

给定一列数，每个数对应一个变换，变换为原先数列一些位置相加起来的和，问r次变换后的序列是多少.

题目链接:点我

题目

One day, Alice and Bob felt bored again, Bob knows Alice is a girl who loves math and is just learning something about matrix, so he decided to make a crazy problem for her.
Bob has a six-faced dice which has numbers 0, 1, 2, 3, 4 and 5 on each face. At first, he will choose a number N (4 <= N <= 1000), and for N times, he keeps throwing his dice for K times (2 <=K <= 6) and writes down its number on the top face to make an N*K matrix A, in which each element is not less than 0 and not

题目链接:点我

题目

 Read the program below carefully then answer the question.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>

const int MAX=100000*2;
const int INF=1e9;

int main()
{
  int n,m,ans,i;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    ans=0;
    for(i=1;i<=n;i++)
    {
      if(i&1)ans=(ans*2+1)%m;
      else ans=ans*2%m;
    }
    printf("%d\n",ans);
  }
  return 0;
}

题目链接:点我

题目

In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 … in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333… (it means a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333…) Besides, in 233 matrix, we got a i,j = a i-1,j +a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,…,a n,0, could you tell me a n,m in the 233 matrix?

题目链接:点我

题目

Jzzhu has invented a kind of sequences, they meet the following property:

You are given x and y, please calculate fn modulo 1000000007 (1e9 + 7).

题目链接:点我

题意:

实际上就是问有多少人可以在开始位置S之前到达终点.

思路:

逆向bfs,记录从终点开始到每个点的距离,然后找出所有的距离比起点离终点小的点,把他们的人数加起来即可.

题目链接:点我

题目

There is a long plate s containing n digits. Iahub wants to delete some digits (possibly none, but he is not allowed to delete all the digits) to form his "magic number" on the plate, a number that is divisible by 5. Note that, the resulting number may contain leading zeros.