牛客小白月赛28

牛牛和牛可乐的赌约
直接概率问题；
对于分数求mod，用费马小定理；

#include<iostream>
using namespace std;
const int mod=1e9+7;
#define int long long
int power(int a,int b)//快速幂
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
signed main()
{
     ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        int h=power(n,m);
        int cnt=power(h,mod-2);
        cout<<(h-1)*cnt%mod<<endl;
    }
}

牛牛和牛可乐的赌约2
找规律；
根据题意，可以观察出(0,0),(1,0),(2,0),(1,0),(2,0）为必胜态；
每3*3矩阵，对角线为必败态；

#include<iostream>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>x>>y;
        if(x%3==y%3) printf("awsl\n");
        else printf("yyds\n");
    }
}

D 位运算之谜
a&b==y则a,b至少为y；

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>x>>y;
        if(x-2*y<0||((x-2*y)&y)>0) cout<<-1<<endl;
        else{
            int k=x-2*y;//因为a&b==y所以，剩余的a中二进制的1与b中二进制的1一定不在同一位置。而a+b==x，k的二进制1一定蕴含在a,b中，所以a^b=k;
            cout<<k<<endl;            
        }
    }
}

牛牛和字符串的日常
KMP裸的；

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100100;
int sum=0;
int pre[maxn];//next数组，记录长度为i的字符串，最大公共前后缀
void pre_table(char p[],int pre[],int n)//初始化pre数组
{
    pre[0]=0;
    int len=0,i=1;
    while(i<n)
    {
        if(p[i]==p[len])
        {
            len++;
            pre[i]=len;
            i++;
        }
        else{
            if(len>0) len=pre[len-1];
            else pre[i]=len,i++;
        }
    }
    for(int i=n-1;i>0;i--)//这里把每个往后错一位；（各有各的写法~~
        pre[i]=pre[i-1];
    pre[0]=-1;
}
int KMP(char text[],char p[],int n)
{
    int k=strlen(text),max1=0,cnt=0;//k为text数组的长度，不断比较数组p（即s数组）与text数组的公共部分，求最大公共部分；
    int i=0,j=0;
    while(i<k)
    {
        if(j==n-1&&p[j]==text[i])//这里是如果最后一个字符相等，则text中包含数组p
        {
            cnt=0;return n;
            j=pre[j];
        }
        if(p[j]==text[i])
        {
            i++,j++;cnt++;
        }
        else{
            j=pre[j];cnt=0;
            if(j==-1) i++,j++;//相当于p数组第一个字符与text当前字符不相等，直接后移
        }
        max1=max(cnt,max1);
    }
    return max1;
}
signed main()
{
    int n;
    char s[maxn];
    cin>>s;
    cin>>n;
    pre_table(s,pre,strlen(s));
    for(int i=1;i<=n;i++)
    {
        char text[maxn];
        cin>>text;
        sum+=KMP(text,s,strlen(s));
    }
    cout<<sum<<endl;
}