链接：https://www.nowcoder.com/acm/contest/160/A
来源：牛客网
第一行两个整数n,m1
接下来一行n个整数表示a
,a
2
,...,a
n
1
1≤n≤100
1≤m,a
,a
2
,...,a
n
≤1000000000
输出一个整数表示答案
3
令 g=gcd(a1,a2,,,,,,an) ,显然 (k*g)%m 的不同个数就是答案,观察之后发现这个式子是有循环节的，假设第一次出现循环的
位置是x，也就是说 x*g=0 (mod m) x*g+y*m=0 ,x的解 x=x0+k*(m/gcd(g,m)) ,其实答案就是 m/(gcd(g,m)。
1
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<queue>
6 #include<vector>
7 #include<cstdlib>
8 #include<map>
9 #include<set>
10
11 #include<bits/stdc++.h>
12 using namespace std;
13
14 #define LL long long
15 #define inf 0x3f3f3f3f
16 #define pii pair<int,int>
17 #define pb push_back
18 #define mp make_pair
19 LL gcd(LL a,LL b){
20 return b==0?a:gcd(b,a%b);
21 }
22 int main(){
23 int t,n,m,i,j,k;
24 while(scanf("%d%d",&n,&m)!=EOF){
25 LL ans=m,a;
26 for(i=1;i<=n;++i){
27 scanf("%lld",&a);
28 ans=gcd(ans,a);
29 }
30 cout<<m/ans<<endl;
31 }
32 return 0;
33 }
链接：https://www.nowcoder.com/acm/contest/160/B
来源：牛客网
第一行两个整数n,m
接下来m行，每行两个整数a,b和一个字符c，表示一条起点为a，终点为b的边，边上的字符是c
1 ≤ n, m ≤ 50000
1 ≤ a < b ≤ n
c可以是大小写字母、句号 ‘.‘ 或空格（方便起见用 ‘_‘ 表示空格）
输出一个整数，表示答案对2
32
取模的结果
ps:我想的复杂了，有个更简单的dp是 f[i][0/1/2/3]表示第i个节点结尾的，符号是j类型的合法子串的数目，这样就好写多了>_<.
先对这个DAG进行拓扑排序。
设置四个类型 0-[A-Z] 1-[a-z] 2-[.] 3-[_] f[j][k1][k2]表示以第j个字符结尾的，开头是k1类型,结尾是k2类型的合法串的个数，答案就是SUM{f[i][0][2]}。转移的时候如果多个‘_‘连着算作一个就好了，如果有合法串与"__"拼接，那么直接略去‘_‘即可，也就是说长度大于1的串中不显示‘_‘，单独设置类型4只用作表示开头指代这个状态的子串长度是1.转移的时候我直接枚举所有情况，所以写的很长，其实很多状态都是无用的，但分析起来怕出错就直接写了。我转移的时候忘记了小写字母可以不存在，，比赛结束5min才发现然后1A......
1 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #include<vector> 7 #include<cstdlib> 8 #include<map> 9 #include<set> 10 11 #include<bits/stdc++.h> 12 using namespace std; 13 14 #define LL long long 15 #define inf 0x3f3f3f3f 16 #define pii pair<int,int> 17 #define pb push_back 18 #define mp make_pair 19 #define uint unsigned int 20 uint f[50050][5][5]={0}; 21 vector<pii>e[50050]; 22 vector<int>vi; 23 int in[50050]; 24 void topsort(int n){ 25 queue<int>q; 26 for(int i=1;i<=n;++i){ 27 if(!in[i]) {q.push(i);vi.push_back(i);} 28 } 29 while(!q.empty()){ 30 int u=q.front(); 31 q.pop(); 32 for(int i=0;i<e[u].size();++i){ 33 pii _e=e[u][i]; 34 if(!(--in[_e.first])){ 35 q.push(_e.first); 36 vi.push_back(_e.first); 37 } 38 } 39 } 40 //for(i=0;i<n;++i)cout<<vi[i]<<endl; 41 } 42 void solve(int n){ 43 uint ans=0; 44 for(int i=0;i<n;++i){ 45 int u=vi[i]; 46 for(int j=0;j<e[u].size();++j){ 47 f[e[u][j].first][4][e[u][j].second]++; 48 } 49 for(int k1=0;k1<=4;k1++){ 50 for(int k2=0;k2<4;++k2){ 51 if(f[u][k1][k2]){ 52 //cout<<u<<‘ ‘<<k1<<‘ ‘<<k2<<‘ ‘<<f[u][k1][k2]<<endl; 53 for(int j=0;j<e[u].size();++j){ 54 //cout<<u<<‘ ‘<<e[u][j].first<<endl; 55 uint s=f[u][k1][k2]; 56 if(e[u][j].second==0){ 57 if(k1==4){ 58 if(k2==3) 59 f[e[u][j].first][4][0]+=s; 60 } 61 } 62 else if(e[u][j].second==1){ 63 if(k1==4){ 64 if(k2==0){ 65 f[e[u][j].first][0][1]+=s; 66 } 67 else if(k2==3){ 68 f[e[u][j].first][4][1]+=s; 69 } 70 } 71 else{ 72 if(k1!=0)continue; 73 if(k2==1) 74 f[e[u][j].first][0][1]+=s; 75 } 76 } 77 else if(e[u][j].second==2){ 78 if(k1==4){ 79 if(k2==0){ 80 f[e[u][j].first][0][2]+=s; 81 } 82 } 83 else{ 84 if(k1!=0)continue; 85 if(k2==1){ 86 f[e[u][j].first][0][2]+=s; 87 } 88 } 89 } 90 else{ 91 if(k1==4){ 92 if(k2==0){ 93 f[e[u][j].first][4][0]+=s; 94 } 95 else if(k2==3){ 96 f[e[u][j].first][4][3]+=s; 97 } 98 } 99 else{ 100 if(k1!=0)continue; 101 if(k2==1){ 102 f[e[u][j].first][0][1]+=s; 103 } 104 else if(k2==2){ 105 f[e[u][j].first][0][2]+=s; 106 } 107 } 108 } 109 } 110 } 111 } 112 } 113 } 114 for(int i=1;i<=n;++i)ans+=f[i][0][2]; 115 cout<<ans<<endl; 116 } 117 int main(){ 118 int n,m; 119 int u,v,w; 120 char c; 121 cin>>n>>m; 122 while(m--){ 123 //scanf("%d%d%c",&u,&v,&c); 124 cin>>u>>v>>c; 125 if(c>=‘A‘&&c<=‘Z‘) w=0; 126 else if(c>=‘a‘&&c<=‘z‘) w=1; 127 else if(c==‘.‘) w=2; 128 else w=3; 129 in[v]++; 130 e[u].push_back(mp(v,w)); 131 } 132 topsort(n); 133 solve(n); 134 return 0; 135 }
原文：https://www.cnblogs.com/zzqc/p/9495543.html