複数校9
7965 ワード
Arithmetic Sequence
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
A sequence
b1,b2,⋯,bn are called
(d1,d2)-arithmetic sequence if and only if there exist
i(1≤i≤n) such that for every
j(1≤jj(i≤jTeacher Mai has a sequence
a1,a2,⋯,an. He wants to know how many intervals
[l,r](1≤l≤r≤n) there are that
al,al+1,⋯,ar are
(d1,d2)-arithmetic sequence.
Input
There are multiple test cases.
For each test case, the first line contains three numbers
n,d1,d2(1≤n≤105,|d1|,|d2|≤1000), the next line contains
n integers
a1,a2,⋯,an(|ai|≤109).
Output
For each test case, print the answer.
Sample Input
Statistic | Submit | Clarifications | Back
Too Simple
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 429 Accepted Submission(s): 83
Problem Description
Rhason Cheung had a simple problem, and asked Teacher Mai for help. But Teacher Mai thought this problem was too simple, sometimes naive. So she ask you for help.
Teacher Mai has
m functions
f1,f2,⋯,fm:{1,2,⋯,n}→{1,2,⋯,n}(that means for all
x∈{1,2,⋯,n},f(x)∈{1,2,⋯,n}). But Rhason only knows some of these functions, and others are unknown.
She wants to know how many different function series
f1,f2,⋯,fm there are that for every
i(1≤i≤n),
f1(f2(⋯fm(i)))=i. Two function series
f1,f2,⋯,fm and
g1,g2,⋯,gm are considered different if and only if there exist
i(1≤i≤m),j(1≤j≤n),
fi(j)≠gi(j).
Input
For each test case, the first lines contains two numbers
n,m(1≤n,m≤100).
The following are
m lines. In
i-th line, there is one number
−1 or
n space-separated numbers.
If there is only one number
−1, the function
fi is unknown. Otherwise the
j-th number in the
i-th line means
fi(j).
Output
For each test case print the answer modulo
109+7.
Sample Input
Statistic | Submit | Clarifications | Back
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
A sequence
b1,b2,⋯,bn are called
(d1,d2)-arithmetic sequence if and only if there exist
i(1≤i≤n) such that for every
j(1≤j
a1,a2,⋯,an. He wants to know how many intervals
[l,r](1≤l≤r≤n) there are that
al,al+1,⋯,ar are
(d1,d2)-arithmetic sequence.
Input
There are multiple test cases.
For each test case, the first line contains three numbers
n,d1,d2(1≤n≤105,|d1|,|d2|≤1000), the next line contains
n integers
a1,a2,⋯,an(|ai|≤109).
Output
For each test case, print the answer.
Sample Input
5 2 -2 0 2 0 -2 0 5 2 3 2 3 3 3 3
Sample Output
12 5
#include
#include
#include
using namespace std;
#define N 100000 + 5
#define LL long long
int a[N];
int D1[N], D2[N];
int d1, d2;
int n;
int main()
{
while(~scanf("%d%d%d", &n, &d1, &d2))
{
for(int i = 1; i <= n; i++)
scanf("%d", a + i);
D1[1] = D2[1] = 1;
int cn1 = 1, cn2 = 1;
for(int i = 2; i <= n; i++)
{
if(a[i] == a[i - 1] + d1)
cn1++;
else cn1 = 1;
D1[i] = cn1;
if(a[i] == a[i - 1] + d2)
cn2++;
else
cn2= 1;
D2[i] = cn2;
}
// for(int i = 1; i <= n; i++)
// cout<= 2)
{
ans += D1[i];
}
else if(D2[i] >= 2)
{
int t = i - D2[i] + 1;
ans += (D1[t] + D2[i] - 1);
//cout< Too Simple
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 429 Accepted Submission(s): 83
Problem Description
Rhason Cheung had a simple problem, and asked Teacher Mai for help. But Teacher Mai thought this problem was too simple, sometimes naive. So she ask you for help.
Teacher Mai has
m functions
f1,f2,⋯,fm:{1,2,⋯,n}→{1,2,⋯,n}(that means for all
x∈{1,2,⋯,n},f(x)∈{1,2,⋯,n}). But Rhason only knows some of these functions, and others are unknown.
She wants to know how many different function series
f1,f2,⋯,fm there are that for every
i(1≤i≤n),
f1(f2(⋯fm(i)))=i. Two function series
f1,f2,⋯,fm and
g1,g2,⋯,gm are considered different if and only if there exist
i(1≤i≤m),j(1≤j≤n),
fi(j)≠gi(j).
Input
For each test case, the first lines contains two numbers
n,m(1≤n,m≤100).
The following are
m lines. In
i-th line, there is one number
−1 or
n space-separated numbers.
If there is only one number
−1, the function
fi is unknown. Otherwise the
j-th number in the
i-th line means
fi(j).
Output
For each test case print the answer modulo
109+7.
Sample Input
3 3 1 2 3 -1 3 2 1
Sample Output
1HintThe order in the function series is determined. What she can do is to assign the values to the unknown functions.
#include
#include
#include
using namespace std;
#define N 100 + 5
#define LL long long
const int mod = 1000000000 + 7;
int n, m;
int f[N][N];
int cnt;
int mul_pow(int a, int k)
{
int res = 1;
while(k)
{
if(k & 1)
res = ((long long)res * a) % mod;
a = ((long long)a * a) % mod;
k >>= 1;
}
return res;
}
int fact(int a)
{
int res = 1;
for(int i = 1; i <= a; i++)
res = ((LL)res * i) % mod;
return res;
}
bool h[N];
int op[N];
int main()
{
while(~scanf("%d%d", &n, &m))
{
memset(op, 0, sizeof op);
int t;
cnt = 0;
for(int i = 1; i <= m; i++)
{
scanf("%d", &t);
if(t == -1) {
op[i] = 1;
cnt++;
}
else
{
f[i][1] = t;
for(int j = 2; j <= n; j++)
scanf("%d", &f[i][j]);
}
}
int flag = 0;
for(int i = 1; i <= m; i++)
{
memset(h, false, sizeof h);
if(op[i] == 0)
for(int j = 1; j <= n; j++)
{
t = f[i][j];
if(h[t] || t > n || t <= 0)
{
//cout<= 1; j--)
t = f[j][t];
if(t != i)
{
flag = 1;
break;
}
}
if(flag) printf("0
");
else printf("1
");
}
else
{
t = fact(n);
int ans = mul_pow(t, cnt - 1);
printf("%d
", ans);
}
}
return 0;
}