codevs 5964 [SDOI2017]序列计数

时间:2021-05-24 11:57:16

codevs 5964 [SDOI2017]序列计数

 [题解]

官方题解就两句话。

codevs 5964 [SDOI2017]序列计数

写了三个版本的不同分值代码。看代码吧。

前导1

//f[i][j][1/0]表示长为i,sum mod p=j,是否已经选了质数的方案数
#include<cstdio>
using namespace std;
const int mod=;
const int N=1e6+;
int tot,prime[N/];bool check[N];
int n,m,f[][N][];int p;
void pre(){
n=1e6;check[]=check[]=;
for(int i=;i<=n;i++){
if(!check[i]) prime[++tot]=i;
for(int j=;j<=tot&&i*prime[j]<=n;j++){
check[i*prime[j]]=;
if(!(i%prime[j])) break;
}
}
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
pre();
scanf("%d%d%d",&n,&m,&p);
for(int i=;i<=m;i++) f[][i%p][!check[i]]++;
for(int i=,val;i<n;i++){
for(int j=;j<p;j++){
for(int k=;k<=m;k++){
val=(j+k)%p;
if(!check[k]){
f[i+&][val][]=(f[i+&][val][]+f[i&][j][]+f[i&][j][])%mod;
}
else{
f[i+&][val][]=(f[i+&][val][]+f[i&][j][])%mod,
f[i+&][val][]=(f[i+&][val][]+f[i&][j][])%mod;
}
}
}
for(int j=;j<p;j++){
f[i&][j][]=;
f[i&][j][]=;
}
}
printf("%d",f[n&][][]);
return ;
}

前导2

#include<cstdio>
using namespace std;
const int mod=;
const int N=1e6+;
int tot,prime[N/];bool check[N];
int n,m,p;
int f[][N];
int g[][N];
int sz[N];
void pre(){
n=1e6;check[]=check[]=;
for(int i=;i<=n;i++){
if(!check[i]) prime[++tot]=i;
for(int j=;j<=tot&&i*prime[j]<=n;j++){
check[i*prime[j]]=;
if(!(i%prime[j])) break;
}
}
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
pre();
scanf("%d%d%d",&n,&m,&p);
//全集
for(int k=;k<=p;k++) sz[k]=m/p+(m%p>=k);sz[]=sz[p];
for(int i=;i<p;i++) f[][i]=sz[i];
for(int i=,val;i<n;i++){
for(int j=;j<p;j++){
for(int k=;k<p;k++){
val=(j+k)%p;
f[i+&][val]=(f[i+&][val]+sz[k]*f[i&][j])%mod;
}
}
for(int j=;j<p;j++) f[i&][j]=;
}
//不包含素数
for(int i=;i<=tot&&prime[i]<=m;i++) sz[prime[i]%p]--;
for(int i=;i<p;i++) g[][i]=sz[i];
for(int i=,val;i<n;i++){
for(int j=;j<p;j++){
for(int k=;k<p;k++){
val=(j+k)%p;
g[i+&][val]=(g[i+&][val]+sz[k]*g[i&][j])%mod;
}
}
for(int j=;j<p;j++) g[i&][j]=;
}
printf("%d",f[n&][]-g[n&][]);
return ;
}

AC代码

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=;
const int N=;
const int M=2e7+;
int tot,prime[M/];bool check[M];
int n,m,p;
int sz[N];
struct matrix{
ll s[N];//降低常数
matrix(){
memset(s,,sizeof s);
}
}A,B;
matrix operator *(const matrix &a,const matrix &b){
matrix c;
for(int i=;i<p;i++){
// c.s[i]=0;
for(int k=;k<p;k++){
c.s[i]+=a.s[(i-k+p)%p]*b.s[k];
c.s[i]%=mod;
}
}
return c;
}
ll fpow(matrix a,ll p){
matrix res;
// for(int i=0;i<p;i++) res.s[i]=0;
res.s[]=;
for(;p;p>>=,a=a*a) if(p&) res=res*a;
return res.s[];
}
void pre(){
check[]=check[]=;
for(int i=;i<=m;i++){
if(!check[i]) prime[++tot]=i;
for(int j=;j<=tot&&i*prime[j]<=m;j++){
check[i*prime[j]]=;
if(!(i%prime[j])) break;
}
}
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
pre();
for(int k=;k<=p;k++) sz[k]=m/p+(m%p>=k);sz[]=sz[p];
for(int i=;i<p;i++) A.s[i]=sz[i];
for(int i=;i<=tot&&prime[i]<=m;i++) sz[prime[i]%p]--;
for(int i=;i<p;i++) B.s[i]=sz[i];
ll ans=(fpow(A,n)-fpow(B,n))%mod;if(ans<) ans+=mod;
printf("%lld",ans);
return ;
}