头像

ৡ心梦ﻬ




在线 



给定n堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。

问如果两人都采用最优策略,先手是否必胜。

输入格式
第一行包含整数n。

第二行包含n个数字,其中第 i 个数字表示第 i 堆石子的数量。

输出格式
如果先手方必胜,则输出“Yes”。

否则,输出“No”。

数据范围
1≤n≤105,
1≤每堆石子数≤109
输入样例:

2
2 3

输出样例:

Yes

nim游戏.jpg


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
    ll res=0;
    while(n--)
    {
        ll a;
        cin>>a;
        res^=a;
    }
    if(res)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}



给定n个0和n个1,它们将按照某种顺序排成长度为2n的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。

输出的答案对109+7取模。

输入格式
共一行,包含整数n。

输出格式
共一行,包含一个整数,表示答案。

数据范围
1≤n≤105
输入样例:

3

输出样例:

5

卡特兰数.jpg

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll qsm(ll a,ll k,ll p)    //快速幂求逆元; 
{
    ll res=1;
    while(k)
    {
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
} 
int main()
{
    ll n;
    cin>>n;
    ll a=2*n,b=n; 
    ll res=1;
    for(ll i=a;i>a-b;i--)res=res*i%mod;
    for(ll i=1;i<=b;i++)res=res*qsm(i,mod-2,mod)%mod;
    res=res*qsm(b+1,mod-2,mod)%mod;
    cout<<res<<endl;
}



输入a,b,求Cba的值。

注意结果可能很大,需要使用高精度计算。

输入格式
共一行,包含两个整数a和b。

输出格式
共一行,输出Cba的值。

数据范围
1≤b≤a≤5000
输入样例:

5 3

输出样例:

10

组合数4.png

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5210;
ll primes[N],cnt;
ll st[N],sum[N];
void gets_primes(ll n)                  //找0-a的质数 
{
    for(ll i=2;i<=n;i++)
    {
        if(!st[i])primes[cnt++]=i;
        for(ll j=0;primes[j]<=n/i;j++)
        {
            st[i*primes[j]]=1;
            if(i%primes[j]==0)break;
        }
    }
}
ll get(ll n,ll p)         //找n!中p的数; 
{
    ll res=0;
    while (n)
    {           
        res+=n/p;
        n/=p;
    }
    return res;
}
vector<ll> mul(vector<ll>A,ll b)
{
    vector<ll>C;
    ll t=0;
    for(ll i=0;i<A.size()||t;i++)
    {
        if(i<A.size())t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    return C;
}

int main()
{
    ll a,b;
    cin>>a>>b;
    gets_primes(a);
    for(ll i=0;i<cnt;i++)
    {
        ll p=primes[i];
        sum[i]=get(a,p)-get(b,p)-get(a-b,p);
    }
    vector<ll>res;
    res.push_back(1);           //初始化; 
    for(ll i=0;i<cnt;i++)
    {
        for(ll j=0;j<sum[i];j++)
        {
            res=mul(res,primes[i]);
        }
    }
    for(ll i=res.size()-1;i>=0;i--)cout<<res[i];   //逆向输出; 
    cout<<endl;
 } 



给定n组询问,每组询问给定三个整数a,b,p,其中p是质数,请你输出Cba mod p的值。

输入格式
第一行包含整数n。

接下来n行,每行包含一组a,b,p。

输出格式
共n行,每行输出一个询问的解。

数据范围
1≤n≤20,
1≤b≤a≤1018,
1≤p≤105,

输入样例:

3
5 3 7
3 1 5
6 4 13

输出样例:

3
3
2

卢卡斯定理证明
卢卡斯1.jpg
卢卡斯2.jpg
本题代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qsm(ll a,ll k,ll p)
{
    ll res=1;
    while(k)
    {
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
ll c(ll a,ll b,ll p)
{
    if(b>a)return 0;                        //如果有一项的b>a则说明在(1+x)^中x^b的系数为0;
    ll res=1;
    for(ll i=1,j=a;i<=b;i++,j--)            //Cab=(a-b+1)!/b!;
    {
        res=res*j%p;
        res=res*qsm(i,p-2,p)%p;             //快速幂求逆元;
    }
    return res;
}
ll lucas(ll a,ll b,ll p)
{
    if(a<p&&b<p)return c(a,b,p);
    return c(a%p,b%p,p)*lucas(a/p,b/p,p)%p;//递归求解的过程;
}
int main()
{
    ll k;
    cin>>k;
    while(k--)
    {
        ll a,b,p;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    return 0;
}



给定n组询问,每组询问给定两个整数a,b,请你输出Cba mod (109+7)的值。

输入格式
第一行包含整数n。

接下来n行,每行包含一组a和b。

输出格式
共n行,每行输出一个询问的解。

数据范围
1≤n≤10000,
1≤b≤a≤105
输入样例:

3
3 1
5 3
2 2

输出样例:

3
10
1

组合数2.png

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,mod=1e9+7;
ll shang[N],xia[N];
ll qsm(ll a,ll k,ll p)     
{
    ll res=1;
    while(k)
    {
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*a%p;
    } 
    return res;
}
int main()
{
    shang[0]=1;xia[0]=1;                     //预处理所有的上下的积; 
    for(ll i=1;i<N;i++)
    {
        shang[i]=shang[i-1]*i%mod;
        xia[i]=xia[i-1]*qsm(i,mod-2,mod)%mod;
    }
    ll k;cin>>k;
    while (k--)
    {
        ll a,b;
        cin>>a>>b;
        cout<<shang[a]*xia[b]%mod*xia[a-b]%mod<<endl;
                    //先mod一次防止爆范围 
    }
 } 



给定n组询问,每组询问给定两个整数a,b,请你输出Cba mod (109+7)的值。

输入格式
第一行包含整数n。

接下来n行,每行包含一组a和b。

输出格式
共n行,每行输出一个询问的解。

数据范围
1≤n≤10000,
1≤b≤a≤2000
输入样例:

3
3 1
5 3
2 2

输出样例:

3
10
1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2020;
ll p[N][N];
ll mod=1e9+7;
void oo()           //数据小询问多预处理; 
{
    p[0][0]=1;                //为了初始化; 
    for(ll i=1;i<N;i++)
        for(ll j=0;j<=i;j++)
            if(!j)p[i][j]=1;
            else p[i][j]=(p[i-1][j]+p[i-1][j-1])%mod;
}
int main()
{
    oo();
    ll k;
    cin>>k;
    while(k--)
    {
        ll a,b;
        cin>>a>>b;
        cout<<p[a][b]<<endl;
    }
}



给定n组数据ai,bi,mi,对于每组数求出一个xi,使其满足ai∗xi≡bi(mod mi),如果无解则输出impossible。

输入格式
第一行包含整数n。

接下来n行,每行包含一组数据ai,bi,mi。

输出格式
输出共n行,每组数据输出一个整数表示一个满足条件的xi,如果无解则输出impossible。

每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。

输出答案必须在int范围之内。

数据范围
1≤n≤105,
1≤ai,bi,mi≤2∗109
输入样例:

2
2 3 6
4 3 5

输出样例:

impossible
7

题解·
裴蜀定理证明见下方链接
线性同余.jpg
裴蜀定理证明

#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;              //这题会爆int
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x); 
                           //这时的x为上一层的y,在递归时已经赋值;
    y-=a/b*x;              //这时的y为上层的x; 

/*  ll d=exgcd(b,a%b,x,y); //也可以这么写; 
    ll c=x;
    x=y;
    y=c-a/b*y;
*/

    return d;
}
int main()
{
    ll k;
    cin>>k;
    while (k--)
    {
        ll a,b,m,x,y;
        cin>>a>>b>>m;
        ll d=exgcd(a,m,x,y);
        if(b%d)cout<<"impossible"<<endl;  //b不是d的倍数则x不存在; 
        else cout<<x*b/d%m<<endl;         //mod m 防止爆int 
    }
}



给定n对正整数ai,bi,对于每对数,求出一组xi,yi,使其满足ai∗xi+bi∗yi=gcd(ai,bi)。

输入格式
第一行包含整数n。

接下来n行,每行包含两个整数ai,bi。

输出格式
输出共n行,对于每组ai,bi,求出一组满足条件的xi,yi,每组结果占一行。

本题答案不唯一,输出任意满足条件的xi,yi均可。

数据范围
1≤n≤105,
1≤ai,bi≤2∗109
输入样例:

2
4 6
8 18

输出样例:

-1 1
-2 1

裴蜀定理和本题证明
扩展欧几里得.jpg

#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)    //要注意传值引用,不然变量的变化不能传递回主函数;
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x); 
                           //这时的x为上一层的y,在递归时已经赋值;
    y-=a/b*x;              //这时的y为上层的x; 

/*  ll d=exgcd(b,a%b,x,y); //也可以这么写; 
    ll c=x;
    x=y;
    y=c-a/b*y;
*/

    return d;
}
int main()
{
    ll k;cin>>k;
    while (k--)
    {
        ll a,b;
        cin>>a>>b;
        ll x,y;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
}



给定n组ai,pi,其中pi是质数,求ai模pi的乘法逆元,若逆元不存在则输出impossible。

注意:请返回在0∼p−1之间的逆元。

乘法逆元的定义
若整数b,m互质,并且对于任意的整数 a,如果满足b|a,则存在一个整数x,使得a/b≡a∗x(mod m),则称x为b的模m乘法逆元,记为b−1(mod m)。
b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时,bm−2即为b的乘法逆元。

输入格式
第一行包含整数n。

接下来n行,每行包含一个数组ai,pi,数据保证pi是质数。

输出格式
输出共n行,每组数据输出一个结果,每个结果占一行。

若ai模pi的乘法逆元存在,则输出一个整数,表示逆元,否则输出impossible。

数据范围
1≤n≤105,
1≤ai,pi≤2∗109
输入样例:

3
4 3
8 5
6 3

输出样例:

1
2
impossible

证明快速幂求逆元
111.jpg
证明欧拉定理
222.jpg

//p要和a互质才可以; 
#include<iostream>
using namespace std;
typedef long long ll;
ll oo(ll a,ll k,ll p)
{
    ll res=1;
    while (k)
    {
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int main()
{
    ll k;cin>>k;
    while (k--)
    {
        ll a,p;
        cin>>a>>p;
        if(a%p)cout<<oo(a,p-2,p)<<endl;   //因为p是质数,只要a不是p的倍数ap即互质; 
        else cout<<"impossible"<<endl;
    }
}



给定n组ai,bi,pi,对于每组数据,求出abii mod pi的值。

输入格式
第一行包含整数n。

接下来n行,每行包含三个整数ai,bi,pi。

输出格式
对于每组数据,输出一个结果,表示abii mod pi的值。

每个结果占一行。

数据范围
1≤n≤100000,
1≤ai,bi,pi≤2∗109
输入样例:

2
3 2 5
4 3 9

输出样例:

4
1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll oo(ll n,ll k,ll p)
{
    ll res=1;
    while(k)
    {
        if(k&1)res=res*n%p;   //如果二进制数最后一位为 1 相乘; 
        k>>=1;                //幂数左移; 
        n=n*n%p;              //更新n 
    }
    return res;
}
int main()
{
    ll k;
    cin>>k;
    while (k--)
    {
        ll n,k,p;
        cin>>n>>k>>p;
        cout<<oo(n,k,p)<<endl;
    }

}