题解：P12975 疯狂星期四

首先想到 dp。

设

f_{i,j}

表示从

1

到

i

的格子里数的和，对

7

取余余数为

j

。

转移应为

f_{i,j}=f_{i-1,j}+\sum_{k=0}^6{f_{i-1,k}}

，可以理解为后面的一部分是第

i

格填

0

到

6

，前面是填

7

。

时间复杂度

O(n)

，可惜

n

太大，似乎无法优化。

发现对于相同的

i

来说，后面的求和是相同的，只有前面一部分影响

i

相同的

f_{i,j}

的值。当

i=1

时，不难发现

f_{1,0}=2

，而

f_{1,1}=f_{1,2}=…=f_{i,6}=1

。

所以，对于任意的

i

，就都有

f_{i,0}=f_{i,1}+1=…=f_{i,6}+1

。

又因为总共有

8^n

种方案，就有

f_{n,0}+6 \times (f_{n,0}-1)=8^n

，解得

f_{n,0}=\frac {8^n+6}{7}

。

101

是质数，由费马小定理得

8^n \equiv8^{n\bmod100} \pmod {101}

，然后在处理逆元计算。

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=101;
int ksm(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int n;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	char c;
	while(cin>>c)
		n=(n*10+(c-'0'))%100;
	cout<<(ksm(8,n)+6)%mod*ksm(7,mod-2)%mod;
	return 0;	
}

题解：P12975 疯狂星期四

文章操作

相关推荐

评论

题解：P12975 疯狂星期四