1001：Age of Moyu

 

1002：

 

1005：GuGuFishtion

首先推公式，欧拉函数是积性函数但不是一个完全积性函数，所以a，b不互质的情况下肯定还有一个偏移量。然后质因数分解一下a,b可以用数论知识证明差一个GCD(a,b)/Φ(GCD(a,b))，所以对于所有a，b不互质的情况下对答案的贡献是GCD(a,b)/Φ(GCD(a,b))，互质的话贡献是1。然后容斥，枚举k，容斥计算以k作为gcd的数对有多少个，然后乘上贡献就行了。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1000000+5;

LL tmp,ans;
long long n,m,p;
long long phi[N], cnt, prime[N/3],dy[N], val[N], q[N],sum_val[N],sum[N],inv[N],mu[N];
bool com[N];

int primes;
void get_prime_phi(){
   memset( com, false, sizeof( com ) );
    primes = 0;
    phi[1] = 1;
    mu[1] = 1;
    for (int i = 2; i < N; ++i){
        if (!com[i]) {
            prime[primes++] = i;
            phi[i] = i-1;
            mu[i] = -1;
        }
        for (int j = 0; j < primes && i*prime[j] <= N; ++j){
            com[i*prime[j]] = true;
            if (i % prime[j]){
                phi[i*prime[j]] = phi[i]*(prime[j]-1);
                mu[i*prime[j]] = -mu[i];
            }
            else {
                mu[i*prime[j]] = 0;
                phi[i*prime[j]] = phi[i]*prime[j];
                break;
            }
        }
    }
}

int lim;
long long f[N],F[N];

void get(){
    for(int i=1;i<=lim;++i)   F[i]=1ll*(m/i)*(n/i)%p;
    for(int i=lim;i>0;--i){
            f[i]=F[i];
        for(int j=i+i;j<=lim;j+=i)
            f[i]-=1ll*f[j]%p;
    }
    for(int i=1;i<=lim;++i)   f[i]%=p;
}


int main(){
    //freopen("case.in","r",stdin);
    int T;
    scanf("%d",&T);
    get_prime_phi();

    while(T--){
        scanf("%lld%lld%lld",&n,&m,&p); tmp=ans=0;
        lim=min(n,m);
        memset(inv,0,sizeof(inv));
        memset(f,0,sizeof(f));
        inv[1]=1;
        for(register int i=2;i<=lim+2;i++)
            inv[i]=(LL)(p-p/i)*inv[p%i]%p;
        get();

        for(register int i=1;i<=lim;i++){
            val[i]=(LL)i*inv[phi[i]]%p;
            ans=(ans+(LL)val[i]*f[i]%p)%p;
            if(ans<0) ans+=p;
            //cout<<ans<<endl;
        }

        printf("%lld\n",ans);
    }
    return 0;
}

View Code

 

1006：

有意思的dp;
根据异或的性质,X_0⊕X_1⊕X_2⊕X_3⊕…..⊕X_(M-1)=S⊕T 
计算出S⊕T中一共有cnt个1，将这个二进制数标准化,使它成为前面N-cnt个0，后cnt个1的二进制数，答案保持不变，问题变为:用K个N位且有3个1的不同二进制数进行异或，最终得到前面N-cnt个0，后面cnt个1这个二进制数，有多少种方案？ 
递推。设d[K][M]表示用K个N位且有3个1的不同二进制数进行异或，最终得到前面N-cnt个0，后面cnt个1这个二进制数的方案数。
然后可以容易推出状态只可以从上一层的-1，-3，+1，+3这些状态转移过来 
考虑加入重复串的影响，d[i][j]-= (d[i-2][j] * (C[n][3]-i+2);表示去除加入i-2个数字并且后面有j个1这个二进制数但后来又异或上两个之前没用过的相同的数的方案数， 
考虑二进制数加入的先后顺序给答案带来的额外贡献，d[i][j]=d[i][j]*inv[i]%mod 

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
const long long mod=19260817;

long long dp[30][50],c[50][50],inv[110];
char S[45],T[45];
int n,k;

void init()
{
    memset(dp,0,sizeof(dp));
}

int main()
{
    int i,j;
    c[0][0]=1;
    for(i=1;i<=45;i++)
    {
        c[i][0]=c[i][i]=1;
        for(j=1;j<i;j++)
        {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }

    inv[1]=1;
    for(i=2;i<=60;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;

    int cas=1;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        if(n==0&&k==0) break;
        init();
        scanf("%s%s",S,T);
        int num_1=0;
        for(i=0;i<n;i++)
            if((S[i]-'0')^(T[i]-'0')==1) num_1++;
        dp[0][0]=1;
        for(i=1;i<=k;i++)
        {
            for(j=0;j<=n;j++)
            {
                if(j>=3) dp[i][j]=(dp[i][j]+dp[i-1][j-3]*c[j][3])%mod;
                if(j>=1) dp[i][j]=(dp[i][j]+dp[i-1][j-1]*c[j][2]%mod*c[n-j][1])%mod;
                if(j+3<=n) dp[i][j]=(dp[i][j]+dp[i-1][j+3]*c[n-j][3])%mod;
                if(j+1<=n) dp[i][j]=(dp[i][j] + dp[i - 1][j + 1] * c[j][1] %mod* c[n - j][2]) % mod;
                if (i - 2 >= 0)dp[i][j] = (dp[i][j] - (dp[i - 2][j] * (c[n][3] - i + 2))) % mod;
                dp[i][j] = dp[i][j] * inv[i] % mod;
                if(dp[i][j]<0) dp[i][j]+=mod;
            }
        }
        printf("Case #%d: %lld\n",cas++, dp[k][num_1]);
    }
    return 0;
}

View Code

1007：

 

1008：

 

1009：

 

1010：

矩阵快速幂，首先可以看出这题只能用矩阵快速幂，然后考虑对p进行分块，处理出p/i这个矩阵的指数，然后就矩阵快速幂了

 

1011：

 

版权声明：本文为Hetui原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Hetui/p/9477405.html