牛客练习赛48

B.小w的a=b问题

题意：给出两个序列求这两个序列的所有数的阶乘积是否相等

我采用分解质因数的方法非常的麻烦

题解:

先预处理 x！= f[x] 肯定要加一个模数模数为一个大质数为了避免偶然性处理10个模数

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
long long mod[10]={10000019,10000079,10000103,10000121,10000139,10000141,10000169,10000189,10000223,10000229};
long long fact[MAXN][10],hash1[10],hash2[10],a[MAXN],b[MAXN];
int T,n,m;
int main()
{
    for(int i=0;i<10;++i)
    {
        fact[0][i]=1;
    }
    for(long long i=1;i<=100000;++i)
    {
        for(int j=0;j<10;++j)
        {
            fact[i][j]=(fact[i-1][j]*i)%mod[j];
        }
    }
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=m;++i)
        {
            scanf("%lld",&b[i]);
        }
        for(int i=1;i<10;++i)
        {
            hash1[i]=hash2[i]=1;
        }
        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<10;++j)
            {
                hash1[j]=(hash1[j]*fact[a[i]][j])%mod[j];
            }
        }
        for(int i=1;i<=m;++i)
        {
            for(int j=0;j<10;++j)
            {
                hash2[j]=(hash2[j]*fact[b[i]][j])%mod[j];
            }
        }
        bool flag=true;
        for(int j=0;j<10;++j)
        {
            if(hash1[j]!=hash2[j])
            {
                flag=false;
            }
        }
        if(flag)
        {
            printf("equal
");
        }
        else
        {
            printf("unequal
");
        }
    }
    return 0;
}

View Code

小w的糖果

一个序列n个数一开始都为0 下面有三种操作

1. 将x位置及以后的数+1

2.将x位置及以后的数+当前位置是第几个加的

3.将x位置及以后的数+ 当前位置是第几个加的的平方

用了线段树维护差分数组又是脑残做法

题解:

维护差分数组

1 2 较简单

3 为三重差分计算得当前项与前一项相差 2k-1

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
const long long mod=(long long)1e9+7;
long long d1[MAXN],d2[MAXN],d3[MAXN];//1 id id2
int n,m,T,type,pos;
void pre_sum(long long a[])
{
    for(int i=1;i<=n;++i)
    {
        a[i]=(a[i]+a[i-1])%mod;
    }
    return;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(d1,0,sizeof(d1));
        memset(d2,0,sizeof(d2));
        memset(d3,0,sizeof(d3));
        scanf("%d %d",&n,&m);
        while(m--)
        {
            scanf("%d %d",&type,&pos);
            if(type==1)
            {
                d1[pos]++;
            }
            if(type==2)
            {
                d2[pos]++;
            }
            if(type==3)
            {
                d3[pos]++;
                d3[pos+1]++;
            }
        }
        pre_sum(d1);
 
        pre_sum(d2);
        pre_sum(d2);
 
        pre_sum(d3);
        pre_sum(d3);
        pre_sum(d3);
 
        for(int i=1;i<=n;++i)
        {
            printf("%lld%c",(d1[i]+d2[i]+d3[i])%mod,i==n?'
':' ');
        }
    }
    return 0;
}

View Code