头像

hyc_noi


访客:2631

离线:5小时前


活动打卡代码 AcWing 1312. 序列统计

hyc_noi
5小时前
#include<bits/stdc++.h>
using namespace std;
const int P=1e6+3;
int qmi(int a,int k)
{
    int res=1;
    while(k)
    {
        if(k&1)
            res=1ll*res*a%P;
        a=1ll*a*a%P;
        k>>=1;
    }
    return res;
}
int C(int a,int b)
{
    if(a<b)
        return 0;
    int up=1,down=1;
    for(int i=a,j=1;j<=b;i--,j++)
    {
        up=1ll*i*up%P;
        down=1ll*j*down%P;
    }
    return 1ll*up*qmi(down,P-2)%P;
}
int lucas(int a,int b)
{
    if(a<P&&b<P)
        return C(a,b);
    return 1ll*lucas(a/P,b/P)*C(a%P,b%P)%P;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,l,r;
        scanf("%d%d%d",&n,&l,&r);
        printf("%d\n",(lucas(r-l+n+1,r-l+1)+P-1)%P);
    }
    return 0;
}


活动打卡代码 AcWing 1310. 数三角形

hyc_noi
11小时前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}
ll C(int a)
{
    return 1ll*a*(a-1)*(a-2)/6;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    n++;
    m++;
    ll res=C(n*m)-C(m)*n-C(n)*m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            res-=2ll*(gcd(i,j)-1)*(n-i)*(m-j);
    printf("%lld",res);
    return 0;
}


活动打卡代码 AcWing 1309. 车的放置

hyc_noi
14小时前
#include<bits/stdc++.h>
using namespace std;
const int NN=2004,mod=100003;
int mul[NN],nimul[NN];
int qmi(int a,int k)
{
    int res=1;
    while(k)
    {
        if(k&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        k>>=1;
    }
    return res;
}
int C(int a,int b)
{
    if(a<b)
        return 0;
    return 1ll*mul[a]*nimul[a-b]*nimul[b]%mod;
}
int P(int a,int b)
{
    if(a<b)
        return 0;
    return 1ll*mul[a]*nimul[a-b]%mod;
}
int main()
{
    mul[0]=nimul[0]=1;
    for(int i=1;i<NN;i++)
    {
        mul[i]=1ll*mul[i-1]*i%mod;
        nimul[i]=1ll*nimul[i-1]*qmi(i,mod-2)%mod;
    }
    int a,b,c,d,k;
    scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
    int ans=0;
    for(int i=0;i<=k;i++)
        ans=(ans+1ll*C(b,i)*P(a,i)%mod*C(d,k-i)*P(a+c-i,k-i))%mod;
    printf("%d",ans);
    return 0;
}


活动打卡代码 AcWing 1308. 方程的解

hyc_noi
17小时前
#include<bits/stdc++.h>
using namespace std;
const int NN=150,P=1000;
int f[P+4][104][NN];
int qmi(int x,int k)
{
    int res=1;
    while(k)
    {
        if(k&1)
            res=res*x%P;
        x=x*x%P;
        k>>=1;
    }
    return res;
}
void add(int c[],int a[],int b[])
{
    int t=0;
    for(int i=0;i<NN;i++)
    {
        t+=a[i]+b[i];
        c[i]=t%10;
        t/=10;
    }
}
int main()
{
    int k,x;
    scanf("%d%d",&k,&x);
    int n=qmi(x%P,x);
    for(int i=0;i<n;i++)
        for(int j=0;j<=i&&j<k;j++)
            if(!j)
                f[i][j][0]=1;
            else
                add(f[i][j],f[i-1][j],f[i-1][j-1]);
    int* g=f[n-1][k-1],i=NN-1;
    while(!g[i])
        i--;
    while(i>=0)
        printf("%d",g[i--]);
    return 0;
}


活动打卡代码 AcWing 1307. 牡牛和牝牛

hyc_noi
1天前
#include<bits/stdc++.h>
using namespace std;
int s[100004];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    s[0]=1;
    for(int i=1;i<=n;i++)
        s[i]=(s[i-1]+s[max(i-k-1,0)])%5000011;
    printf("%d",s[n]);
    return 0;
}


活动打卡代码 AcWing 1305. GT考试

hyc_noi
1天前
#include<bits/stdc++.h>
using namespace std;
const int NN=24;
int n,m,p,ne[NN],a[NN][NN];
char s[NN];
void mul(int c[][NN],int a[][NN],int b[][NN])
{
    int temp[NN][NN]={0};
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<m;k++)
                temp[i][j]=(temp[i][j]+1ll*a[i][k]*b[k][j])%p;
    memcpy(c,temp,sizeof(temp));
}
int qmi(int k)
{
    int res[NN][NN]={1};
    while(k)
    {
        if(k&1)
            mul(res,res,a);
        mul(a,a,a);
        k>>=1;
    }
    int sum=0;
    for(int i=0;i<m;i++)
        (sum+=res[0][i])%=p;
    return sum;
}
int main()
{
    scanf("%d%d%d%s",&n,&m,&p,s+1);
    int j=0;
    for(int i=2;i<=m;i++)
    {
        while(j&&s[i]!=s[j+1])
            j=ne[j];
        if(s[i]==s[j+1])
            j++;
        ne[i]=j;
    }
    for(int j=0;j<m;j++)
        for(char c='0';c<='9';c++)
        {
            int k=j;
            while(k&&s[k+1]!=c)
                k=ne[k];
            if(s[k+1]==c)
                k++;
            if(k<m)
                a[j][k]++;
        }
    printf("%d",qmi(n));
    return 0;
}



hyc_noi
1天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
void mul(int c[][3],int a[][3],int b[][3],int n)
{
    int temp[n][3]={0};
    for(int i=0;i<n;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                temp[i][j]=(temp[i][j]+1ll*a[i][k]*b[k][j])%m;
    memcpy(c,temp,sizeof(temp));
}
int main()
{
    int f[1][3]={1,1,1},a[3][3]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };
    scanf("%d%d",&n,&m);
    n--;
    while(n)
    {
        if(n&1)
            mul(f,f,a,1);
        mul(a,a,a,3);
        n>>=1;
    }
    printf("%d",f[0][2]);
    return 0;
}


活动打卡代码 AcWing 1298. 曹冲养猪

hyc_noi
2天前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN=14;
int a[NN],b[NN];
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main()
{
    int n;
    scanf("%d",&n);
    ll m=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        m*=a[i];
    }
    ll res=0;
    for(int i=1;i<=n;i++)
    {
        ll mi=m/a[i],ti,y;
        exgcd(mi,a[i],ti,y);
        res+=1ll*b[i]*mi*ti;
    }
    printf("%lld",(res%m+m)%m);
    return 0;
}


活动打卡代码 AcWing 202. 最幸运的数字

hyc_noi
2天前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll smul(ll a,ll k,ll p)
{
    ll res=0;
    while(k)
    {
        if(k&1)
            (res+=a)%=p;
        (a+=a)%=p;
        k>>=1;
    }
    return res;
}
ll qmi(ll a,ll k,ll p)
{
    ll res=1;
    while(k)
    {
        if(k&1)
            res=smul(res,a,p);
        a=smul(a,a,p);
        k>>=1;
    }
    return res;
}
ll calc(ll x)
{
    ll res=x;
    for(ll i=2;i<=x/i;i++)
        if(!(x%i))
        {
            while(!(x%i))
                x/=i;
            res=res/i*(i-1);
        }
    if(x>1)
        res=res/x*(x-1);
    return res;
}
int main()
{
    int t=0;
    ll l;
    while(scanf("%lld",&l)&&l)
    {
        int d=1;
        while(!(l%(d*2))&&d*2<=8)
            d*=2;
        ll x=9*l/d,phi=calc(x),ans=1e18;
        if(!(x%2)||!(x%5))
            ans=0;
        for(ll d=1;d<=phi/d;d++)
            if(!(phi%d))
            {
                if(qmi(10,d,x)==1)
                    ans=min(ans,d);
                if(qmi(10,phi/d,x)==1)
                    ans=min(ans,phi/d);
            }
        printf("Case %d: %lld\n",++t,ans);
    }
    return 0;
}


活动打卡代码 AcWing 222. 青蛙的约会

hyc_noi
2天前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
    return y?gcd(y,x%y):x;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main()
{
    ll x,y,n,m,l;
    scanf("%lld%lld%lld%lld%lld",&x,&y,&n,&m,&l);
    ll d=gcd(n-m,l);
    if(n==m||(y-x)%d)
    {
        printf("Impossible");
        return 0;
    }
    ll a,b;
    exgcd(n-m,l,a,b);
    a*=(y-x)/d;
    ll t=abs(l/d);
    printf("%lld",(a%t+t)%t);
    return 0;
}