[LOJ2002] [SDOI2017] 序列计数

题目链接

LOJ：https://loj.ac/problem/2002

洛谷：https://www.luogu.org/problemnew/show/P3702

Solution

考虑补集转换，用所有数减去只用合数的方案数，我们先考虑算所有数的

首先可以得到一个普及组\(\rm dp\)，\(f_{i,j}\)表示当前填了前\(i\)个，总和\({\rm mod}\ p\)为\(j\)的方案数。

记录一个\(cnt_i\)表示\({\rm mod}\ p\)为\(i\)的数的个数。

转移就是\(f_{i,j}=\sum_{k=0}^{p-1}f_{i-1,(j-k){\rm mod}\ p}\cdot cnt_k\)。

然后我们拿矩阵大力优化这个转移就可以过了。

复杂度\(O(p^3\log n)\)。

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define ll long long 

#define pii pair<int,int >

#define vec vector<int >

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) 

const int maxm = 2e7+10;

const int inf = 1e9;

const lf eps = 1e-8;

const int mod = 20170408;

int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}

int del(int x,int y) {return x-y<0?x-y+mod:x-y;}

int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}

int n,m,p;

struct Matrix {

    int a[102][102];

    Matrix () {memset(a,0,sizeof a);}

    Matrix operator * (const Matrix &r) const {

        Matrix c;

        for(int i=0;i<p;i++)

            for(int j=0;j<p;j++)

                for(int k=0;k<p;k++)

                    c.a[i][j]=add(c.a[i][j],mul(a[i][k],r.a[k][j]));

        return c;

    }

};

Matrix qpow(Matrix a,int x) {

    Matrix res;for(int i=0;i<p;i++) res.a[i][i]=1;

    for(;x;x>>=1,a=a*a) if(x&1) res=res*a;

    return res;

}

int pri[maxm],vis[maxm],tot,cnt1[102],cnt2[102];

void sieve() {

    cnt1[1]=cnt2[1]=1;

    for(int i=2;i<=m;i++) {

        if(!vis[i]) pri[++tot]=i;

        else cnt2[i%p]++;

        cnt1[i%p]++;

        for(int j=1;j<=tot&&i*pri[j]<=m;j++) {

            vis[i*pri[j]]=1;

            if(i%pri[j]==0) break;

        }

    }

}

int solve(int *t) {

    Matrix tp,res;

    for(int i=0;i<p;i++)

        for(int j=0;j<p;j++) tp.a[i][j]=t[(i-j+p)%p];

    for(int i=0;i<p;i++) res.a[i][0]=t[i];

    return (qpow(tp,n-1)*res).a[0][0];

}

int main() {

    read(n),read(m),read(p);sieve();

    write(del(solve(cnt1),solve(cnt2)));

    return 0;

}

巴特西

[LOJ2002] [SDOI2017] 序列计数

题目链接

Solution

最新文章

热门文章