| by XianKa | No comments

【数论】欧拉降幂,费马小定理求逆元,阶乘逆元

今天在群里看见一道题目t1

  • 首先这题模数是一个大质数,所以考虑求分母的逆元
  • 由于只需要算一次,没有变量也没有多次询问,所以直接暴力求20192019!%p的结果,然后用费马小定理求出其逆元即可
  • 对于分母,也可以用欧拉定理来降幂,由于p是个质数,所以p的欧拉函数值就是p-1,可以直接放上分子,然后对分子进行快速幂

SharedImage

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll qsm(ll n,ll k,ll md)
{
    ll res=1;
    while(k)
    {
        if(k&1) res=(res*n)%md;
        n=(n*n)%md;
        k>>=1;
    }
    return res%md;
}
int main()
{
    ll fac=1;
    for(int i=1;i<=20192019;i++) fac=(fac*i)%mod;
    ll inv=qsm(fac,mod-2,mod);
    ll son=qsm(2019,qsm(2019,2019,mod-1),mod);
    cout<<inv*son%mod<<endl;
}

 

  • 补充:
  • 对于阶乘的逆元,可以[latex]O(N)[/latex]预处理出其逆元。
  • 假设用费马小定理求出了[latex]q![/latex]的逆元[latex](q!)^{-1}[/latex]。那么就有
  • [latex](q!) * (q!)^{-1} \equiv 1[/latex]
  • [latex](q-1)! * q * (q!)^{-1} \equiv 1[/latex]
  • 从上式可以看出[latex](q-1)![/latex]的逆元就是[latex]q * q!^{-1}[/latex]
  • fact[0]=1;
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
    invfact[n]=qsm(n,mod-2);
    for(int i=n;i>=1;i--) invfact[i-1]=invfact[i]*i%mod;

     

 … Read the rest

Read More
| by XianKa | No comments

【组合|卡特兰数】牛客19寒假R1H

链接:https://ac.nowcoder.com/acm/contest/317/H
来源:牛客网


本题考查对卡特兰数的理解。突破点就是2n天恰好写n天作业。

先把问题抽象成:任意位置,不写为-1,写了为+1,要求在任意位置,前缀和大于-k。

当K=1的时候。结果就是卡特兰数。katelan1

如图,卡特兰数的几何理解。假设写了为往x轴+1,没写为y+1,任何时刻写了要大于等于没写,所以任意合法路径不能够超过y=x+1这条线。

对于任意不合法路径,将其从第一个不合法的地方开始,把剩余图像关于y=x+1对称。那么要达到的(n,n)就变成了(n-1,n+1)。所以对于任意不合法路径,可以看作一条到(n-1,n+1)的路径。

合法路径的条数就是到(n,n)的条数减去到(n-1,n+1)的条数。也就是C(2n,n)-C(2n,n-1)  (因为有一次横着走变成了竖着走,所以是n-1)

本题对于卡特兰数的几何意义作了推广,把y=x+1变成了y=x+k,所以答案就是C(2n,n)-C(2n,n-k)

这里还有一个考点就是组合数取模,有很多做法,由于P不一定是质数,不一定有逆元,可以套线性筛模板,把组合的质因子和幂处理出来,再快速幂。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+233;
int primes[N], cnt;
ll st[N];
ll sum[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; j < cnt && i * primes[j] <= n; j ++ )
        {
            st[primes[j] * i] = primes[j];
            if (i % primes[j] 
Read the rest Read More
| by XianKa | No comments

【数论】牛客19寒假R1D

链接:https://ac.nowcoder.com/acm/contest/317/D
来源:牛客网


数论题

  • 1.1.首先x+y=n在任何时刻都恒成立。所以如果(x,n)=1那么(y,n)=1也必定成立。
  • 1.2.关于gcd(),记作(),支持几种操作:(n-x,n)=(-x,n)=(x,n)也就是说,一边加到另一边,一边取反,gcd的还是不变的。可以由同余的性质证明。
  • 2.1.每次符合条件k的指数就会增加,所以问题就变成了1-n里面和n互质的数,的和。
  • 2.2.欧拉定理,即费马小定理的推广,介绍了欧拉函数phi(x)表示小于x的数里面,与x互质的数,的个数。有1.1得到的结论,如果xn互质,那么n-x也和n互质。两数之和等于n。所以两两配个对。所有数之和 sum(x)=n \times φ(n) \div 2
  • 2.3.关于nphi(n)的奇偶,如果phi(n)是奇数,那么n/2就会和n互质。但由于n/2还是n的一个约数。所以n只能为2。所以phi(n)为奇数当且仅当n=2,此时也可以整除。同时证明了当n不等于2的时候phi(n)一定为偶数。
  • 3.1.最后快速幂处理答案。注意模
#include
using namespace std;
typedef long long ll;
const 
Read the rest
Read More
| by XianKa | No comments

【高斯消元】牛客19寒假R1C

链接:https://ac.nowcoder.com/acm/contest/317/C

来源:牛客网


题目要求有大小顺序,所以可以先把值在第一个最后一个之间的所有数筛选出来;

由于可以进行多次异或操作,所以数字集合也是有一个最大独立集的概念的(有一些数字可以由另一些数字异或得到)。异或是按位计算,所以对数字集合做一遍高斯消元,最多得到15个无关的数字。并且都是阶梯排列的。复杂度可以低到O(15*N)。

接下来可以暴力枚举一遍。但更好的方法是以每一位来看,从最高为到最低位,如果可以为1那么就变成1,否则只能不管。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4;
int n;
int p[maxn];
vector<int> v;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&p[i]);
    }
    if(n==1) {printf("%d",p[0]);return 0;}
    if(p[n-1]>=p[0]) {printf("-1"); return 0;}
    for(int i=1;i<n-1;i++)
    {
        if(p[i]>p[n-1] && p[i]<p[0]) v.push_back(p[i]);
    }
    int ans=p[0]^p[n-1];
    if(v.size())
    {
        for(int i=14,k=0;i>=0;i--)
        {
            for(int j=k;j<v.size();j++)
            {
                if(v[j]>>i & 1) 
                {
                    swap(v[j],v[k]);
                    break;
                }
            }
            if(v[k]>>i & 1)
            {  
                for(int j=k+1;j<v.size();j++)
                {
                    if(v[j]>>i && 1) v[j]^=v[k];
                }
                k++;
            }
        }
        for(int i=14,k=0;i>=0;i--)
        {
            if(v[k]>>i 
Read the rest
Read More
| by XianKa | No comments

【数学/数位DP】牛客网19寒假R3G

链接:https://ac.nowcoder.com/acm/contest/329/G
来源:牛客网

经过了选号和漫长的等待,处女座终于拿到了给小姐姐定制的手环,小姐姐看到以后直呼666!

处女座其实也挺喜欢6这个数字的,实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样,想起了小姐姐。

现在你要给处女座展示一系列数字,你想知道他的内心会激动多少次。对于同一个数字,他最多只会激动一次,即如果这个数是66666,他还是只会激动一次。

输入描述:

一行包括两个数字l,r,表示你给处女座展示的数字范围为[l,r]。

输出描述:

一行一个整数,表示处女座内心激动的次数。
示例1

输入

10 20

输出

1

备注:

0lr1018

此题做法很多。

1.数学

可以先想求不含6的数有多少个,那么题目实际上是问的去掉6以后,给定一个数,问这个数在不含6的数组成的序列中排第几个。那么可以看成是给定一个9进制数,问在十进制数里排第几个(值是多少)。

比如18,看成九进制,[latex]1*9^1 + 7*9^0 = 16[/latex] 。由于6被去掉了,那么8就排在了第7位。这个思想在很多题目里都可以用到。

那么如果给定的数本来就含6怎么处理呢?第一,x5999和x6xxx内所包含的 不含6 的数其实是一样多的。第二,通过列表可以发现,凡是某一位有6的都不存在了,相当于问1和2之间有多少个1。所以对于含6的数,把最高位的6改为5,低位全部改成9就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,pl,pr;
ll ni[22]={0},num[22]={0};

string s;
int len;
ll getnum(ll k)
{
    if(k<6) return k;
    return k-1;
}
ll solve(ll k)
{
    int cnt=0;
    memset(num,0,sizeof(num));
    int flag=0;
    while(k)
    {
        if(k%10==6) flag=1;
        num[cnt++]=k%10;
        k/=10;
    }
    if(flag) 
        
Read the rest Read More
| by XianKa | No comments

【poj1961\kmp算法next数组思想】Period

http://poj.org/problem?id=1961

Period
Time Limit: 3000MS Memory Limit: 30000K
Total Submissions: 20690 Accepted: 10091

Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can … Read the rest
Read More
| by XianKa | No comments

【字符串哈希】CH1401 兔子与兔子

描述
很久很久以前,森林里住着一群兔子。有一天,兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列(小兔子是外星生物,DNA 序列可能包含 26 个小写英文字母),然后我们每次选择两个区间,询问如果用两个区间里的 DNA 序列分别生产出来两只兔子,这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入格式
第一行一个 DNA 字符串 S。
接下来一个数字 m,表示 m 次询问。
接下来 m 行,每行四个数字 l1, r1, l2, r2,分别表示此次询问的两个区间,注意字符串的位置从1开始编号。
其中 1 ≤ length(S), m ≤ 1000000

输出格式
对于每次询问,输出一行表示结果。如果两只兔子完全相同输出 Yes,否则输出 No(注意大小写)

样例输入
aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2
样例输出
Yes
No
Yes

字符串哈希的练习模板题。

  • 坑:strlen很慢,放在循环里会超时。
  • s+1输入字符串,s[0]是结束符,如果传入strlen(s)会返回1;
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=1e6+23;
char s[maxn];
int m,l1,l2,r1,r2;
ull f[maxn],p[maxn];
Read the rest Read More
| by XianKa | No comments

【对顶堆】Running Median POJ – 3784

Running Median
Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3467		Accepted: 1606
Description

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.
Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set 
Read the rest Read More
| by XianKa | No comments

【STL::set】CH1301 邻值查找(迭代器使用学习)

描述
给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 A_i,求:
min(1≤j<i) ⁡|A_i-A_j|
以及令上式取到最小值的 j(记为 P_i)。若最小值点不唯一,则选择使 A_j 较小的那个。

输入格式
第一行一个整数n,第二行n个数A_1~A_n。

输出格式
n-1行,每行2个用空格隔开的整数。分别表示当i取2~n时,对应的 min(1≤j<i) ⁡|A_i-A_j| 和 P_i 的值。

样例输入
3
1 5 3
样例输出
4 1
2 1
数据范围与约定
对于30%的数据: n<=100
对于70%的数据: n<=10^4
对于100%的数据: n<=10^5, |A_i|<=10^9

一种做法是用set,因为set是有序集合,直接依次插入,每次找比这个数大的和小的,比较一下做差的绝对值。

  • 迭代器的使用:
  • set的迭代器只支持++和–两种运算
  • it++ 和 ++it 是不一样的,前者先返回自己,再运算,后者是先运算再返回自己。在使用的时候需要注意。
  • *号解除引用,*(it++) 和 *(++it)也是不一样的。尽管有括号。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+233;
map<int,int> hm;
set<int> st;
int n;
int k[maxn]={0};
int main()
{
    scanf("%d",&n);
    scanf("%d",&k[1]);
    st.insert(k[1]);
    hm[k[1]]=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&k[i]);
        st.insert(k[i]);
        
Read the rest Read More
| by XianKa | No comments

【栈/CF534B】Game with string

http://codeforces.com/contest/1104/problem/B

题意:
给定一串小写字母序列,每次取连着的两个相同字母,直到无法取为止

 

用栈来做。

由于必须取连着的两个,所以依次进栈,遇到和栈顶相同的就弹出,同时把取的次数+1

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+233;
char ss[maxn];
stack<int> prs;
int cond=0;
int main()
{
    scanf("%s",ss);
    int len=strlen(ss);
    prs.push(ss[0]);
    for(int i=1;i<len;i++)
    {
        if(!prs.empty()&&prs.top()==ss[i])
        {
            prs.pop();
            cond++;
        }
        else
        {
            prs.push(ss[i]);
        }   
    }
    printf("%s",(cond%2==1)?"Yes":"No");
}

 … Read the rest

Read More