[HDU4990] 等比公式+取模运算公式 或矩阵求递推法~

2019-04-13 14:29发布

站内文章 / 模拟电子
10554 0 997

Reading comprehension

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 384    Accepted Submission(s): 185


Problem Description Read the program below carefully then answer the question.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include

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 ",ans);
  }
  return 0;
}  
Input Multi test cases，each line will contain two integers n and m. Process to end of file.
[Technical Specification]
1<=n, m <= 1000000000  
Output For each case，output an integer，represents the output of above program.  
Sample Input 1 10 3 100  
Sample Output 1 5  
Source BestCoder Round #8  
Recommend heyang   |   We have carefully selected several similar problems for you:  4992 4988 4987 4984 4983 
打个表，递推公式 a[n]=a[n-1]+2*a[n-2]+1 建立矩阵 [a[n-1],a[n-2],1]*[1,1,0]                                               [2,0,0]                                               [1,0,1] 【a[2],a[1],1】* 后面矩阵的 n-2次幂 n=1,2的时候特判就行 注意爆int #define DeBUG #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std ; #define zero {0} #define INF 0x3f3f3f3f #define EPS 1e-6 #define TRUE true #define FALSE false typedef long long LL; const double PI = acos(-1.0); //#pragma comment(linker, "/STACK:102400000,102400000") inline int sgn(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1); } #define N 100005 const int MAXN = 5; long long mod; struct Matrix { long long mat[MAXN][MAXN]; void Zero() { memset(mat, 0, sizeof(mat)); } void Unit() { memset(mat, 0, sizeof(mat)); for (int i = 0; i < MAXN; i++) mat[i][i] = 1; } void output() { for (int i = 0; i < MAXN; i++) { for (int j = 0; j < MAXN; j++) { printf("%d ", mat[i][j]); } printf(" "); } } }; Matrix operator*(Matrix &a, Matrix &b) { Matrix tmp; tmp.Zero(); for (int k = 0; k < MAXN; k++) { for (int i = 0; i < MAXN; i++) { if (!a.mat[i][k]) continue; for (int j = 0; j < MAXN; j++) { tmp.mat[i][j] += a.mat[i][k] * b.mat[k][j] % mod; if ( tmp.mat[i][j] >= mod) tmp.mat[i][j] -= mod; } } } return tmp; } Matrix operator ^(Matrix a, int k) { Matrix tmp; tmp.Unit(); if(k<=1) return a; for (; k; k >>= 1) { if (k & 1) tmp = tmp * a; a = a * a; } return tmp; } int main() { #ifdef DeBUGs freopen("C:\Users\Sky\Desktop\1.in", "r", stdin); #endif Matrix mt; long long n,m; while (scanf("%I64d%I64d", &n, &m) + 1) { mod=m; if(n==1) { printf("%I64d ", 1%m); continue; } else if(n==2) { printf("%I64d ", 2%m); continue; } mt.Zero(); mt.mat[0][0] = 1; mt.mat[0][1] = 1; mt.mat[1][0] = 2; mt.mat[2][0] = 1; mt.mat[2][2] = 1; mt = mt ^ (n-2); Matrix mt2; mt2.Zero(); mt2.mat[0][0] = 2; mt2.mat[0][1] = 1; mt2.mat[0][2] = 1; Matrix ans = mt2 * mt; printf("%I64d ", ans.mat[0][0]); } return 0; }

推公式，公式看程序就懂了，两个等比数列其实 关键求(4^dm -1)/3 %mod 利用公式a/b%m = a%(b*m)/b注意这时候再取模是%（b*m）快速幂的时候得变了，因为这个逗B了。。。 #define DeBUG #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std ; #define zero {0} #define INF 0x3f3f3f3f #define EPS 1e-6 #define TRUE true #define FALSE false typedef long long LL; const double PI = acos(-1.0); //#pragma comment(linker, "/STACK:102400000,102400000") inline int sgn(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1); } #define N 100005 long long MOD; LL pow2(LL a, LL b, LL mod) { LL r = 1, base = a; while (b != 0) { if (b % 2) r = r * base % mod; base = base * base % mod; b /= 2; } return r; } int main() { #ifdef DeBUGs freopen("C:\Users\Sky\Desktop\1.in", "r", stdin); #endif long long n, m; while (scanf("%I64d%I64d", &n, &m) + 1) { MOD = m; int dm; if (n & 1) dm = (n - 1) / 2 + 1; else dm = (n - 2) / 2 + 1; long long ans = (pow2(4, dm, (3 * MOD)) - 1) % (3 * MOD) / 3; if (n % 2 == 0) { ans = (ans * 2) % MOD; } printf("%I64d ", ans); } return 0; }

热门文章