链接：

来源：牛客网

找一找

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数

输入描述:

第一行输入一个n

接下来一行输入n个正整数a

_i

输出描述:

输出符合条件个数

示例1

输入

51 2 3 4 5

输出

2

说明

5个数中1和2符合条件，1是后面每个数的因子，2是4的因子

备注:

1≤n,a

_i

≤1000000

---

这个就是利用埃筛的思想枚举就可以了，1需要的次数比较多，特判下吧

还可以离散化，应该跑的更快

#include 
       
        using namespace std;const int N=1e6+5;int b[N],a[N],sum;int main(){    ios::sync_with_stdio(false);    int n;    cin>>n;    for(int i=0; i
        
         >a[i],b[a[i]]=1;    for(int i=0; i
        
       

链接：

来源：牛客网

列一列

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

小W在计算一个数列{A

_n},其中A

₁=1,A

₂=2,A

_n+2=A

_n+1+A

_n。尽管他计算非常精准，但很快他就弄混了自己的草稿纸，他找出了一些他计算的结果，但他忘记了这些都是数列中的第几项。

输入描述:

每行包括数列中的一项A_k(k<=100000)。

总行数T<=30。

输出描述:

对于每一项A_k，输出一行包括一个正整数k表示输入中数是数列的第几项。

示例1

输入

235813

输出

23456

---

循环节是这样

并不一定我代码能过，等等我的逻辑好像有问题，应该要有冲突的?还是py直接写吧，不难

#include
             
              using namespace std;const int MD=1e8+7,N=1e5+5;int ans[N];unordered_map
              
               M;int main(){    ans[0]=ans[1]=1;    for(int i=2; i
               
                >s)    {        int ans=0;        for(int i=0; s[i]; ++i)            ans=ans*10+(s[i]-'0'),ans%=MD;        printf("%d\n",M[ans]);    }    return 0;}
               
              
             

 

好吧，写错了，这么多冲突的，1e9+7只有一个冲突，特判下还是可以的

py代码

ans = []M = {}ans.append(1)M[1] = 1ans.append(2)M[2] = 2for i in range(100000):    ans.append(ans[-1] + ans[-2])    M[ans[-1]] = len(ans)while True:    try:        n = input()        if n:            print(M[int(n)])    except EOFError:        break

 链接：

来源：牛客网

造一造

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

WYF正试图用一个栈来构造一棵树，现在他已经构造了n个元素作为树的节点，只要将这n个元素依次入栈出栈就可以形成一棵树了。当然，这个问题与树并没有关系，所以它叫做WYF的栈。每次你可以入栈一个新元素或者当栈非空时出栈一个元素，n个元素必须依次入栈，而WYF希望其中第m个元素入栈之后，栈中恰好有k个元素，现在他想知道一共有多少种入栈出栈顺序满足这个条件。

输入描述:

第一行一个正整数T，表示数据组数。(1<=T<=10000) 对于每组数据包含一行三个正整数n,m,k。

输出描述:

 对于每组数据输出一个正整数表示答案。

 由于答案可能过大，所以只需要输出对10

⁹+7取模后的答案

 

示例1

输入

23 3 33 3 2

输出

12

示例2

输入

510 3 210 2 210 7 510 6 210 7 6

输出

68641193422003780924

示例3

输入

25 4 45 2 1

输出

514

备注:

1<=n,m,k<=10

⁶

n次入栈m次出栈的合法排列次数则可参考卡特兰数公式。C(n+m,m)-C(n+m,m-1)

#include
               
                using namespace std;const int MD=1e9+7,N=2e6+5;int f[N],v[N];int C(int n,int m){    if(m<0||m>n) return 0;    return 1LL*f[n]*v[m]%MD*v[n-m]%MD;}int F(int n,int m){    return (C(n+m,m)-C(n+m,m-1)+MD)%MD;}int main(){    v[0]=v[1]=f[0]=f[1]=1;    for(int i=2; i
               

看了另一个聚聚是处理倒着的逆元，骚的

inv[i]=inv[p%i]*(p-p/i)%p递推得到逆元

invf[i]=invf[i+1]*(i+1)%p这个公式反递推得到1！~n!的逆元

C(n,m)=A(n,m)/m!=n!/(m!*(n-m)!)所以C(n,m)=C(n,n-m)

所以C(n+m,m)-C(n+m,m-1)=C(n+m,(n+m)-n))-C(n+m,(n+m)-(m-1))=C(n+m,n)-C(n+m,n+1)

#include
               
                using namespace std;const int MD=1e9+7,N=2e6+5;int INV(int x){    return x==1?x:1LL*(MD-MD/x)*INV(MD%x)%MD;}int f[N],v[N];int C(int n,int m){    if(m<0||m>n) return 0;    return 1LL*f[n]*v[m]%MD*v[n-m]%MD;}int F(int n,int m){    return (C(n+m,n)-C(n+m,n+1)+MD)%MD;}int main(){    f[0]=1;    for (int i=1; i
                
                 =0; i--) v[i]=v[i+1]*(i+1LL)%MD;    int n,m,k,T;    scanf("%d",&T);    while (T--)    {        scanf("%d%d%d",&n,&m,&k);        printf("%d\n",1LL*F(m-1,m-k)*F(n-m+k,n-m)%MD);    }    return 0;}
                
               

 链接：

来源：牛客网

数一数

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

设s,t为两个字符串，定义f(s,t) = t的子串中，与s相等的串的个数。如f("ac","acacac")=3, f("bab","babab")=2。现在给出n个字符串，第i个字符串为s

_i。你需要对

，求出

，由于答案很大，你只需要输出对 998244353取模后的结果。

输入描述:

第一行一个整数n。 接下来n行每行一个仅由英文字母构成的非空字符串，第i个字符串代表s

_i

。

输出描述:

共n行，第i行输出

对 998244353取模的结果。

示例1

输入

1BALDRSKYKirishimaRain

输出

1

备注:

1 ≤ n ≤ 10

⁶

，所有字符串的总长度不超过2*10

⁶

B可以KMP 看毛片啊

找到最长的串KMP得到pre的前缀处理，然后对每个字符串进行贡献求积

#include 
                  
                   using namespace std;const int N=1e6+5,MD=998244353;string s[N];int f[N+N];int main(){    int n,mi=N+N,ff,ans=1;    cin>>n;    for(int i=0; i
                   
                    >s[i];        if(s[i].size()
                   
                  

 链接：

来源：牛客网

组一组

时间限制：C/C++ 3秒，其他语言6秒

空间限制：C/C++ 65536K，其他语言131072K

Special Judge, 64bit IO Format: %lld

题目描述

有一个长为 n 的数列 A，其中有 m 个限制条件，条件有两种：

1、对于区间 [l,r]，其区间元素按位或和等于 x

2、对于区间 [l,r]，其区间元素按位与和等于 x

求出一个数列 A，使得满足给定的 m 个条件，保证有解。

输入描述:

输入第一行两个正整数 n,m，意义如上 接下来 m 行，每行四个整数 op,l,r,x，表示一组限制 op = 1 表示是限制 1，op = 2 表示是限制 2

输出描述:

输出仅一行，n 个整数 a

_i

表示数列 A。要求 0 <= a

_i

< 10

⁹

示例1

输入

4 3 1 1 2 9 2 3 4 2 1 2 3 11

输出

1 9 2 6

备注:

1<=n,m<=10^5, 1<=l<=r<=n, 0<=x<2^20

---

有3维BIT的，竟然还有一个dij的写法，666

#include
                    
                     #include
                     
                      #include
                      
                       const int N=1e5+5;int n,m,a[N],d[N];int op[N],L[N],R[N],x[N];int cnt,head[N];struct Edge {    int to,nxt,len;}edge[N<<3];void init() {    for(int i=0;i<=n;i++) head[i]=-1;cnt=0;}void addEdge(int from,int to,int len) {    edge[cnt].to=to;edge[cnt].len=len;edge[cnt].nxt=head[from];head[from]=cnt++;}struct Node {    int p,len;    Node(int p=0,int len=0):p(p),len(len){}    bool operator < (const Node &b) const {        return len>b.len;    }};std::priority_queue
                       
                         q;void dijkstra() {    for(int i=1;i<=n;i++) d[i]=N;    d[0]=0;q.push(Node(0,0));    while(!q.empty()) {        Node c=q.top();q.pop();        if(d[c.p]
                        
                         w) d[v]=w,q.push(Node(v,d[v]));        }    }}void solve(int k) {    init();    for(int i=1;i<=m;i++) {        if(op[i]==1) {            if(x[i]>>k&1) addEdge(R[i],L[i]-1,-1);            else addEdge(L[i]-1,R[i],0),addEdge(R[i],L[i]-1,0);        }        else {            if(x[i]>>k&1) addEdge(L[i]-1,R[i],R[i]-L[i]+1),addEdge(R[i],L[i]-1,L[i]-1-R[i]);            else addEdge(L[i]-1,R[i],R[i]-L[i]);        }    }    for(int i=1;i<=n;i++) addEdge(i,i-1,0),addEdge(i-1,i,1);    dijkstra();    for(int i=1;i<=n;i++) a[i]|=(d[i]-d[i-1])<