HDU - 5685 Problem A（逆元）

2021-09-15 18:18:48

　　这题我第一次想的就是直接模拟，因为我是这样感觉的，输入n是3次方，长度是5次方，加起来才8次方，里面的操作又不复杂，感觉应该能过，然而不如我所料，TLE了，玛德，这是第一次的代码。

#include <bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long LL;

#define PI(A) printf("%d\n",A)

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const double EPS= 1e- ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN=  +  ;

char str[MAXN];

int N;

int main()

{

    while(~SI(N))

    {

        int x,y;

        scanf("%s",str);

        while(N--)

        {

            LL ans=;

            SII(x,y);

            x--,y--;

            for (int i=x;i<=y;i++)

            {

                ans=ans*((int)str[i]-);

                ans%=;

            }

            printf("%lld\n",ans);

        }

    }

    return ;

}

　　之后想了一会，想不通，就查题解了，我看的是这个题解 http://www.cnblogs.com/inmoonlight/p/5512340.html

　　看了之后，觉得有几点要注意：

　　1.像这样求连乘的，一段区间的东西，一定要先打表，之后在输入查询，否则几乎绝对超时，比如求这题可以换成H(t)/H(s-1)，由此可以想到，连加的时候也可以打表，那就是H(t)-H(s-1)

　　2.看到大数相除，还取模，那就是逆元了，可以用 exgcd 或费马小定理求，这里可以写个函数自己判断下m是不是素数，9973 显然是素数，所以就费马小定理。费马小定理，H(n)的逆元为H(n)^MOD-2% MOD，当MOD是素数时。

　　之后，理所当然，AC

#include <bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long LL;

#define PI(A) printf("%d\n",A)

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const double EPS= 1e- ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN=  +  ;

char str[MAXN];

int h[MAXN];

int N;

int M=;

//快速幂模板

LL mod_pow(LL x,LL n,LL mod)

{

    LL res=;

    while(n>){

        if (n&) res=res*x%mod;

        x=x*x%mod;

        n>>=;

    }

    return res;

}

int main()

{

    while(~SI(N))

    {

        int x,y;

        scanf("%s",str);

        h[]=;

        //注意这是str[i]!='\0' 不是strlen(str) 如果换了 会超时，因为调用函数浪费时间，不信？ 你自己试下，就知道了

        for (int i=;str[i];i++)

        {

            h[i+]=h[i]*(str[i]-)%M;

        }

        while(N--)

        {

            SII(x,y);

            printf("%lld\n",h[y]*mod_pow(h[x-],M-,M)%M);

        }

    }

    return ;

}

　　做完这题，有个感悟，就是不管什么题，不求速度，只求质量，一定要搞懂，就算一周只看一个题，只要搞懂了，绝对比看100道，一道都没懂好。

　　在附赠一个测素数的代码：

#include <bits/stdc++.h>

using namespace std;

int N;

int main()

{

    //PS:9973   1e9+7  都是素数

    while(cin>>N)

    {

        bool fl=;

        for (int i=;i<=sqrt(N);i++)

        {

            if (N%i==)

                fl=;

        }

        puts(fl&&N>?"yes":"no");

    }

    return ;

}

码农公寓

相关文章