All X
Accepts: 1281
Submissions: 7580
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
F(x, m)F(x,m) 代表一個全是由數字xx組成的mm位數字。請計算，以下式子是否成立：
F(x,m)\ mod\ k\ \equiv \ cF(x,m) mod k ≡ c
Input
第一行一個整數TT，表示TT組資料。 每組測試資料占一行，包含四個數字x,m,k,cx,m,k,c
1\leq x\leq 91≤x≤9
1\leq m\leq 10^{10}1≤m≤1010
0\leq c< k\leq 10,0000≤c<k≤10,000
Output
對于每組資料，輸出兩行： 第一行輸出："Case #i:"。ii代表第ii組測試資料。 第二行輸出“Yes” 或者 “No”，代表四個數字，是否能夠滿足題目中給的公式。
Sample Input
3
1 3 5 2
1 3 5 1
3 5 99 69
Sample Output
Case #1:
No
Case #2:
Yes
Case #3:
Yes Hint
對于第一組測試資料：111 mod 5 = 1，公式不成立，是以答案是”No”，而第二組測試資料中滿足如上公式，是以答案是 “Yes”。
代碼:
1 #include <stdio.h>
2 #include <string.h>
3 #include <algorithm>
4 #include <iostream>
5 #include <iomanip>
6 #include <stdlib.h>
7 using namespace std;
8 int s[10000009];
9 int main()
10 {
11 long long n;
12 cin>>n;
13 long long x,m,k,c;
14 long long num=1;
15 while(n--)
16 {
17 cin>>x>>m>>k>>c;
18
19 s[1]=x%k;
20 int i;
21 for(i=2;i<=10000005;i++)
22 {
23 s[i]=(s[i-1]*10+x)%k;
24 if(s[1]==s[i]) break;
25 }
26 m=m%i;
27 cout<<"Case #"<<num++<<":"<<endl;
28 if(c==s[m]) cout<<"Yes"<<endl;
29 else cout<<"No"<<endl;
30 }
31 return 0;
32 } 瞬間移動
Accepts: 1018
Submissions: 3620
Time Limit: 4000/2000 MS (Java/Others)
有一個無限大的矩形，初始時你在左上角（即第一行第一列），每次你都可以選擇一個右下方格子，并瞬移過去（如從下圖中的紅色格子能直接瞬移到藍色格子），求到第nn行第mm列的格子有幾種方案，答案對10000000071000000007取模。
多組測試資料。
兩個整數n,m(2\leq n,m\leq 100000)n,m(2≤n,m≤100000)
一個整數表示答案
4 5 Copy
10
楊輝三角...找規律... 逆元求組合數 C(m+n-4,m-2) 1 #include <cstdio>
2 #include <cmath>
3 #include <cstring>
4 #include <string>
5 #include <algorithm>
6 #include <queue>
7 #include <map>
8 #include <set>
9 #include <vector>
10 #include <iostream>
11 using namespace std;
12 #define ll long long
13 #define MOD 1000000007
14 int n,m;
15 long long t1[100010],t2[100010];
16
17 long long qpow(long long x,long long k)
18 {
19 long long res = 1;
20 while(k){
21 if(k & 1)
22 res=res*x%MOD;
23 x=x*x%MOD;
24 k>>=1;
25 }
26 return res;
27 }
28 long long inv(long long a,long long x)
29 {
30 return qpow(a,x-2);
31 }
32
33 void init()
34 {
35 t1[0]=t1[1]=1;
36 t2[0]=t2[1]=1;
37 for(int i=2; i<100010; i++){
38 t1[i]= (t1[i-1] * i)%MOD;
39 t2[i]= inv(t1[i],MOD);
40 }
41 }
42
43 long long pro(int n,int m)
44 {
45 if(n < m|| m < 0)
46 return 1;
47 return ((t1[n]*t2[m]) % MOD *t2[n-m]) %MOD;
48 }
49
50 int main()
51 {
52 init();
53 while(scanf("%d%d",&n,&m)!=EOF){
54 long long ans=0;
55 for(int i=0; i<= min(n,m)-2; i++){
56 ans=(ans+ ( pro(n-2,i) * pro(m-2,i)) %MOD) %MOD;
57 }
58 printf("%I64d\n",ans);
59
60 }
61 return 0;
62 } 中位數計數
Accepts: 592
Submissions: 3341
Time Limit: 12000/6000 MS (Java/Others)
中位數定義為所有值從小到大排序後排在正中間的那個數，如果值有偶數個，通常取最中間的兩個數值的平均數作為中位數。
現在有nn個數，每個數都是獨一無二的，求出每個數在多少個包含其的區間中是中位數。
多組測試資料
第一行一個數n(n\leq 8000)n(n≤8000)
第二行nn個數，0\leq0≤每個數\leq 10^{9}≤109,
NN個數，依次表示第ii個數在多少包含其的區間中是中位數。
5
1 2 3 4 5
1 2 3 2 1 
1 #include <cstdio>
2 #include <cmath>
3 #include <cstring>
4 #include <string>
5 #include <algorithm>
6 #include <queue>
7 #include <map>
8 #include <set>
9 #include <vector>
10 #include <iostream>
11 using namespace std;
12
13 const double pi=acos(-1.0);
14 double eps=0.000001;
15
16 int aa[8008];
17 int les[8008];
18 int big[8008];
19 int has[8008+8000];
20 int main()
21 {
22
23
24 int n;
25 while(scanf("%d",&n)!=EOF)
26 {
27 int i,j;
28 for (i=1; i<=n; i++)
29 {
30 scanf("%d",&aa[i]);
31 }
32 for (i=1; i<=n; i++)
33 {
34 long long ans=0;
35 memset(has,0,sizeof has);
36 les[i]=0;
37 big[i]=0;
38 for (j=i-1; j>=1; j--)
39 {
40 if (aa[j]<aa[i]) les[j]=les[j+1]+1;
41 else les[j]=les[j+1];
42 if (aa[j]>aa[i]) big[j]=big[j+1]+1;
43 else big[j]=big[j+1];
44 }
45 for (j=i+1; j<=n; j++)
46 {
47 if (aa[j]<aa[i]) les[j]=les[j-1]+1;
48 else les[j]=les[j-1];
49 if (aa[j]>aa[i]) big[j]=big[j-1]+1;
50 else big[j]=big[j-1];
51 }
52 for (j=i+1; j<=n; j++)
53 {
54 int need_big=les[j]-big[j];
55 has[need_big+8000]++;
56 }
57 has[0+8000]++;
58 for (j=1; j<i; j++)
59 {
60 ans+=has[big[j]-les[j]+8000];
61 }
62 ans+=has[0+8000];
63 if (i>1)printf(" ");
64 printf("%I64d",ans);
65 }
66
67 printf("\n");
68
69
70 }
71
72 return 0;
73
74 } View Code