2017百度之星资格赛&&cf edu26-D

自用笔记算法

2017百度之星资格赛&&cf edu26-D

cf edu26-D

题目要求

有n个元素的数组 从中选k个 使得选中的数字乘积末尾的0最多

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int dp[205][20005];
int get2(LL x){
	int ans=0;
	while(x%2==0){
		x/=2;
		ans++;
	}
	return ans;
}
int get5(LL x){
	int ans=0;
	while(x%5==0){
		x/=5;
		ans++;
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,k;
	cin>>n>>k;
	mm(dp,-inf); dp[0][0]=0;
	for(int t=1;t<=n;t++){
		LL x;
		cin>>x;
		int num2=get2(x);
		int num5=get5(x);
		for(int i=k;i>=1;i--){
			for(int j=num2;j<=20000;j++){
				dp[i][j]=max(dp[i][j],dp[i-1][j-num2]+num5);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=20000;i++){
		ans=max(ans,min(i,dp[k][i]));
	}
	cout<<ans<<endl;
	return 0;
}

思路

末尾0的个数可以转化为因数2和因数5的个数
dp：dp[i][j]表示选择了i个数，且这i个数质因子中2的个数和为j时,质因子中5的个数和的最大值。
状态转移方程为：dp[j][l]=max(dp[j][l],dp[j-1][l-n2]+n5);
最后扫一遍即可(注意取2的个数与5的个数其中的较小值)

2017Astar 1002

题目要求

Problem Description

度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。
哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。
所以这一场战争，将会十分艰难。
为了更好的进攻哗啦啦族，度度熊决定首先应该从内部瓦解哗啦啦族。
第一步就是应该使得哗啦啦族内部不能同心齐力，需要内部有间隙。
哗啦啦族一共有n个将领，他们一共有m个强关系，摧毁每一个强关系都需要一定的代价。
现在度度熊命令你需要摧毁一些强关系，使得内部的将领，不能通过这些强关系，连成一个完整的连通块，以保证战争的顺利进行。
请问最少应该付出多少的代价。

Input
本题包含若干组测试数据。
第一行两个整数n，m，表示有n个将领，m个关系。
接下来m行，每行三个整数u,v,w。表示u将领和v将领之间存在一个强关系，摧毁这个强关系需要代价w
数据范围：
2<=n<=3000
1<=m<=100000
1<=u,v<=n
1<=w<=1000

Output
对于每组测试数据，输出最小需要的代价。

Sample Input
2 1
1 2 1
3 3
1 2 5
1 2 4
2 3 3

Sample Output
1
3

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
#define maxn 3050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int g[maxn][maxn];
int n,m;
void Mincut(){
    int res=inf;
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            if(i!=j) sum+=g[i][j];
        }
        res=min(res,sum);
    }
    printf("%d\n",res);
}
int p[maxn];
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
} 
void merge(int u,int v){
    int x=find(u);
    int y=find(v);
    if(x!=y) p[x]=y;
}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(cin>>n>>m){
        mm(g,0);
        for(int i=1;i<maxn;i++) p[i]=i;
        for(int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            g[u][v]+=w;
            g[v][u]+=w;
            merge(u,v);    
        }
        int count=0;
        for(int i=1;i<=n;i++){
            if(p[i]==i) count++;
            if(count>1) break;
        }
        if(count>1) cout<<"0"<<endl;
        else Mincut(); 
    }
    return 0;
}

思路

正解应该为最小割 但是过不掉 数据问题
AC思路为：先用并查集判断原图是否联通 不联通直接输出0 否则孤立每个点 把所有连接到该点的边权相加 维护最小值
注意边权要累加

2017Astar 1003

题目要求

Problem Description
度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。
邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。
度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石，造成p[i]点伤害。
当然，如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。
如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。
当然每个技能都可以使用无限次。
请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。

Input
本题包含若干组测试数据。
第一行两个整数n，m,表示有n个怪兽，m种技能。
接下来n行，每行两个整数，a[i],b[i]，分别表示怪兽的生命值和防御力。
再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。
数据范围:
1<=n<=100000
1<=m<=1000
1<=a[i]<=1000
0<=b[i]<=10
0<=k[i]<=100000
0<=p[i]<=1000

Output
对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1

Sample Input
1 2
3 5
7 10
6 8
1 2
3 5
10 7
8 6

Sample Output
6
18

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
LL a[maxn],b[maxn];
LL k[1050],p[1050]; 
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    while(cin>>n>>m){
        for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
        for(int i=1;i<=m;i++) cin>>k[i]>>p[i];
        LL ans=0;
        LL dp[2100][15];
        for(int i=1;i<=2050;i++){
            for(int j=0;j<=10;j++) dp[i][j]=INF;
        }
        for(int i=0;i<=10;i++) dp[0][i]=0;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=10;j++){
                int harm=p[i]-j;
                if(harm<=0) continue;
                for(int v=harm;v<=2050;v++){
                    dp[v][j]=min(dp[v][j],dp[v-harm][j]+k[i]);
                }
            }
        }
        for(int i=1000;i<=2050;i++){
            for(int j=0;j<=10;j++) dp[1000][j]=min(dp[1000][j],dp[i][j]);
        }
        for(int i=999;i>=1;i--){
            for(int j=0;j<=10;j++) dp[i][j]=min(dp[i][j],dp[i+1][j]);
        }
        for(int i=1;i<=n;i++){
            if(dp[a[i]][b[i]]==INF){
                ans=-1;
                break;
            }
            else ans+=dp[a[i]][b[i]];
        }
        cout<<ans<<endl;
    }
    return 0;
}

思路

背包dp
dp[i][j]表示攻击血量为i 防御为j的怪物携带的最小晶石
注意开LL以及攻击溢出的情况(伤害i+1的血量可能比伤害i的血量消耗的晶石要少)
所以dp更新完后 再逆序更新维护最小值

2017Astar 1004

题目要求

Problem Description
度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。
百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。
但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)

Input
第一行一个整数T，表示T组数据。 每组测试数据将以如下格式从标准输入读入：
B
N
score_1 cost_1
score_2 cost_2
:
score_N cost_N
第一行，正整数B（0 <= B <= 1000），代表午餐的预算。
第二行，正整数N (0 <= N <= 100)，代表午餐可选的菜品数量
从第三行到第 (N + 2) 行，每行两个正整数，以空格分隔，score_i表示菜品的得分，cost_i表示菜品的价格(0 <= score_i, cost_i <= 100)。

Output
对于每组数据，输出两行： 第一行输出：”Case #i:”。i代表第i组测试数据。 第二行输出菜品的总得分和总花费，以空格分隔。 第三行输出所选菜品的序号，菜品序号从1开始，以空格分隔。

Sample Input
2
29
6
9 10
3 4
6 5
7 20
10 9
15 11
0
2
2 23
10 12

Sample Output
Case #1:
34 29
2 3 5 6
Case #2:
0 0

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int value[maxn],cost[maxn];
int b,n;
int flag=1;
int dp1[1050],dp2[1050];
vector<int>e;
int dish[105][1050]; 
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t; cin>>t;
    while(t--){
        e.clear();
        cin>>b>>n;
        for(int i=1;i<=n;i++) cin>>value[i]>>cost[i];
        cout<<"Case #"<<flag++<<":"<<endl;
        mm(dp1,0),mm(dp2,inf),mm(dish,0);
        for(int i=1;i<=n;i++){
            for(int j=b;j>=cost[i];j--){
                if(dp1[j]<dp1[j-cost[i]]+value[i] || (dp1[j]==dp1[j-cost[i]]+value[i] && dp2[j]>dp2[j-cost[i]]+i)){
                    dp1[j]=dp1[j-cost[i]]+value[i];
                    dp2[j]=dp2[j-cost[i]]+i;
                    dish[i][j]=1;
                }
            }
        }
        int s=b,total=0;
        for(int i=n;i>=1;i--){
            if(dish[i][s]){
                total+=cost[i];
                s-=cost[i];
                e.pb(i);
            }
        }
        cout<<dp1[b]<<" "<<total<<endl;
        int len=e.size();
        for(int i=len-1;i>=0;i--){
            if(i==0) cout<<e[i];
            else cout<<e[i]<<" ";
        }
        if(e.size()>0) cout<<endl;
    }    
    return 0;
}

思路

类似于输出01背包字典序顺序
注意为了使得菜品的序列好最小 再开一个dp2来维护dp1 若dp1更新时同步更新dp2 若dp1相同但是dp2可以获得更小的字典序 同步更新dp1和dp2
dish记录位置 输出字典序即可

2017Astar 1005

题目要求

Problem Description
对于一个串S，当它同时满足如下条件时，它就是一个01偏串：
1、只由0和1两种符组成；
2、在S的每一个前缀中，0的个数不超过1的个数；
3、S中0的个数和1的个数相等。
现在给定01偏串S，请计算一下S在所有长度为n的01偏串中作为子串出现的次数的总和。
由于结果比较大，结果对1e9+7取余后输出。
样例解释：
在第二个样例中，长度为4的偏串共两个1010，1100。10在1010中出现了两次，在1100中出现了1次。所以答案是3。

Input
第一行给出一个整数T(1<=T<=40),表示测试数据的数目。
每一组测试包含一个整数n和字符串S，中间用空格分开。(1<=|S|<=100000，1<=n<=1000000000)
输入保证S是一个01偏串。

Output
对于每一组数据，输出一个整数占一行，表示答案。

Sample Input
2
2 10
4 10

Sample Output
1
3

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
//LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
LL fac[] = {1, 641102369, 578095319, 5832229, 259081142, 974067448, 316220877, 690120224, 251368199, 980250487, 682498929, 
	134623568, 95936601, 933097914, 167332441, 598816162, 336060741, 248744620, 626497524, 288843364, 491101308, 245341950, 
	565768255, 246899319, 968999, 586350670, 638587686, 881746146, 19426633, 850500036, 76479948, 268124147, 842267748, 
	886294336, 485348706, 463847391, 544075857, 898187927, 798967520, 82926604, 723816384, 156530778, 721996174, 299085602, 
	323604647, 172827403, 398699886, 530389102, 294587621, 813805606, 67347853, 497478507, 196447201, 722054885, 228338256, 
	407719831, 762479457, 746536789, 811667359, 778773518, 27368307, 438371670, 59469516, 5974669, 766196482, 606322308, 86609485, 
	889750731, 340941507, 371263376, 625544428, 788878910, 808412394, 996952918, 585237443, 1669644, 361786913, 480748381, 
	595143852, 837229828, 199888908, 526807168, 579691190, 145404005, 459188207, 534491822, 439729802, 840398449, 899297830, 
	235861787, 888050723, 656116726, 736550105, 440902696, 85990869, 884343068, 56305184, 973478770, 168891766, 804805577, 
	927880474, 876297919, 934814019, 676405347, 567277637, 112249297, 44930135, 39417871, 47401357, 108819476, 281863274, 
	60168088, 692636218, 432775082, 14235602, 770511792, 400295761, 697066277, 421835306, 220108638, 661224977, 261799937, 
	168203998, 802214249, 544064410, 935080803, 583967898, 211768084, 751231582, 972424306, 623534362, 335160196, 243276029, 
	554749550, 60050552, 797848181, 395891998, 172428290, 159554990, 887420150, 970055531, 250388809, 487998999, 856259313, 
	82104855, 232253360, 513365505, 244109365, 1559745, 695345956, 261384175, 849009131, 323214113, 747664143, 444090941, 
	659224434, 80729842, 570033864, 664989237, 827348878, 195888993, 576798521, 457882808, 731551699, 212938473, 509096183, 
	827544702, 678320208, 677711203, 289752035, 66404266, 555972231, 195290384, 97136305, 349551356, 785113347, 83489485, 
	66247239, 52167191, 307390891, 547665832, 143066173, 350016754, 917404120, 296269301, 996122673, 23015220, 602139210, 
	748566338, 187348575, 109838563, 574053420, 105574531, 304173654, 542432219, 34538816, 325636655, 437843114, 630621321, 
	26853683, 933245637, 616368450, 238971581, 511371690, 557301633, 911398531, 848952161, 958992544, 925152039, 914456118, 
	724691727, 636817583, 238087006, 946237212, 910291942, 114985663, 492237273, 450387329, 834860913, 763017204, 368925948, 
	475812562, 740594930, 45060610, 806047532, 464456846, 172115341, 75307702, 116261993, 562519302, 268838846, 173784895, 
	243624360, 61570384, 481661251, 938269070, 95182730, 91068149, 115435332, 495022305, 136026497, 506496856, 710729672, 
	113570024, 366384665, 564758715, 270239666, 277118392, 79874094, 702807165, 112390913, 730341625, 103056890, 677948390,
	 339464594, 167240465, 108312174, 839079953, 479334442, 271788964, 135498044, 277717575, 591048681, 811637561, 353339603, 
	 889410460, 839849206, 192345193, 736265527, 316439118, 217544623, 788132977, 618898635, 183011467, 380858207, 996097969, 
	 898554793, 335353644, 54062950, 611251733, 419363534, 965429853, 160398980, 151319402, 990918946, 607730875, 450718279, 
	 173539388, 648991369, 970937898, 500780548, 780122909, 39052406, 276894233, 460373282, 651081062, 461415770, 358700839, 
	 643638805, 560006119, 668123525, 686692315, 673464765, 957633609, 199866123, 563432246, 841799766, 385330357, 504962686, 
	 954061253, 128487469, 685707545, 299172297, 717975101, 577786541, 318951960, 773206631, 306832604, 204355779, 573592106, 
	 30977140, 450398100, 363172638, 258379324, 472935553, 93940075, 587220627, 776264326, 793270300, 291733496, 522049725, 
	 579995261, 335416359, 142946099, 472012302, 559947225, 332139472, 499377092, 464599136, 164752359, 309058615, 86117128, 
	 580204973, 563781682, 954840109, 624577416, 895609896, 888287558, 836813268, 926036911, 386027524, 184419613, 724205533, 
	 403351886, 715247054, 716986954, 830567832, 383388563, 68409439, 6734065, 189239124, 68322490, 943653305, 405755338, 
	 811056092, 179518046, 825132993, 343807435, 985084650, 868553027, 148528617, 160684257, 882148737, 591915968, 701445829, 
	 529726489, 302177126, 974886682, 241107368, 798830099, 940567523, 11633075, 325334066, 346091869, 115312728, 473718967, 
	 218129285, 878471898, 180002392, 699739374, 917084264, 856859395, 435327356, 808651347, 421623838, 105419548, 59883031, 
	 322487421, 79716267, 715317963, 429277690, 398078032, 316486674, 384843585, 940338439, 937409008, 940524812, 947549662, 
	 833550543, 593524514, 996164327, 987314628, 697611981, 636177449, 274192146, 418537348, 925347821, 952831975, 893732627, 
	 1277567, 358655417, 141866945, 581830879, 987597705, 347046911, 775305697, 125354499, 951540811, 247662371, 343043237, 
	 568392357, 997474832, 209244402, 380480118, 149586983, 392838702, 309134554, 990779998, 263053337, 325362513, 780072518, 
	 551028176, 990826116, 989944961, 155569943, 596737944, 711553356, 268844715, 451373308, 379404150, 462639908, 961812918, 
	 654611901, 382776490, 41815820, 843321396, 675258797, 845583555, 934281721, 741114145, 275105629, 666247477, 325912072, 
	 526131620, 252551589, 432030917, 554917439, 818036959, 754363835, 795190182, 909210595, 278704903, 719566487, 628514947, 
	 424989675, 321685608, 50590510, 832069712, 198768464, 702004730, 99199382, 707469729, 747407118, 302020341, 497196934, 
	 5003231, 726997875, 382617671, 296229203, 183888367, 703397904, 552133875, 732868367, 350095207, 26031303, 863250534, 
	 216665960, 561745549, 352946234, 784139777, 733333339, 503105966, 459878625, 803187381, 16634739, 180898306, 68718097, 
	 985594252, 404206040, 749724532, 97830135, 611751357, 31131935, 662741752, 864326453, 864869025, 167831173, 559214642, 
	 718498895, 91352335, 608823837, 473379392, 385388084, 152267158, 681756977, 46819124, 313132653, 56547945, 442795120, 
	 796616594, 256141983, 152028387, 636578562, 385377759, 553033642, 491415383, 919273670, 996049638, 326686486, 160150665, 
	 141827977, 540818053, 693305776, 593938674, 186576440, 688809790, 565456578, 749296077, 519397500, 551096742, 696628828, 
	 775025061, 370732451, 164246193, 915265013, 457469634, 923043932, 912368644, 777901604, 464118005, 637939935, 956856710, 
	 490676632, 453019482, 462528877, 502297454, 798895521, 100498586, 699767918, 849974789, 811575797, 438952959, 606870929,
	 907720182, 179111720, 48053248, 508038818, 811944661, 752550134, 401382061, 848924691, 764368449, 34629406, 529840945, 
	 435904287, 26011548, 208184231, 446477394, 206330671, 366033520, 131772368, 185646898, 648711554, 472759660, 523696723,
	 271198437, 25058942, 859369491, 817928963, 330711333, 724464507, 437605233, 701453022, 626663115, 281230685, 510650790,
	 596949867, 295726547, 303076380, 465070856, 272814771, 538771609, 48824684, 951279549, 939889684, 564188856, 48527183,
     201307702, 484458461, 861754542, 326159309, 181594759, 668422905, 286273596, 965656187, 44135644, 359960756, 936229527,
	  407934361, 267193060, 456152084, 459116722, 124804049, 262322489, 920251227, 816929577, 483924582, 151834896, 167087470,
	   490222511, 903466878, 361583925, 368114731, 339383292, 388728584, 218107212, 249153339, 909458706, 322908524, 
	   202649964, 92255682, 573074791, 15570863, 94331513, 744158074, 196345098, 334326205, 9416035, 98349682, 882121662, 
	   769795511, 231988936, 888146074, 137603545, 582627184, 407518072, 919419361, 909433461, 986708498, 310317874, 373745190, 
	   263645931, 256853930, 876379959, 702823274, 147050765, 308186532, 175504139, 180350107, 797736554, 606241871, 384547635, 
	   273712630, 586444655, 682189174, 666493603, 946867127, 819114541, 502371023, 261970285, 825871994, 126925175, 701506133,
	    314738056, 341779962, 561011609, 815463367, 46765164, 49187570, 188054995, 957939114, 64814326, 933376898, 329837066, 
	    338121343, 765215899, 869630152, 978119194, 632627667, 975266085, 435887178, 282092463, 129621197, 758245605, 827722926,
	     201339230, 918513230, 322096036, 547838438, 985546115, 852304035, 593090119, 689189630, 555842733, 567033437, 
	     469928208, 212842957, 117842065, 404149413, 155133422, 663307737, 208761293, 206282795, 717946122, 488906585, 414236650, 
	     280700600, 962670136, 534279149, 214569244, 375297772, 811053196, 922377372, 289594327, 219932130, 211487466, 701050258, 
	     398782410, 863002719, 27236531, 217598709, 375472836, 810551911, 178598958, 247844667, 676526196, 812283640, 863066876, 
	     857241854, 113917835, 624148346, 726089763, 564827277, 826300950, 478982047, 439411911, 454039189, 633292726, 48562889,
	     802100365, 671734977, 945204804, 508831870, 398781902, 897162044, 644050694, 892168027, 828883117, 277714559, 713448377,
	     624500515, 590098114, 808691930, 514359662, 895205045, 715264908, 628829100, 484492064, 919717789, 513196123, 748510389,
        403652653, 574455974, 77123823, 172096141, 819801784, 581418893, 15655126, 15391652, 875641535, 203191898, 
        264582598, 880691101, 907800444, 986598821, 340030191, 264688936, 369832433, 785804644, 842065079, 423951674, 
        663560047, 696623384, 496709826, 161960209, 331910086, 541120825, 951524114, 841656666, 162683802, 629786193, 
        190395535, 269571439, 832671304, 76770272, 341080135, 421943723, 494210290, 751040886, 317076664, 672850561, 
        72482816, 493689107, 135625240, 100228913, 684748812, 639655136, 906233141, 929893103, 277813439, 814362881, 
        562608724, 406024012, 885537778, 10065330, 60625018, 983737173, 60517502, 551060742, 804930491, 823845496, 
        727416538, 946421040, 678171399, 842203531, 175638827, 894247956, 538609927, 885362182, 946464959, 116667533, 
        749816133, 241427979, 871117927, 281804989, 163928347, 563796647, 640266394, 774625892, 59342705, 256473217, 
        674115061, 918860977, 322633051, 753513874, 393556719, 304644842, 767372800, 161362528, 754787150, 627655552, 
        677395736, 799289297, 846650652, 816701166, 687265514, 787113234, 358757251, 701220427, 607715125, 245795606, 
        600624983, 10475577, 728620948, 759404319, 36292292, 491466901, 22556579, 114495791, 647630109, 586445753, 482254337,
        718623833, 763514207, 66547751, 953634340, 351472920, 308474522, 494166907, 634359666, 172114298, 865440961, 
        364380585, 921648059, 965683742, 260466949, 117483873, 962540888, 237120480, 620531822, 193781724, 213092254, 
        107141741, 602742426, 793307102, 756154604, 236455213, 362928234, 14162538, 753042874, 778983779, 25977209, 49389215,
        698308420, 859637374, 49031023, 713258160, 737331920, 923333660, 804861409, 83868974, 682873215, 217298111, 
        883278906, 176966527, 954913, 105359006, 390019735, 10430738, 706334445, 315103615, 567473423, 708233401, 48160594, 
        946149627, 346966053, 281329488, 462880311, 31503476, 185438078, 965785236, 992656683, 916291845, 881482632, 
	    899946391, 321900901, 512634493, 303338827, 121000338, 967284733, 492741665, 152233223, 165393390, 680128316, 
	    917041303, 532702135, 741626808, 496442755, 536841269, 131384366, 377329025, 301196854, 859917803, 676511002, 373451745, 
	    847645126, 823495900, 576368335, 73146164, 954958912, 847549272, 241289571, 646654592, 216046746, 205951465, 3258987, 
	    780882948, 822439091, 598245292, 869544707, 698611116, 0};
const LL M=1e6;
LL get(LL x){
    if(x>=mod) return 0;
    if(x==0) return 1;
    LL res=fac[x/M]%mod;
    for(LL i=x/M*M+1;i<=x;i++){
        res=res*i%mod;
    }
    return res;
}
LL qpow(LL n,LL m){
    LL res = 1;
    while(m){
        if(m&1) res = res*n%mod;
        n = n*n%mod;
        m >>= 1;
    }
    return res;
}
LL solve(LL x){
    LL a=get(2*x+1),b=get(x+1),c=get(x);
    b=qpow(b,mod-2),c=qpow(c,mod-2);
    return a*b%mod*c%mod;
}
char s[100050]; 
int main(){
//    freopen("input.txt","r",stdin);
    int t; scanf("%d",&t);
    while(t--){
        LL n;
        scanf("%I64d%s",&n,s);
        LL len=strlen(s);
        if((n-len)&1 || (n-len)<0) puts("0");
        else printf("%I64d\n",solve((n-len)/2));
    }
    return 0;
}
//http://www.cnblogs.com/fancy-itlife/p/4312170.html lucas定理转跳
//blog.csdn.net/WuBaizhe/article/details/76820871 本题详细题解转跳

思路

卡特兰数变形+组合数取模
AC代码用的是分块打表解决组合数取模的问题 组合数取模当mod比较小时 还可以用LUCAS定理

本文标题:2017百度之星资格赛&&cf edu26-D

文章作者:Hippopmonkey

发布时间:2017-08-06, 17:56:31

最后更新:2017-08-14, 10:40:43

原始链接:http://xuboming8.github.io/2017/08/06/2017百度之星-cf-edu26-D/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2017百度之星资格赛&&cf edu26-D
    1. 1.1. cf edu26-D
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. 2017Astar 1002
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. 2017Astar 1003
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. 2017Astar 1004
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. 2017Astar 1005
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|