Happy new year! The year 2020 is also known as Year Gyeongja (경자년, gyeongja-nyeon) in Korea. Where did the name come from? Let's briefly look at the Gapja system, which is traditionally used in Korea to name the years.
There are two sequences of nn strings s1,s2,s3,…,sns1,s2,s3,…,sn and mm strings t1,t2,t3,…,tmt1,t2,t3,…,tm. These strings contain only lowercase letters. There might be duplicates among these strings.
Let's call a concatenation of strings xx and yy as the string that is obtained by writing down strings xx and yy one right after another without changing the order. For example, the concatenation of the strings "code" and "forces" is the string "codeforces".
The year 1 has a name which is the concatenation of the two strings s1s1 and t1t1. When the year increases by one, we concatenate the next two strings in order from each of the respective sequences. If the string that is currently being used is at the end of its sequence, we go back to the first string in that sequence.
For example, if n=3,m=4,s=n=3,m=4,s={"a", "b", "c"}, t=t= {"d", "e", "f", "g"}, the following table denotes the resulting year names. Note that the names of the years may repeat.
You are given two sequences of strings of size nn and mm and also qq queries. For each query, you will be given the current year. Could you find the name corresponding to the given year, according to the Gapja system?
The first line contains two integers n,mn,m (1≤n,m≤201≤n,m≤20).
The next line contains nn strings s1,s2,…,sns1,s2,…,sn. Each string contains only lowercase letters, and they are separated by spaces. The length of each string is at least 11 and at most 1010.
The next line contains mm strings t1,t2,…,tmt1,t2,…,tm. Each string contains only lowercase letters, and they are separated by spaces. The length of each string is at least 11 and at most 1010.
Among the given n+mn+m strings may be duplicates (that is, they are not necessarily all different).
The next line contains a single integer qq (1≤q≤20201≤q≤2020).
In the next qq lines, an integer yy (1≤y≤1091≤y≤109) is given, denoting the year we want to know the name for.
Print qq lines. For each line, print the name of the year as per the rule described above.
10 12 sin im gye gap eul byeong jeong mu gi gyeong yu sul hae ja chuk in myo jin sa o mi sin 14 1 2 3 4 10 11 12 13 73 2016 2017 2018 2019 2020
sinyu imsul gyehae gapja gyeongo sinmi imsin gyeyu gyeyu byeongsin jeongyu musul gihae gyeongja
The first example denotes the actual names used in the Gapja system. These strings usually are either a number or the name of some animal.
就是对S和T分别循环查找第y个元素，
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define inf 0x3f3f3f3f 5 #define pii pair<int,int> 6 #define pb push_back 7 string S[22],T[22]; 8 int n,m,q,y; 9 int main() 10 { 11 //freopen("in.txt","r",stdin); 12 cin>>n>>m; 13 for(int i=1;i<=n;++i)cin>>S[i]; 14 for(int i=1;i<=m;++i)cin>>T[i]; 15 cin>>q; 16 while(q--){ 17 cin>>y; 18 int s=y%n,t=y%m; 19 if(s==0)s=n; 20 if(t==0)t=m; 21 cout<<S[s]<<T[t]<<endl; 22 } 23 return 0; 24 }
A sequence a=[a1,a2,…,al]a=[a1,a2,…,al] of length ll has an ascent if there exists a pair of indices (i,j)(i,j) such that 1≤i<j≤l1≤i<j≤l and ai<ajai<aj. For example, the sequence [0,2,0,2,0][0,2,0,2,0] has an ascent because of the pair (1,4)(1,4), but the sequence [4,3,3,3,1][4,3,3,3,1] doesn't have an ascent.
Let's call a concatenation of sequences pp and qq the sequence that is obtained by writing down sequences pp and qq one right after another without changing the order. For example, the concatenation of the [0,2,0,2,0][0,2,0,2,0] and [4,3,3,3,1][4,3,3,3,1] is the sequence [0,2,0,2,0,4,3,3,3,1][0,2,0,2,0,4,3,3,3,1]. The concatenation of sequences pp and qq is denoted as p+qp+q.
Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has nn sequences s1,s2,…,sns1,s2,…,sn which may have different lengths.
Gyeonggeun will consider all n2n2 pairs of sequences sxsx and sysy (1≤x,y≤n1≤x,y≤n), and will check if its concatenation sx+sysx+sy has an ascent. Note that he may select the same sequence twice, and the order of selection matters.
Please count the number of pairs (x,yx,y) of sequences s1,s2,…,sns1,s2,…,sn whose concatenation sx+sysx+sy contains an ascent.
The first line contains the number nn (1≤n≤1000001≤n≤100000) denoting the number of sequences.
The next nn lines contain the number lili (1≤li1≤li) denoting the length of sisi, followed by lili integers si,1,si,2,…,si,lisi,1,si,2,…,si,li (0≤si,j≤1060≤si,j≤106) denoting the sequence sisi.
It is guaranteed that the sum of all lili does not exceed 100000100000.
Print a single integer, the number of pairs of sequences whose concatenation has an ascent.
5 1 1 1 1 1 2 1 4 1 3
9
3 4 2 0 2 0 6 9 9 8 8 7 7 1 6
7
10 3 62 24 39 1 17 1 99 1 60 1 64 1 30 2 79 29 2 20 73 2 85 37 1 100
72
For the first example, the following 99 arrays have an ascent: [1,2],[1,2],[1,3],[1,3],[1,4],[1,4],[2,3],[2,4],[3,4][1,2],[1,2],[1,3],[1,3],[1,4],[1,4],[2,3],[2,4],[3,4]. Arrays with the same contents are counted as their occurences.
我的思路是对于每一个数列只记录下他的MAX和MIN元素即可，然后遍历每一个数列，看有哪些数列的最小值是小于当前数列得最大值得，这些数列的个数就是当前数列做的贡献。
注意有些数列本身就是特殊数列了，就把他得MIN和MAX分别记为最小值-1和最大值INF即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define inf 0x3f3f3f3f 5 #define pii pair<int,int> 6 #define pb push_back 7 int minn[100010],maxx[100010]; 8 int sum[1000100]; 9 int main() 10 { 11 //freopen("in.txt","r",stdin); 12 int n,l; 13 cin>>n; 14 for(int i=1;i<=n;++i){ 15 cin>>l; 16 int a,MIN=99999999,MAX=0,ok=0; 17 for(int j=1;j<=l;++j){ 18 scanf("%d",&a); 19 if(a>MIN)ok=1; 20 MIN=min(MIN,a); 21 MAX=max(MAX,a); 22 } 23 minn[i]=MIN; 24 maxx[i]=MAX; 25 if(ok){ 26 minn[i]=-1; 27 maxx[i]=1000002; 28 } 29 sum[minn[i]+1]++; 30 } 31 for(int i=1;i<=1000002;++i)sum[i]+=sum[i-1]; 32 LL ans=0; 33 for(int i=1;i<=n;++i){ 34 ans+=sum[maxx[i]]; 35 } 36 cout<<ans<<endl; 37 return 0; 38 }
Recall that the permutation is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).
A sequence aa is a subsegment of a sequence bb if aa can be obtained from bb by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. We will denote the subsegments as [l,r][l,r], where l,rl,r are two integers with 1≤l≤r≤n1≤l≤r≤n. This indicates the subsegment where l−1l−1 elements from the beginning and n−rn−r elements from the end are deleted from the sequence.
For a permutation p1,p2,…,pnp1,p2,…,pn, we define a framed segment as a subsegment [l,r][l,r] where max{pl,pl+1,…,pr}−min{pl,pl+1,…,pr}=r−lmax{pl,pl+1,…,pr}−min{pl,pl+1,…,pr}=r−l. For example, for the permutation (6,7,1,8,5,3,2,4)(6,7,1,8,5,3,2,4) some of its framed segments are: [1,2],[5,8],[6,7],[3,3],[8,8][1,2],[5,8],[6,7],[3,3],[8,8]. In particular, a subsegment [i,i][i,i] is always a framed segments for any ii between 11 and nn, inclusive.
We define the happiness of a permutation pp as the number of pairs (l,r)(l,r) such that 1≤l≤r≤n1≤l≤r≤n, and [l,r][l,r] is a framed segment. For example, the permutation [3,1,2][3,1,2] has happiness 55: all segments except [1,2][1,2] are framed segments.
Given integers nn and mm, Jongwon wants to compute the sum of happiness for all permutations of length nn, modulo the prime number mm. Note that there exist n!n! (factorial of nn) different permutations of length nn.
The only line contains two integers nn and mm (1≤n≤2500001≤n≤250000, 108≤m≤109108≤m≤109, mm is prime).
Print rr (0≤r<m0≤r<m), the sum of happiness for all permutations of length nn, modulo a prime number mm.
1 993244853
1
2 993244853
6
3 993244853
32
2019 993244853
923958830
2020 437122297
265955509
For sample input n=3n=3, let's consider all permutations of length 33:
- [1,2,3][1,2,3], all subsegments are framed segment. Happiness is 66.
- [1,3,2][1,3,2], all subsegments except [1,2][1,2] are framed segment. Happiness is 55.
- [2,1,3][2,1,3], all subsegments except [2,3][2,3] are framed segment. Happiness is 55.
- [2,3,1][2,3,1], all subsegments except [2,3][2,3] are framed segment. Happiness is 55.
- [3,1,2][3,1,2], all subsegments except [1,2][1,2] are framed segment. Happiness is 55.
- [3,2,1][3,2,1], all subsegments are framed segment. Happiness is 66.
Thus, the sum of happiness is 6+5+5+5+5+6=326+5+5+5+5+6=32.
先考虑长度为len得时候这样的幸福度有多少，此时MAX-MIN=len-1才满足题意，有一个极为重要的点我没发现，就是满足这些的数恰好都是连续的（如12，23，34，123，234，345...）
如果发现了这点就简单多了，len知道以后，不同种类的数有n-len+1种然后剩下考虑如何排列组合就好了，
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 250005; 4 using lint = long long; 5 6 7 using pi = pair<int, int>; 8 9 int n, mod; 10 lint fact[MAXN]; 11 12 int main(){ 13 fact[0] = 1; 14 cin >> n >> mod; 15 for(int i=1; i<=n; i++) fact[i] = fact[i-1] * i % mod; 16 lint ret = 0; 17 for(int i=1; i<=n; i++){ 18 ret += (n - i + 1) * (fact[i] * fact[n - i + 1] % mod); 19 cout<<(n - i + 1) * (fact[i] * fact[n - i + 1] % mod)<<endl; 20 ret %= mod; 21 } 22 cout << ret << endl; 23 }