「BZOJ2326」[HNOI2011] 数学作业

2014年4月28日7,2505

Description

题解

(F[n]) (10^k 1 1 )(F[n-1])

( n )=( 0 1 1 )( n-1 )

( 1 ) ( 0 0 1 )( 1 )

然后分段矩阵乘法

0-9,10-99…10^k-n

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
ll n,m;
ll a[4][4],b[4][4];
ll mul(ll x,ll y)
{
	ll s=0;
	while(y)
	{
		if(y&1)s=(s+x)%m;
		x=(x<<1)%m;
		y>>=1;
	}
	return s;
}
void mmul(ll a[4][4],ll b[4][4],ll s[4][4])
{
	ll tmp[4][4];
	for(int i=1;i<=3;i++)
	   for(int j=1;j<=3;j++)
	   {
	   	  tmp[i][j]=0;
	      for(int k=1;k<=3;k++)
	         tmp[i][j]=(tmp[i][j]+mul(a[i][k],b[k][j]))%m;
	     }
    for(int i=1;i<=3;i++)
       for(int j=1;j<=3;j++)
          s[i][j]=tmp[i][j];
}
void cal(ll t,ll last)
{
	memset(b,0,sizeof(b));
	b[1][1]=t;
    b[2][1]=b[2][2]=b[3][1]=b[3][2]=b[3][3]=1;
    ll y=last-t/10+1;
    while(y)
    {
    	if(y&1)mmul(a,b,a);
    	mmul(b,b,b);
    	y>>=1;
    }
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=3;i++)a[i][i]=1;
	ll t=10;
	while(n>=t)
	{
		cal(t,t-1);
		t*=10;
	}
	cal(t,n);
	printf("%lld",a[3][1]);
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

#include<cstdio>

#include<iostream>

#include<cstring>

#define ll long long

using namespace std;

ll n,m;

ll a[4][4],b[4][4];

ll mul(ll x,ll y)

{

ll s=0;

while(y)

{

if(y&1)s=(s+x)%m;

x=(x<<1)%m;

y>>=1;

}

return s;

}

void mmul(ll a[4][4],ll b[4][4],ll s[4][4])

{

ll tmp[4][4];

for(int i=1;i<=3;i++)

for(int j=1;j<=3;j++)

{

tmp[i][j]=0;

for(int k=1;k<=3;k++)

tmp[i][j]=(tmp[i][j]+mul(a[i][k],b[k][j]))%m;

}

for(int i=1;i<=3;i++)

for(int j=1;j<=3;j++)

s[i][j]=tmp[i][j];

}

void cal(ll t,ll last)

{

memset(b,0,sizeof(b));

b[1][1]=t;

b[2][1]=b[2][2]=b[3][1]=b[3][2]=b[3][3]=1;

ll y=last-t/10+1;

while(y)

{

if(y&1)mmul(a,b,a);

mmul(b,b,b);

y>>=1;

}

}

int main()

{

scanf("%lld%lld",&n,&m);

for(int i=1;i<=3;i++)a[i][i]=1;

ll t=10;

while(n>=t)

{

cal(t,t-1);

t*=10;

}

cal(t,n);

printf("%lld",a[3][1]);

return 0;

}

« 「BZOJ1677」[Usaco2005 Jan] Sumsets 求和「BZOJ1207」[HNOI2004] 打鼹鼠 »

Subscribe

WT

巨大确定是
(F ) (10^k 1 1 )(F[n-1])

( n )=( 0 1 1 )( n-1 )

( 1 ) ( 0 0 1 )( 1 )
不是
(F ) (10^k 1 0 )(F[n-1])

( n )=( 0 1 1 )( n-1 )

( 1 ) ( 0 0 1 )( 1 )
吗？

hu

为何这里要用慢速乘捏..既然Mod的数<=10^9，那么相乘应该不会超过longlong啊？

我不知道我当时怎么想的。。。

第二个样例就爆long long了啊。。

Flandre·Scarlet

慢速乘是啥