第二届CCPC女生赛 粗略题解（要做重现的不要看哦）

因为再不全力投入华为软件精英挑战赛就来不及了！

而且直播时讲过题了，所以只能粗略写一个题解，希望大家包涵>.<

基本可以参考代码，可以画图模拟加思考脑补其原理与过程23333~~

会后续有人写题解的啦！感谢参加经费、人员都不足的第二届CCPC女生赛！ 希望明年我也有机会参赛！

06是claris的防AK题，虽然我试图几次想要说服换掉这题。想补的可以找claris或者等几天2333

PS：预测全对

PS2：我真的不会说话和撩妹啊哈哈哈哈          T_____________________________________T

【2017CCPC女生赛 A】【水题 模拟】Automatic Judge

Automatic Judge

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

Welcome to HDU to take part in the second CCPC girls’ competition!
A new automatic judge system is used for this competition. During the five-hour contest time, you can submit your code to the system, then the judge will reply you. Here is a list of the judge's replies and their meaning:

1.  Accepted(AC) : Yes, your program is correct. You did a good job!

2.  PresentationError(PE)  : Your program's output format is not exactly the same as required by the problem, although the output is correct. This usually means the existence of omitted or extra blank characters (white spaces, tab characters and/or new line characters) between any two non-blank characters, and/or blank lines (a line consisting of only blank characters) between any two non-blank lines. Trailing blank characters at the end of each line and trailing blank lines at the of output are not considered format errors. Check the output for spaces, blank lines, etc. against the problem's output specification.

3.  WrongAnswer(WA)  : Correct solution not reached for the inputs. The inputs and outputs that we use to test the programs are not public (it is recomendable to get accustomed to a true contest dynamic :-)

4.  RuntimeError(RE)  : Your program failed during the execution and you will receive the hints for the reasons.

5.  TimeLimitExceeded(TLE)  : Your program tried to run during too much time.

6.  MemoryLimitExceeded(MLE) : Your program tried to use more memory than the judge default settings.

7.  OutputLimitExceeded(OLE) : Your program tried to write too much information. This usually occurs if it goes into a infinite loop.

8.  CompilationError(CE) : The compiler fails to compile your program. Warning messages are not considered errors. Click on the judge's reply to see the warning and error messages produced by the compiler.

For each submission, if it is the first time that the judge returns ``AC'' on this problem, then it means you have passed this problem, and the current time will be added to the penalty of your team. In addition, every time you pass a problem, each unsuccessful try for that problem before is counted as 20 minutes penalty, it should also be added to the penalty of your team.
Now given the number of problems in the contest and the submission records of a team. Please write a program to calculate the number of problems the team passed and their penalty.

 

Input

The first line of the input contains an integer  T(1≤T≤20) , denoting the number of test cases.
In each test case, there are two integers  n(1≤n≤13)  and  m(1≤m≤100)  in the first line, denoting the number of problems and the number of submissions of a team. Problems are labeled by 1001, 1002, ...,  1000+n .
In the following  m  lines, each line contains an integer  x(1001≤x≤1000+n)  and two strings  t(00:00≤t≤05:00)  and  s , denoting the team submits problem  x  at time  t , and the result is  s .  t  is in the format of HH:MM, while  s  is in the set \{AC, PE, WA, RE, TLE, MLE, OLE\}. The team is so cautious that they never submit a CE code. It is guaranteed that all the  t  in the input is in ascending order and every  t  is unique.

 

Output

For each test case, print a single line containing two integers  A  and  B , denoting the number of problems the team passed and the penalty.

 

Sample Input

   
   
  
  

   
   
    
    1
    
    
   
   
3 5
    
    
   
   
1002 00:02 AC
    
    
   
   
1003 00:05 WA
    
    
   
   
1003 00:06 WA
    
    
   
   
1003 00:07 AC
    
    
   
   
1002 04:59 AC
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    2 49
   
   
  
  

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
int cnt[20], ac[20];
int main()
{
	scanf("%d", &casenum);
	for (casei = 1; casei <= casenum; ++casei)
	{
		scanf("%d%d", &n, &m);
		MS(cnt, 0); MS(ac, 0);
		int num = 0;
		int ans = 0;
		for (int i = 1; i <= m; ++i)
		{
			int o, hh, mm; char s[10];
			scanf("%d%d:%d%s", &o, &hh, &mm, s);
			o -= 1000;
			if (!strcmp(s, "AC") && !ac[o])
			{
				ans += cnt[o] * 20 + hh * 60 + mm;
				ac[o] = 1;
				++num;
			}
			else ++cnt[o];
		}
		printf("%d %d\n", num, ans);
	}
	return 0;
}

【2017CCPC女生赛 B】【DP】Building Shops

Building Shops

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

HDU’s  n  classrooms are on a line ,which can be considered as a number line. Each classroom has a coordinate. Now Little Q wants to build several candy shops in these  n  classrooms.

The total cost consists of two parts. Building a candy shop at classroom  i  would have some cost  ci . For every classroom  P  without any candy shop, then the distance between  P  and the rightmost classroom with a candy shop on  P 's left side would be included in the cost too. Obviously, if there is a classroom without any candy shop, there must be a candy shop on its left side.

Now Little Q wants to know how to build the candy shops with the minimal cost. Please write a program to help him.

 

Input

The input contains several test cases, no more than 10 test cases.
In each test case, the first line contains an integer  n(1≤n≤3000) , denoting the number of the classrooms.
In the following  n  lines, each line contains two integers  xi,ci(−109≤xi,ci≤109) , denoting the coordinate of the  i -th classroom and the cost of building a candy shop in it.
There are no two classrooms having same coordinate.

 

Output

For each test case, print a single line containing an integer, denoting the minimal cost.

 

Sample Input

   
   
  
  

   
   
    
    3
    
    
   
   
1 2
    
    
   
   
2 3
    
    
   
   
3 4
    
    
   
   
4
    
    
   
   
1 7
    
    
   
   
3 1
    
    
   
   
5 10
    
    
   
   
6 1
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    5
    
    
   
   
11
   
   
  
  

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 3030, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
pair<int, int> a[N];
LL f[N][N];
int main()
{
	while(~scanf("%d", &n))
	{
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d%d", &a[i].first, &a[i].second);
		}sort(a + 1, a + n + 1);

		MS(f, 63); f[1][1] = a[1].second;
		for (int i = 2; i <= n + 1; ++i)
		{
			//自己不建
			LL mn = 1e18;
			for (int j = 1; j < i; ++j)
			{
				f[i][j] = f[i - 1][j] + a[i].first - a[j].first;
				gmin(mn, f[i - 1][j]);
			}

			if (i == n + 1)
			{
				printf("%lld\n", mn);
				break;
			}

			//自己建
			f[i][i] = mn + a[i].second;
		}
	}
	return 0;
}
/*
【题意】
有n个节点，我们可以选择在每个节点建或不建商店。
对于第i个点，其坐标是a[i].x，建设商店的成本为a[i].c。
每个节点对答案的贡献是——dis（i点的坐标, i向左方向走最近节点的坐标）。
让你安排一个方案，使得"∑所有节点对答案的贡献"尽可能小。

【分析】
显然要按照坐标排序。
用f[i][j]表示我们考虑到第i个点，i向左走，距离i最近的有商店的点是j对应的前缀最小成本。
那么有转移f[i][j] = f[i - 1][j] + dis(i, j);
特别的，如果我们在第i个点建服务器，那么有f[i][i] = max(f[i - 1][j], for all j);
这样在f[n][1~n]中找到答案就好啦

【时间复杂度&&优化】
f(n^2)

*/

【2017CCPC女生赛 C】【暴力】Coprime Sequence

Coprime Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

Do you know what is called ``Coprime Sequence''? That is a sequence consists of  n  positive integers, and the GCD (Greatest Common Divisor) of them is equal to 1.
``Coprime Sequence'' is easy to find because of its restriction. But we can try to maximize the GCD of these integers by removing exactly one integer. Now given a sequence, please maximize the GCD of its elements.

 

Input

The first line of the input contains an integer  T(1≤T≤10) , denoting the number of test cases.
In each test case, there is an integer  n(3≤n≤100000)  in the first line, denoting the number of integers in the sequence.
Then the following line consists of  n  integers  a1,a2,...,an(1≤ai≤109) , denoting the elements in the sequence.

 

Output

For each test case, print a single line containing a single integer, denoting the maximum GCD.

 

Sample Input

   
   
  
  

   
   
    
    3
    
    
   
   
3
    
    
   
   
1 1 1
    
    
   
   
5
    
    
   
   
2 2 2 3 2
    
    
   
   
4
    
    
   
   
1 2 4 8
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    1
    
    
   
   
2
    
    
   
   
2
   
   
  
  
   
   
  
  

    
    
   
   

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
int a[N], bef[N], beh[N];
int gcd(int x, int y)
{
	return y == 0 ? x : gcd(y, x % y);
}
int main()
{
	scanf("%d", &casenum);
	for (casei = 1; casei <= casenum; ++casei)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
		bef[1] = a[1]; for (int i = 2; i <= n; ++i)bef[i] = gcd(bef[i - 1], a[i]);
		beh[n] = a[n]; for (int i = n - 1; i >= 1; --i)beh[i] = gcd(beh[i + 1], a[i]);
		int ans = max(bef[n -  1], beh[2]);
		for (int i = 2; i < n; ++i)gmax(ans, gcd(bef[i - 1], beh[i + 1]));
		printf("%d\n", ans);
	}
	return 0;
}
/*
【题意】
n个数，恰好去掉一个后的最大gcd

【分析】
很常见的套路，暴力枚举去掉的数是哪个，然后前缀后缀max一下就好啦！

*/

【2017CCPC女生赛 D】【最短路+计数】Deleting Edges

Deleting Edges

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

Little Q is crazy about graph theory, and now he creates a game about graphs and trees.
There is a bi-directional graph with  n  nodes, labeled from 0 to  n−1 . Every edge has its length, which is a positive integer ranged from 1 to 9.
Now, Little Q wants to delete some edges (or delete nothing) in the graph to get a new graph, which satisfies the following requirements:
(1) The new graph is a tree with  n−1  edges.
(2) For every vertice  v(0<v<n) , the distance between 0 and  v  on the tree is equal to the length of shortest path from 0 to  v  in the original graph.
Little Q wonders the number of ways to delete edges to get such a satisfied graph. If there exists an edge between two nodes  i  and  j , while in another graph there isn't such edge, then we regard the two graphs different.
Since the answer may be very large, please print the answer modulo  109+7 .

 

Input

The input contains several test cases, no more than 10 test cases.
In each test case, the first line contains an integer  n(1≤n≤50) , denoting the number of nodes in the graph.
In the following  n  lines, every line contains a string with  n  characters. These strings describes the adjacency matrix of the graph. Suppose the  j -th number of the  i -th line is  c(0≤c≤9) , if  c  is a positive integer, there is an edge between  i  and  j  with length of  c , if  c=0 , then there isn't any edge between  i  and  j .
The input data ensure that the  i -th number of the  i -th line is always 0, and the  j -th number of the  i -th line is always equal to the  i -th number of the  j -th line.

 

Output

For each test case, print a single line containing a single integer, denoting the answer modulo  109+7 .

 

Sample Input

   
   
  
  

   
   
    
    2
    
    
   
   
01
    
    
   
   
10
    
    
   
   
4
    
    
   
   
0123
    
    
   
   
1012
    
    
   
   
2101
    
    
   
   
3210
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    1
    
    
   
   
6
   
   
  
  

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 55, M = N * N, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
char s[N][N];
struct node
{
	int x;		//x表示当前点的编号
	int dis;	//dis表示从起点到当前点的距离，注意有时需要LL
	bool operator < (const node&b)const
	{
		return dis > b.dis;
	}
};
struct Dijkstra
{
	int first[N], id;
	struct Edge
	{
		int w, c, nxt;
	}edge[M];
	int f[N];	//f[x]表示从ST到x的最短路
	bool e[N];	//e[x]表示我们是否更新过从ST到x的最短路
	priority_queue<node>q;
	void init()
	{
		for (int i = 1; i <= n; ++i)first[i] = 0;
		id = 1;
	}
	void ins(int x, int y, int z)
	{
		edge[++id] = { y,z,first[x] };
		first[x] = id;
	}
	void inq(int y, int dis)
	{
		if (dis >= f[y])return;
		f[y] = dis;
		q.push({ y,dis });
	}
	void dijkstra()
	{
		LL ans = 1;
		for (int i = 1; i <= n; ++i)
		{
			f[i] = inf;
			e[i] = 0;
		}
		int finish = 0;
		while (!q.empty())q.pop(); inq(1, 0);
		while (!q.empty())
		{
			int x = q.top().x; q.pop();
			if (e[x])continue; e[x] = 1; ++finish;
			if (x != 1)
			{
				int cnt = 0;
				for (int y = 1; y <= n; ++y)if (y != x && e[y] && s[y][x] != '0' && f[y] + s[y][x] - 48 == f[x])++cnt;
				ans = ans * cnt % Z;
			}
			for (int z = first[x]; z; z = edge[z].nxt)
			{
				inq(edge[z].w, f[x] + edge[z].c);
			}
		}
		if (finish != n)ans = 0;
		printf("%lld\n", ans);
	}
}dij;
int main()
{
	while (~scanf("%d", &n))
	{
		dij.init();
		for (int i = 1; i <= n; ++i)
		{
			scanf("%s", s[i] + 1);
			for (int j = 1; j <= n; ++j)if (s[i][j] != '0')
			{
				dij.ins(i, j, s[i][j] - 48);
			}
		}
		dij.dijkstra();
	}
	return 0;
}
/*
【题意】
让你把一个图删成一棵树，使得1到每个点的最短路保持不变

【分析】
我们可以直接求出1到每个点的最短路，然后看看每个点的前驱边可能是有几条（显然对于每一条合法前驱边，以任何一条作为前缀都是等价的）
所有点可能的前驱边数量，乘起来就是最后的答案啦！

【时间复杂度&&优化】
O（nlogn）

*/

【2017CCPC女生赛 E】【分块打表 原题】Easy Summation

Easy Summation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

You are encountered with a traditional problem concerning the sums of powers.
Given two integers  n  and  k . Let  f(i)=ik , please evaluate the sum  f(1)+f(2)+...+f(n) . The problem is simple as it looks, apart from the value of  n  in this question is quite large.
Can you figure the answer out? Since the answer may be too large, please output the answer modulo  109+7 .

 

Input

The first line of the input contains an integer  T(1≤T≤20) , denoting the number of test cases.
Each of the following  T  lines contains two integers  n(1≤n≤10000)  and  k(0≤k≤5) .

 

Output

For each test case, print a single line containing an integer modulo  109+7 .

 

Sample Input

   
   
  
  

   
   
    
    3
    
    
   
   
2 5
    
    
   
   
4 2
    
    
   
   
4 1
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    33
    
    
   
   
30
    
    
   
   
10
   
   
  
  

 

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;

int ans[4][1005] =
{
	{0,163183,319464,468941,611712,747875,877528,1000769,1117696,1228407,1333000,1431573,1524224,1611051,1692152,1767625,1837568,1902079,1961256,2015197,2064000,2107763,2146584,2180561,2209792,2234375,2254408,2269989,2281216,2288187,2291000,2289753,2284544,2275471,2262632,2246125,2226048,2202499,2175576,2145377,2112000,2075543,2036104,1993781,1948672,1900875,1850488,1797609,1742336,1684767,1625000,1563133,1499264,1433491,1365912,1296625,1225728,1153319,1079496,1004357,928000,850523,772024,692601,612352,531375,449768,367629,285056,202147,119000,35713,999952391,999869118,999785999,999703132,999620615,999538546,999457023,999376144,999296007,999216710,999138351,999061028,998984839,998909882,998836255,998764056,998693383,998624334,998557007,998491500,998427911,998366338,998306879,998249632,998194695,998142166,998092143,998044724,998000007,997958090,997919071,997883048,997850119,997820382,997793935,997770876,997751303,997735314,997723007,997714480,997709831,997709158,997712559,997720132,997731975,997748186,997768863,997794104,997824007,997858670,997898191,997942668,997992199,998046882,998106815,998172096,998242823,998319094,998401007,998488660,998582151,998681578,998787039,998898632,999016455,999140606,999271183,999408284,999552007,999702450,999859711,23881,195072,373375,558888,751709,951936,1159667,1375000,1598033,1828864,2067591,2314312,2569125,2832128,3103419,3383096,3671257,3968000,4273423,4587624,4910701,5242752,5583875,5934168,6293729,6662656,7041047,7429000,7826613,8233984,8651211,9078392,9515625,9963008,10420639,10888616,11367037,11856000,12355603,12865944,13387121,13919232,14462375,15016648,15582149,16158976,16747227,17347000,17958393,18581504,19216431,19863272,20522125,21193088,21876259,22571736,23279617,24000000,24732983,25478664,26237141,27008512,27792875,28590328,29400969,30224896,31062207,31913000,32777373,33655424,34547251,35452952,36372625,37306368,38254279,39216456,40192997,41184000,42189563,43209784,44244761,45294592,46359375,47439208,48534189,49644416,50769987,51911000,53067553,54239744,55427671,56631432,57851125,59086848,60338699,61606776,62891177,64192000,65509343,66843304,68193981,69561472,70945875,72347288,73765809,75201536,76654567,78125000,79612933,81118464,82641691,84182712,85741625,87318528,88913519,90526696,92158157,93808000,95476323,97163224,98868801,100593152,102336375,104098568,105879829,107680256,109499947,111339000,113197513,115075584,116973311,118890792,120828125,122785408,124762739,126760216,128777937,130816000,132874503,134953544,137053221,139173632,141314875,143477048,145660249,147864576,150090127,152337000,154605293,156895104,159206531,161539672,163894625,166271488,168670359,171091336,173534517,176000000,178487883,180998264,183531241,186086912,188665375,191266728,193891069,196538496,199209107,201903000,204620273,207361024,210125351,212913352,215725125,218560768,221420379,224304056,227211897,230144000,233100463,236081384,239086861,242116992,245171875,248251608,251356289,254486016,257640887,260821000,264026453,267257344,270513771,273795832,277103625,280437248,283796799,287182376,290594077,294032000,297496243,300986904,304504081,308047872,311618375,315215688,318839909,322491136,326169467,329875000,333607833,337368064,341155791,344971112,348814125,352684928,356583619,360510296,364465057,368448000,372459223,376498824,380566901,384663552,388788875,392942968,397125929,401337856,405578847,409849000,414148413,418477184,422835411,427223192,431640625,436087808,440564839,445071816,449608837,454176000,458773403,463401144,468059321,472748032,477467375,482217448,486998349,491810176,496653027,501527000,506432193,511368704,516336631,521336072,526367125,531429888,536524459,541650936,546809417,552000000,557222783,562477864,567765341,573085312,578437875,583823128,589241169,594692096,600176007,605693000,611243173,616826624,622443451,628093752,633777625,639495168,645246479,651031656,656850797,662704000,668591363,674512984,680468961,686459392,692484375,698544008,704638389,710767616,716931787,723131000,729365353,735634944,741939871,748280232,754656125,761067648,767514899,773997976,780516977,787072000,793663143,800290504,806954181,813654272,820390875,827164088,833974009,840820736,847704367,854625000,861582733,868577664,875609891,882679512,889786625,896931328,904113719,911333896,918591957,925888000,933222123,940594424,948005001,955453952,962941375,970467368,978032029,985635456,993277747,958993,8679306,16438777,24237504,32075585,39953118,47870201,55826932,63823409,71859730,79935993,88052296,96208737,104405414,112642425,120919868,129237841,137596442,145995769,154435920,162916993,171439086,180002297,188606724,197252465,205939618,214668281,223438552,232250529,241104310,249999993,258937676,267917457,276939434,286003705,295110368,304259521,313451262,322685689,331962900,341282993,350646066,360052217,369501544,378994145,388530118,398109561,407732572,417399249,427109690,436863993,446662256,456504577,466391054,476321785,486296868,496316401,506380482,516489209,526642680,536840993,547084246,557372537,567705964,578084625,588508618,598978041,609492992,620053569,630659870,641311993,652010036,662754097,673544274,684380665,695263368,706192481,717168102,728190329,739259260,750374993,761537626,772747257,784003984,795307905,806659118,818057721,829503812,840997489,852538850,864127993,875765016,887450017,899183094,910964345,922793868,934671761,946598122,958573049,970596640,982668993,994790206,6960370,19179597,31447978,43765611,56132594,68549025,81015002,93530623,106095986,118711189,131376330,144091507,156856818,169672361,182538234,195454535,208421362,221438813,234506986,247625979,260795890,274016817,287288858,300612111,313986674,327412645,340890122,354419203,367999986,381632569,395317050,409053527,422842098,436682861,450575914,464521355,478519282,492569793,506672986,520828959,535037810,549299637,563614538,577982611,592403954,606878665,621406842,635988583,650623986,665313149,680056170,694853147,709704178,724609361,739568794,754582575,769650802,784773573,799950986,815183139,830470130,845812057,861209018,876661111,892168434,907731085,923349162,939022763,954751986,970536929,986377690,2274360,18227051,34235854,50300867,66422188,82599915,98834146,115124979,131472512,147876843,164338070,180856291,197431604,214064107,230753898,247501075,264305736,281167979,298087902,315065603,332101180,349194731,366346354,383556147,400824208,418150635,435535526,452978979,470481092,488041963,505661690,523340371,541078104,558874987,576731118,594646595,612621516,630655979,648750082,666903923,685117600,703391211,721724854,740118627,758572628,777086955,795661706,814296979,832992872,851749483,870566910,889445251,908384604,927385067,946446738,965569715,984754096,3999972,23307455,42676636,62107613,81600484,101155347,120772300,140451441,160192868,179996679,199862972,219791845,239783396,259837723,279954924,300135097,320378340,340684751,361054428,381487469,401983972,422544035,443167756,463855233,484606564,505421847,526301180,547244661,568252388,589324459,610460972,631662025,652927716,674258143,695653404,717113597,738638820,760229171,781884748,803605649,825391972,847243815,869161276,891144453,913193444,935308347,957489260,979736281,2049501,24429032,46874965,69387398,91966429,114612156,137324677,160104090,182950493,205863984,228844661,251892622,275007965,298190788,321441189,344759266,368145117,391598840,415120533,438710294,462368221,486094412,509888965,533751978,557683549,581683776,605752757,629890590,654097373,678373204,702718181,727132402,751615965,776168968,800791509,825483686,850245597,875077340,899979013,924950714,949992541,975104592,286958,25539751,50863062,76256989,101721630,127257083,152863446,178540817,204289294,230108975,255999958,281962341,307996222,334101699,360278870,386527833,412848686,439241527,465706454,492243565,518852958,545534731,572288982,599115809,626015310,652987583,680032726,707150837,734342014,761606355,788943958,816354921,843839342,871397319,899028950,926734333,954513566,982366747,10293967,38295338,66370951,94520904,122745295,151044222,179417783,207866076,236389199,264987250,293660327,322408528,351231951,380130694,409104855,438154532,467279823,496480826,525757639,555110360,584539087,614043918,643624951,673282284,703016015,732826242,762713063,792676576,822716879,852834070,883028247,913299508,943647951,974073674,4576768,35157345,65815496,96551319,127364912,158256373,189225800,220273291,251398944,282602857,313885128,345245855,376685136,408203069,439799752,471475283,503229760,535063281,566975944,598967847,631039088,663189765,695419976,727729819,760119392,792588793,825138120,857767471,890476944,923266637,956136648,989087075,22118009,55229562,88421825,121694896,155048873,188483854,221999937,255597220,289275801,323035778,356877249,390800312,424805065,458891606,493060033,527310444,561642937,596057610,630554561,665133888,699795689,734540062,769367105,804276916,839269593,874345234,909503937,944745800,980070921,15479391,50971322,86546805,122205938,157948819,193775546,229686217,265680930,301759783,337922874,374170301,410502162,446918555,483419578,520005329,556675906,593431407,630271930,667197573,704208434,741304611,778486202,815753305,853106018,890544439,928068666,965678797,3374923,41157156,79025587,116980314,155021435,193149048,231363251,269664142,308051819,346526380,385087923,423736546,462472347,501295424,540205875,579203798,618289291,657462452,696723379,736072170,775508923,815033736,854646707,894347934,934137515,974015548,13982124,54037355,94181332,134414153,174735916,215146719,255646660,296235837,336914348,377682291,418539764,459486865,500523692,541650343,582866916,624173509,665570220,707057147,748634388,790302041,832060204,873908975,915848452,957878733,999999916},

	{0,512248278,195993196,492234908,135973547,156209260,875942187,912172454,175900194,872125554,499848646,852069610,15788558,372005630,595720938,655934601,815646738,631857461,955566889,931775127,999482287,891688474,635393793,551598349,255302240,655505571,955208433,651410917,535113121,691315136,499017046,631218942,54920901,31123014,114825358,155028010,294731047,970934546,914638570,150843189,998548487,70754506,274461330,810669015,174377610,154587185,834297796,590509485,94222308,310436321,498151566,210368085,294085927,890305134,434025734,654247776,573971288,510196305,73922855,170150973,997880687,50112004,113844966,270079587,893815888,654053876,513793572,730034990,853778137,730023020,497769646,590018022,733768148,950020024,553773643,154029005,653786110,250044937,433805486,990067743,997831687,830097304,153864573,930133487,413904004,154176110,993949784,70224977,814001682,950279850,498059446,770340442,374122789,210406452,474191389,654477551,534264889,190553354,994342904,610633469,998425007,410717448,394510743,790804829,734599636,654895101,274691154,610987732,974784758,971082155,498879846,751177761,214975809,671273920,195071996,155369960,215167721,331465188,755262270,31558862,999354887,791650226,835444788,851738468,855531161,155822755,355613152,351902233,335689886,791975999,499760446,532043115,255823880,332102622,715879215,656153526,695925429,672194791,715961479,252225353,999986287,972244127,475998733,112249965,775997683,656241726,235981947,292218199,895950328,412178166,499901566,112120360,495834394,192043493,35747496,155946235,975639542,211827228,875509139,271685079,999354887,951518367,315175337,571325622,494969026,155105360,914734442,430856062,654470038,830576167,498174246,490264079,933845463,249918181,153482037,653536821,53082309,949118305,232644571,88660904,996167087,728162882,351648072,227622433,11085734,651037751,390478239,766406974,609823711,45728212,493120246,664999561,568365912,504219054,67558735,147384710,926696727,882494520,785777837,701546419,988800007,300538328,583761130,79468133,322659078,142333685,661491688,297132800,760256755,55863259,482952046,634522822,397575300,953109200,776124221,635620076,594596471,10053105,532989691,108405914,975301487,666676088,9529416,124861170,427671035,626958696,725723838,20966139,103685291,858880972,465552846,396700598,419323899,594422420,276995825,116043785,54565964,329562026,472031628,306974427,953390087,824278251,626638576,361470712,323774309,102549010,580794465,935510310,637696181,452351721,438476566,949070352,631132701,425663249,567661625,586127451,304060349,838459948,600325856,294657695,920455087,770717633,432444948,786636647,8292324,566411601,223994065,38039324,359546979,833516624,398947846,288840246,30193411,444006935,645280398,43013380,340205475,533856256,914965303,68532182,873556487,503037770,423975611,397369576,478219231,15524135,652283861,325497954,266165980,999287498,343862046,412889190,613368475,646299446,506681648,483514626,159797918,412531069,412713610,625345079,809425007,17952918,597928357,190350834,730219887,446535026,862295782,794501665,354152192,946246887,269785246,317766793,377191031,29057463,148365599,904114942,759304981,470935219,90005152,961514283,724462087,311848060,950671698,161932469,760629876,855763387,850332484,441336642,619775343,670648055,172954246,999693398,317864958,588468408,566503202,300968801,134864666,705190258,942945024,73128411,614739887,380778885,478244859,308137249,565455502,239199051,612367343,261959804,58975874,168414986,49276566,454560047,431264848,320390395,756936114,669901417,282285723,111088451,967309020,955946828,476001287,220471809,176357799,624658662,140373789,592502592,144044455,251998783,667364967,435142391,894330453,677928530,712936013,220352279,715176719,6408696,197047601,684092804,158543668,605399577,303659887,826323975,40391190,106860909,480732488,911005283,440678643,406751931,440224496,466095687,703364853,665031336,158094478,283553628,436408121,305657292,874300483,419337015,511766230,16587449,92800007,193403225,65396424,749778932,581550056,189709117,497255436,721188320,372507076,256211018,471299453,410771681,761627009,504864730,915484151,562484558,308865251,311625523,21764660,184281955,838176694,316448149,246095613,548118365,437515677,423286828,308431090,189947735,458836035,800095255,192724653,909723508,518091064,878826593,146929339,771398574,495233535,355433480,682997660,102925312,534215694,189868036,576881589,496255583,42989255,606081849,868532588,807340702,693505421,92025968,861901580,156131459,421714842,399650938,124938963,926578140,427567664,544906758,489594624,766630471,175013494,807742909,51817897,588237674,392001421,732108340,171557612,567348439,70479995,125951475,472762060,143910924,466397255,61220220,843379007,21872769,99700694,873861949,435355687,169181082,754337301,163823490,664638823,817782446,478253512,795051181,211174592,463622905,583395259,895490800,18908660,866647999,645707935,857087614,295786161,50802715,505136408,335786358,513751697,304031543,265625021,251531249,408749345,178278420,295117592,788265972,980722664,489486772,225557407,393933673,493614667,317599486,952887234,780476994,475367863,6558931,637049295,923838031,717924222,164306951,701985308,63958355,277225182,662784858,835636452,704779033,473211670,637933432,989943381,614240572,889824074,489692935,380846217,824282975,375002250,882003104,488284571,630845706,40685543,742803137,56197508,593867711,262812766,264031714,92523582,537287404,681322200,901626997,869200815,549042674,200151594,375526595,922166690,981070885,987238193,669667620,51358172,449308862,474518682,31986631,320711715,833692926,357929249,974419690,58163220,278158845,597405543,272902292,855648084,190641883,416882681,967369449,569101151,243076765,304295262,361755606,318456761,371397691,11577353,23994711,487648722,775538336,554662503,786020180,724610310,919431843,213483715,743764883,941274276,531010830,531973488,257161179,313572839,602207397,318063775,950140909,281437707,388953105,643686018,710635361,548800049,411178997,844771120,690575319,83590502,452815584,521249459,305891028,117739192,561792852,537050895,236512215,147175706,50040255,20104749,426368075,931829113,493486736,362339831,83387271,495627936,732060692,219684405,679497955,126500194,869690002,512066224,950627733,376373374,274302013,423412502,896703693,61174424,577823561,401649935,781652398,260829781,676180936,158704687,133399879,319265343,729299910,670502404,743871656,844406490,161105723,176968186,668992696,708178063,659523104,182026629,228687455,46504385,176476229,453601790,6879864,259309261,927888777,23617194,851493329,10515950,393683867,187995855,874450710,228047200,317784121,506660248,451674356,103825220,708111622,803532323,223086091,93771701,836587921,166533498,92607207,917807809,239134044,947584687,228158471,559854164,715670506,762606244,61660118,267830882,330117269,491518019,289031865,553657547,410393791,278239330,870192897,193253204,548418991,530688970,29061860,226536387,600111263,920785200,253556903,957425098,685388476,384445749,295595622,953836800,188167967,121587835,171095095,47688438,756366562,596128144,159971875,334896446,301900534,535982823,806141990,175376705,685652,933067508,917520929,193044585,292637153,43297289,566023663,275814924,881669742,386586759,87564638,575602035,735697592,746849958,82057775,508319699,86634358,172000401,413416463,753881179,430393177,973951099,209553559,256199199,526886640,728614503,862381409,223185972,400026820,275902560,27811806,126753172,337725265,719726692,625756053,702811955,891892998,427997775,840124893,951272938,878440503,32626174,118828551,136046213,377277746,429521729,173776741,785041368,732314175,778593741,980878638,690167431,551458692,503750986,780042878,907332926,706619688,292901722,75177586,756445838,333705015,97953675,634190369,821413634,832622014,134814046,488988281,950143249,867277480,883389511,935477872,254541086,365577690,87586200,533565146,110513037,519428403,755309753,107155596,157964455,784734839,158465243,744154190,300800168,881401693,832957253,796465350,706924479,793333135,578689806,879992987,808241159,768432810,459566421,874640480,300653454,318603831,803490085,924310683,144064092,219748793,202363246,436905918,562375269,511769759,512087848,84327989,43488642,498568260,852565289,802478175,339305364,748045309,607696442,791257209,465726042,92101380,425381662,514565313,702650765,626636443,217520772,700302184,593979090,711549915,160013070,340366980,947610056,970740702,692757329,690658348,835442163,292107171,519651783,271074389,593373393,827547185,608594155,865512700,821301203,992958054,191481629,521870325,383122511,468236570,764210878,552043804,406733724,197279007,86678022,531929138,284030710,387981107,182778684,301421803,670908819,512238080,340407941,964416757,487262862,305944611,111460345,888808412,916987139,768994867,311829930,706490669,407975404,165282469,21410191,313356897,672120907,22700534,584094112,869299947,685316352,133141640,607774131,798212124,687453925,552497840,964342175,787985222,182425280,600660655,789689632,790510503,938121560,861521088,483707372,21678697,986433355,182969603,710285740,961380030,623250744,676896160,397314542,353504161,408463281,719190166,736683073,205940259,165959988,949740517,184280082,790576954,983629369,272435570,459993814,643302337,213359375,855163178,547711968,564003988,471037467,129810634,695321725,616568955,636550553,792264741,414709734,128883754,853785023,802411742,481762126,692834390,530626735,384137369,936364500,164306315,338961029,25326829,82401916,663184484,214672713,477864804,487758937,573353299,357646070,757635437,984319573,542696651,231764851,144522346,667967309,483097899,564912289,182408638,898585119,570439877,348971078,679176881,300055431,244604887,839823401,706709111,760260169,209474713,557350895,600886846,431080704,432930607,285434686,961591079,728397903,146853289,71955368,652702264,332092087,847122968,228793010,802100344,186043066,293619300,331827149,801664723,498130118,510221444,220936797,307274280,740231989,784808013,441},

	{0,24398083,389738264,967730634,201621270,97960270,218369711,671311670,103856210,693449415,139681334,656054044,961749594,273398033,296845424,218921809,699209237,861809743,287113362,3566136,479438100,614591275,732247689,570757363,275366318,389984575,848954148,968817044,440083270,318998840,19313754,304050019,277269628,375842581,361214871,311176491,611629434,948355686,298785226,923764054,359322135,408441462,132824007,844659756,98394667,682498733,611233912,116422176,639213504,821853854,499453191,691753487,594896700,573192795,150887730,3931470,951745980,948993204,77343100,537241640,639678768,797956442,519456613,397409239,102660271,375439667,17129371,882031348,869135535,913887890,979958364,51008901,122461466,193266003,257668463,296978797,271338956,111490891,710544560,915745907,520244883,254863446,779863554,676715151,439864195,468500644,58326449,393323575,537521973,426767601,860490424,493472393,827615480,203709636,793200840,589959043,402046217,843484334,326023352,50909250,652000,930793581,361675951,570209103,581639009,161315648,806461013,737937076,892013830,912137261,140697355,610796119,38015532,812185608,989152333,282545707,55547744,312660451,691473835,454433903,480610676,257466168,872622407,5629400,919733196,453643802,13303260,563653612,620404886,241803124,20398375,74812688,41508112,66554703,797398524,374629624,423750080,46941955,814835333,758276277,360094871,546873206,680713366,551005442,366195532,745553741,710942167,678582922,450826118,207917874,499768316,237719563,686313755,455061018,490207499,66503338,778970696,534671713,544476557,314831389,639526384,591463710,514425549,14842083,953559515,437608020,811969815,651347096,751930080,123164977,979522025,732263434,981211449,506516301,260424242,359045524,74122399,824797140,169379999,797117270,519959219,264328140,62886327,46304081,435027710,531047522,709665839,411264983,133075290,420943103,861098765,71924619,695723043,390484387,821655036,653905361,542897754,127054607,19326326,798959324,3264000,119382795,576058136,735400457,884656206,227975831,878181808,848536592,44510659,255550506,146846616,251101493,960297648,517465585,8451836,353686940,299953429,412153856,65078774,435174757,492312372,991554207,464922843,213168889,297538954,531543654,472725612,414427465,377559857,102369439,40206876,345294840,866496010,139081065,376496719,462133672,941094645,11962352,518567549,941756971,391161367,596963514,901666182,251860148,189992217,846133194,929745884,721453113,64805714,358050541,545898441,111292275,67174925,948257280,802786222,184312661,143459521,219689726,433074214,276059930,705237840,133110903,419862113,865122457,199738929,577542558,567116359,143563368,680274642,940697231,70102199,587352645,376671647,679410318,85815764,526799126,265703531,890072141,303416104,716982610,641522835,879059983,514657258,908185892,686093110,733170165,184320310,416326826,39620987,890050102,20645459,693390402,370988247,708630352,545764068,897860774,948183849,39556686,666130713,465153337,208736000,795622158,242955260,678046797,330144246,522199119,662634928,237115199,800311486,967671336,407186317,831160025,987976049,653865999,624677506,707642208,713143757,446485819,699660081,243114230,817519988,125541063,823601212,513652171,734941718,955781631,565315702,865287751,61809591,257129077,441398057,484440400,127519989,975108735,486654535,968349335,564897067,251281698,824535209,895505581,880624823,993676958,237566016,396084062,25679154,447223385,737780848,722375657,965759947,764181860,137153559,819219235,251723065,574577275,618030084,894433739,590012494,556630631,303560439,989250235,413092329,7191073,828130833,548743968,449878879,412167974,907795682,992266439,296172702,16962956,910709700,283877426,985090682,396901995,427559941,502777096,557498057,27667435,841997876,413738012,632440524,855730093,901071421,37537224,977576260,868781266,285657021,221388325,79607985,666164836,180891713,209373493,714715060,29309305,846605168,212875568,518985480,492159872,187751740,981010108,558847993,911610461,324842571,371057424,901504128,37935798,164377598,918894692,185360251,85223495,969277651,409427946,190459656,301806064,929316474,447024197,408914586,540693001,731552823,25943447,615338310,830002842,130762501,100770780,437277179,943395219,519870435,156848397,925642696,970502923,500382704,780707693,125143544,887363960,452818630,230501292,644717698,126853607,107142820,6435145,227964418,149116489,113197236,421200558,323576368,11998607,611133244,170406248,655771637,941479429,801843670,903010434,794725809,902103911,517394870,791752851,727004026,167414595,791458793,103586848,425993044,890383665,429745016,770111444,422333296,673844961,580432835,958003349,374350941,140926091,304603293,639449062,638489934,505480473,146671264,162576920,839744075,142519370,704817502,821889161,442089072,158643988,201420683,428693952,318914611,962477511,53489503,881537501,323456398,835097150,443094706,736636064,859228229,500466234,887801147,778308043,450454032,695866252,811099855,589406021,312499958,742328902,112840096,121748832,922306416,115068161,739661443,266553624,588820122,13912355,255425790,424867901,23426190,933736201,411649471,78001593,910380181,234892849,717935274,357959126,477240124,713646001,12404511,617871457,65298635,172601897,32129102,2428144,700014945,991141441,983563603,18309423,661446942,695852194,112977255,104618236,54683262,530960493,276886103,203312308,380275345,28763472,512484989,329636203,104669463,580061146,608079643,142553380,230638818,4588432,673518739,515178263,867715577,121447261,710625951,105208276,802622928,319538592,183632009,925355941,69707157,127994489,589606776,913780885,521369711,786610191,28891269,504521945,398499219,816276140,775529771,197929210,900903597,589410072,847701831,131096077,757742069,900389066,578154369,648291314,797957258,535981586,184633718,871391109,520707221,845779572,340317687,270311140,665797526,312630461,744247610,233438645,784113294,123069285,691760409,638064457,808051269,737750706,644920664,420815067,621951874,461881065,802952662,148084701,632531274,15650473,672672453,586467369,339313425,104664853,638919920,273188907,905062151,990377996,534990828,86539068,726213172,60523603,213068887,816303564,3306195,399547404,114657815,734196108,311416970,359039144,841013394,164290505,170589318,128164688,723575512,53452701,616267229,304098070,394400254,541772832,769726890,462453542,356591944,532997280,408508762,727717644,554735201,264960750,536849643,343681253,945327002,880018326,956114710,243871660,67208731,995477506,835229582,621984612,611998277,274030286,281112390,502316368,994522034,994185230,909105840,310195776,923246999,620699477,413409234,442416322,970712828,375010860,137510582,837668186,143963878,805669934,644618630,546970298,454981298,358772025,288094909,304102415,491115043,948389328,781885833,96037163,985515972,527002914,770954713,733372107,387567876,655934842,401713848,420761786,433319576,75780173,892456581,327349811,715916944,276839068,103789327,157200893,256034973,69548809,109063685,719732920,72309854,154915890,764808452,500148992,751771018,694948059,281161686,229869512,20273178,883086374,792302804,456964228,312928441,514637273,926884589,116584282,344538308,557204637,378465281,101394294,680025772,721121832,475940640,832004404,304867353,29883772,753975981,827402321,195525182,390579003,523438244,275385407,889879043,164321717,441828064,602992733,57658415,736683857,83711813,46937107,70874584,88127131,511153677,224037179,574252650,364435124,844147691,701649462,55663597,447145305,831049816,568100402,416556384,523981118,419009995,3118448,542389959,659284031,324404216,848266115,873065350,364445592,603266561,177371998,973357707,168339499,221721262,866962905,103348365,187753649,626414785,166695836,788856928,697822201,314947851,269790116,391873269,702457625,406307534,883459402,680989656,504782779,211299289,799343753,401832759,277562958,802979036,463941707,847495748,633637957,587085188,549042330,428970314,196354113,872470749,522157265,245578767,169996396,441535335,216952802,655406071,910220444,120657265,403681941,845731900,494484612,350625603,359616434,403462708,292482070,757072214,439478862,885563799,536572831,720903827,645874684,389491348,892215814,948734105,199724293,123624506,28400900,43315680,110695093,977697435,188081023,73972251,747633541,93231343,758604184,147030598,408997196,433966610,842145528,976252673,893286817,356294774,826139414,453267628,69478370,179690636,953711464,218003920,447455147,757144309,894110619,229121332,748439766,45593253,313141202,334443043,475426262,676354387,443594988,841387691,483612150,525556082,655683239,87401415,550830467,284570273,27468774,10389953,947981842,30444494,915298053,719150663,9466538,796333948,524233177,63804579,703616557,141933535,478484014,206228516,203127626,723909971,391840213,190487077,455491330,866333781,438103281,513264744,753427119,131111397,921518639,694297920,305314385,888417228,847207671,846806999,805624539,887125667,491599801,247928415,5353025,825243203,972864549,909146726,282451439,920340456,821343566,146726621,212259529,479984233,549982725,152145046,137937293,472169605,224764163,562523211,740897028,95751942,35138344,31058660,611235372,350878997,864456122,797457362,818165395,609422941,860400776,258365711,480448627,185412433,5420101,537802652,336827142,905464697,687158471,57591681,316455600,679217536,268888846,107792950,109333310,69761437,659944898,417135295,736736300,864071620,886153018,723448306,121649345,643440059,660264400,344094383,659198079,353907594,952387104,746400813,787080995,876695966,560418091,118091791,556001543,598639859,680475314,937720532,200100179,982618998,477329746,545101264,707386428,137990163,654837464,711741354,390170919,391019301,26371684,211273315,455497483,855313533,85254852,389886904,575575181,2253231,575190672,736761150,458210374,231424109,60696169,454496424,417238786,441049230,497533780,29546509,942957560,598421097,803143368,802650656,272557300,310333702,427074306,539265612,960554176,393514596,921417547,999997732},

	{0,186912818,987873282,112372461,719365719,397412938,145107001,351790304,778559416,539557859,83557022,175825174,880284597,541956839,769696129,419210835,576373119,540816649,809822480,62493013,144214130,51405372,916558314,993562990,643322508,319655736,555488122,949330627,152046785,853907918,771936373,637536998,184416654,136791889,197884704,38706460,287129905,517249300,239028686,888238278,816678930,282694790,441974033,338637700,896616706,911316912,41572366,801886657,554962319,504518474,688396497,971953843,41745980,399496484,356355163,27444399,326693561,961961531,430447364,14389096,777050623,558996700,974656130,409172975,15545978,712056042,179981829,861603556,958494792,430102480,992615037,118118532,34041089,722885298,922248802,125133011,580539936,294357080,30530547,312526201,425078959,416230225,99653423,57267664,642139519,981672912,981087154,327183076,492397303,739144606,124448416,504859465,541662484,706371098,286510785,391689997,959959359,764459009,420354079,392058261,745500,432149835,744653311,877662060,660270474,820213512,993107106,731976708,517073957,765981452,844005645,74857868,751623494,148019141,529938122,167283882,346091667,380938229,627639707,496237593,464272846,90348098,27978008,39727708,11639390,967947013,86079088,711949688,375537424,806752695,951592939,988586081,345522059,716472505,79098483,712246445,213832188,519013057,918648156,78046742,56004753,324129386,786451858,799328259,191628539,285213615,915700570,453515993,825237474,535223135,687529372,8116640,867343435,302748291,42120030,526856020,935608595,208219602,69943082,55956015,536157241,740254466,783139416,690551090,425027140,912143378,67041368,821244222,149760383,98475682,811833389,560802433,771133777,51904836,224352099,350991787,765028701,100053141,320026001,749551907,104440531,522556039,594954582,397309991,521627550,108245882,878126997,165434383,950399336,892475263,363780238,482827608,148544712,74579769,823896844,843658934,500399216,115480373,842054,495036454,999552007,15425206,180140578,304818688,411692354,771870940,943392769,809565670,617595638,17503607,101330364,442629548,136248797,838399029,807011780,942384746,828115375,772322621,849156797,940597555,778539986,987168847,125620880,730935314,361292382,639540084,297008958,217615055,482250978,413465062,620428688,44191682,3225883,239256775,963383281,902485649,345921493,192509926,997803813,21650130,276038527,573237878,574221056,837377793,867515646,165149104,276076822,841246933,646910515,675063192,154174806,610207265,917920448,352466286,641270956,16205139,266042489,789206131,646803335,615948310,243373083,899326540,831761531,220810165,233547183,79041437,63695531,646873554,496816926,546848406,51864164,645114029,395269787,863781690,162522987,11722673,798186274,633804780,414351740,878568421,667537094,384342482,654021286,183799831,823619881,626952490,911900071,322586494,890835388,98136465,937900090,977999824,423603220,180290669,917462373,132033424,212417080,502796049,367681970,256763000,770039507,723247876,213572470,685645690,997836127,488824883,44469998,164958976,32249438,577797923,550576760,585379116,271412115,221178112,139644059,893699019,581899758,604504527,733794887,184685696,685623230,549771361,746485939,973077224,726860473,377494647,239609224,645719139,19427830,948918460,260733147,93840461,973990915,888360618,360483090,525469148,205514905,985697945,290061534,457987063,820854492,778990991,878907687,890824510,886483180,317248300,92496590,658294213,76362221,103330177,270277813,962564871,499949022,216991961,543753559,86774156,710345016,618066818,434696358,288281308,892583123,629788040,633506253,872059145,232054668,602250871,957707478,444225649,463075854,756013825,490584663,345715072,597593685,205839517,899958573,266088499,834031465,164575035,937101297,37483966,646273768,327171776,115791013,608706084,52790942,434844830,571506252,199455141,65903119,19371863,100759612,634695787,321183717,327531527,380571090,859165141,887002483,425681341,368080822,632020481,254208021,484475134,880301413,401626419,505949882,243719966,354009717,360481582,667640083,657372583,785778200,680284813,237054209,718675350,852145725,927140878,894572014,465431739,209927927,656905693,393557479,165421302,976667080,190671064,630878481,681954164,391221414,570388933,897565870,19565001,654494064,694635116,309612122,49846601,950301406,634512596,418909505,417422847,646380983,129694294,4327702,626061269,675538930,264605374,42931017,304925095,96936877,324745026,861335038,654964822,837518421,833147804,467202820,75449258,613575027,766984435,60880630,970636154,32451540,954302183,727173142,736582237,874391147,650904677,307258145,928092882,554519824,297371294,450740834,605811185,764970394,456216027,847847523,863446626,297145986,929185866,641758920,535143182,44123091,54698692,21082915,82987009,183194075,185420726,992466874,664653602,538549226,345983400,333349390,381194447,124098307,70839818,724851673,704963256,866431650,422260709,64808299,87681624,507920686,188469858,960937612,748644290,689958093,261919106,404151499,643063806,216337352,197702807,622004825,610554824,496771900,952111840,112284241,703757819,170553719,801327085,856736617,697102353,910351515,440252475,714936883,775709852,406148319,261487505,998295488,404435882,529318706,814439275,224205274,377051959,676845422,444574025,50327947,45566837,295675587,112808232,389019984,729687351,587216404,395039164,701898095,306418710,391970339,661814961,474544191,979804394,254309870,438144243,871349872,230805445,667391707,943445231,570500386,947319404,498210525,811634339,779098164,734338614,592792245,991354342,428425798,404248169,561526779,826341994,549348595,647263292,744640323,315935201,827856588,882006240,357807135,555719693,340746088,286222736,817900861,358315181,471440763,7637921,248885311,54301076,5952174,554951784,167844832,473281686,408979894,368974112,351154110,105090912,280151063,573898995,880787534,441136513,990399533,908718781,370768045,495883807,498484442,838777579,373755540,508478948,347648392,847464275,967774726,824511681,842415056,908045040,523082515,957917610,405526326,135635358,649174967,833019993,115019009,619311595,321933669,206711036,421440980,434362004,190911697,270772714,45206862,834677341,66759042,434337070,54093254,625280903,588787577,286486062,120873416,714998149,72675502,738990916,961091509,849265778,538311365,349190957,950976306,523080348,917777505,823012016,925494472,74086408,443473078,698124266,156543294,955804136,216376582,207239648,511282980,190996448,954447867,321548768,790608401,5175725,921169658,974297300,247760409,640249934,34228633,464501909,287076654,348308311,154335986,40805722,342881872,565546592,554187468,665473256,938517735,266331680,567562990,958524866,925512172,497405895,418565725,322010741,902888245,92230674,231000709,244424399,816612496,565469847,217892962,785255660,739182828,187612349,51145115,239683153,829355892,239734529,411334564,983406378,472013980,448401895,717650109,497617176,598171452,600710414,37968127,574110838,185120634,339467311,179068272,700536615,936717285,138511388,956988632,625787804,143805493,458172842,647520434,105531326,724782203,80872589,616842290,827876831,446301111,626861143,132293886,519185260,324116204,250096931,353289247,230017011,204064722,514264212,502369459,801219541,523189675,448930418,216394946,510154488,251001845,785843078,77877246,897064362,10881336,375366199,326450286,771578665,381618602,783056216,750481177,399359594,379094988,66377378,758820522,868887222,118102812,731556745,632692244,638384171,654304939,870578579,957722913,262879854,6333840,478318353,236110572,301414181,358030241,949816224,678933132,404380785,440821180,757689991,178596182,581009775,96237661,309687629,461420424,646989988,18571786,986379294,420368516,852230761,677673393,358988813,627911505,688763202,421886200,587364778,29034717,878780995,761123511,998091041,814383216,542820683,830083358,842736792,473546685,548081506,31603212,236246136,28483932,36884703,860154207,275467176,447086825,135272376,905474800,337820588,236883747,841745818,36344049,560107744,218882613,96143368,764494355,497458320,481553344,28657828,788663661,962417438,514949875,388993302,718787269,44172279,524971683,155661604,980329093,307918286,927764814,325418186,898752439,174364768,24262409,882837537,964130319,479380122,854864806,950028116,275895243,213776491,234259029,116486805,167728566,443233991,966377951,949092882,12589292,408364395,239498802,682241430,207882440,804914379,201481344,88116378,340766888,244108232,715145433,527102971,533602751,893130142,293788150,178339746,969538258,295745897,216840466,450410091,598236135,373064218,825663364,572173233,21739529,604437493,999483495,363734795,560477417,388502087,811468368,187556845,499409507,584358158,364941025,79707451,514310715,232888951,809734243,61249756,278195092,458219654,538684214,629770566,247879299,549315711,564263801,431048430,630685574,221720690,75355237,110861275,531284212,59433650,174162393,346933512,278675579,136926007,793262510,61022655,933311618,821297927,792797465,811145495,974356847,754574211,237804564,363943710,167088919,16139728,855686834,447189086,610438674,465314340,673822786,682428153,964669655,264067298,837315775,697766390,859197207,579871235,606882789,420791929,480547054,468695588,536882807,551638772,340453389,938139596,833484635,216189500,224096470,190704748,892974262,799417537,318479743,47206821,20201736,958868864,520946464,550327347,327167567,818283309,927835841,748304635,811748580,341355308,503278675,658764313,616563344,885634200,928132549,412689362,467977100,936563993,629056460,578529670,295246174,21662699,987725048,666451085,29801924,804841168,730182254,812724002,584674200,360861358,496334561,644251442,14054282,629934251,589583699,323236658,852997408,52457149,906598877,771990247,637264696,383890588,47228521,77876747,603304705,689774674,604551567,78400817,568374411,520884995,635068169,126432839,990799745,268528025,309030025,35574096,210375609,699976034,740910160,205661442,868905468,674041497,12201}
};
void table()
{
	fre();
	for (int k = 2; k <= 5; ++k)
	{
		int sum = 0;
		for (int i = 1; i <= 1e9; ++i)
		{
			LL val = i; for (int j = 2; j <= k; ++j)val = val * i % Z;
			gadd(sum, val);
			if (i % 1000000 == 0)
			{
				printf("%d,", sum);
			}
		}
		puts("");
	}
}
int n, K;
int main()
{
	//table(); return 0;
	scanf("%d", &casenum);
	for (casei = 1; casei <= casenum; ++casei)
	{
		scanf("%d%d", &n, &K);
		if (K == 0)printf("%d\n", n);
		else if (K == 1)
		{
			int ans = (1ll + n) * n / 2 % Z;
			printf("%d\n", ans);
		}
		else
		{
			int o = n / 1000000;
			int sum = ans[K - 2][o];
			for (int i = o * 1000000 + 1; i <= n; ++i)
			{
				LL val = i; for (int j = 2; j <= K; ++j)val = val * i % Z;
				gadd(sum, val);
			}
			printf("%d\n", sum);
		}
	}
	return 0;
}
/*
【题意】
直接暴力求1^k + ... + n ^ k

【分析】
数据规模被缩小了。
本来是1e9的数据规模，可能要推式子（其实最省脑是分块打表）
后来改成了1e4的数据模拟，直接暴力就好啦。

*/

【2017CCPC女生赛 F】【Bitset 不会做 有空补】Forgiveness 需要补★

Forgiveness

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

Little Q is now checking whether string  A  matches  B . Two strings are considered matched if they have the same length, and there are no position  i  that  Ai  is different from  Bi .
However, Little Q is a kind man, he forgives every person hurt him. What's more, he even forgives strings! He gives the string 3 opportunities, if there are no more than 3 positions  i  that  Ai  is different from  Bi , then Little Q will also consider the two strings matched.
For a string  S ,  S[l,r]  means the substring combined by  Sl,Sl+1,...,Sr . And the function  occ(A,B)  returns the number of substrings in string  B  which matches  A .
Little Q now has a long numeric 1-based string  S , and his job is to deal with  m  operations:

1. +  l   r   k , for every positions from  l  to  r , change  Si  to  (Si+k)mod10 .
2. ?  l   r   T , report  occ(T,S[l,r]) .

After lots of work, Little Q is very tired now, please write a program to help him deal with these operations.

 

Input

The first line of the input contains an integer  T(1≤T≤15) , denoting the number of test cases.
In each test case, there are two integers  n(1≤n≤50000)  and  m(1≤m≤50000)  in the first line, denoting the length of string  S  and the number of operations.
The second line of the input contains a numeric string  S  with  n  integers, each number  Si  is in the range of 0 to 9.
In the following  m  lines, each line describes an operation.
If it is a modification, then it is in the format of ''+  l   r   k '', where  1≤l≤r≤n  and  1≤k≤9 .
If it is a query, then it is in the format of ''?  l   r   T '', where  1≤l≤r≤n  and  T  is a numeric string composed of integers from 0 to 9.
It is guaranteed that  ∑|T|≤100000  in each test case, and there are no more than  4  test cases satisfying  min(n,m)>1000 .

 

Output

For each query, print a single line with an integer, denoting the answer.

 

Sample Input

   
   
  
  

   
   
    
    1
    
    
   
   
5 5
    
    
   
   
01234
    
    
   
   
? 2 5 1234
    
    
   
   
? 2 5 1777
    
    
   
   
? 2 5 9999
    
    
   
   
+ 1 5 5
    
    
   
   
? 1 5 56789
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    1
    
    
   
   
1
    
    
   
   
0
    
    
   
   
1
   
   
  
  

【2017CCPC女生赛 G】【判定】Graph Theory 要不不连前缀边 要不连所有前缀边 判判断是否可以n个数配成二分之n对

Graph Theory

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

Little Q loves playing with different kinds of graphs very much. One day he thought about an interesting category of graphs called ``Cool Graph'', which are generated in the following way:
Let the set of vertices be {1, 2, 3, ...,  n }. You have to consider every vertice from left to right (i.e. from vertice 2 to  n ). At vertice  i , you must make one of the following two decisions:
(1) Add edges between this vertex and all the previous vertices (i.e. from vertex 1 to  i−1 ).
(2) Not add any edge between this vertex and any of the previous vertices.
In the mathematical discipline of graph theory, a matching in a graph is a set of edges without common vertices. A perfect matching is a matching that each vertice is covered by an edge in the set.
Now Little Q is interested in checking whether a ''Cool Graph'' has perfect matching. Please write a program to help him.

 

Input

The first line of the input contains an integer  T(1≤T≤50) , denoting the number of test cases.
In each test case, there is an integer  n(2≤n≤100000)  in the first line, denoting the number of vertices of the graph.
The following line contains  n−1  integers  a2,a3,...,an(1≤ai≤2) , denoting the decision on each vertice.

 

Output

For each test case, output a string in the first line. If the graph has perfect matching, output ''Yes'', otherwise output ''No''.

 

Sample Input

   
   
  
  

   
   
    
    3
    
    
   
   
2
    
    
   
   
1
    
    
   
   
2
    
    
   
   
2
    
    
   
   
4
    
    
   
   
1 1 2
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    Yes
    
    
   
   
No
    
    
   
   
No
   
   
  
  

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 2e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
LL fac[N];	//阶乘预处理
LL inv[N];	//阶乘逆元预处理
LL f[N];	//用f[i]记录从（1，1）走到这个点i的方案数
void factorial()
{
	int top = 2e5;
	fac[0] = 1; for (int i = 1; i <= top; i++)fac[i] = fac[i - 1] * i%Z;
	inv[0] = inv[1] = 1; for (int i = 2; i <= top; i++)inv[i] = inv[Z%i] * (Z - Z / i) % Z;
	for (int i = 2; i <= top; i++)inv[i] = inv[i] * inv[i - 1] % Z;
}
LL C(int n, int m)
{
	return fac[n] * inv[m] % Z*inv[n - m] % Z;
}
void table()
{
	int f[105][105]; MS(f, 0);
	int ans[105];
	int top = 20; f[0][0] = 1;
	for (int i = 1; i <= top; ++i)
	{
		ans[i] = 0;
		for (int j = 0; j <= i / 2; ++j)
		{
			f[i][j] = f[i - 1][j];						//这里放的是1
			if (j)f[i][j] += f[i - 1][j - 1];			//这里放的是0
			ans[i] += f[i][j];
		}
		printf("%d ", ans[i]);
	}puts("");
}
int main()
{
	//table();
	factorial();
	scanf("%d", &casenum);
	for (casei = 1; casei <= casenum; ++casei)
	{
		int n; scanf("%d", &n);
		if (n & 1)puts("0");
		else
		{
			int ans = C(n, n / 2);
			printf("%d\n", (Z + 1) / 2ll * ans % Z);
		}
	}
	return 0;
}
/*
【题意】
有n个点，每个点要不不连前缀边 要不连所有前缀边，判断是否可以n个数配成n/2对。

【分析】
显然我们从后向前看，任意时刻2的数量一定要比1的数量多。
于是直接一个for就做完啦！

这道题的原题是判定在2^n个图中（每个点可能为1或2），有多少个可以配对成n/2的图
对于原题，答案是C（n, n / 2），这个可以通过打表发现，或者自己思考为什么2333

*/

【2017CCPC女生赛 H】【矩阵快速幂】Happy Necklace 珍珠染色素数都满足

Happy Necklace

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

Little Q wants to buy a necklace for his girlfriend. Necklaces are single strings composed of multiple red and blue beads.
Little Q desperately wants to impress his girlfriend, he knows that she will like the necklace only if for every prime length continuous subsequence in the necklace, the number of red beads is not less than the number of blue beads.
Now Little Q wants to buy a necklace with exactly  n  beads. He wants to know the number of different necklaces that can make his girlfriend happy. Please write a program to help Little Q. Since the answer may be very large, please print the answer modulo  109+7 .
Note: The necklace is a single string,  {not a circle}.

 

Input

The first line of the input contains an integer  T(1≤T≤10000) , denoting the number of test cases.
For each test case, there is a single line containing an integer  n(2≤n≤1018) , denoting the number of beads on the necklace.

 

Output

For each test case, print a single line containing a single integer, denoting the answer modulo  109+7 .

 

Sample Input

   
   
  
  

   
   
    
    2
    
    
   
   
2
    
    
   
   
3
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    3
    
    
   
   
4
   
   
  
  

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int prime[10] = { 2,3,5,7,11,13,17 };
int s[24];
int ans[24];
int n;
void table()
{
	for (n = 1; n <= 20; ++n)
	{
		int top = 1 << n;
		for (int sta = 0; sta < top; ++sta)
		{
			for (int i = 0; i < n; ++i)s[i] = (sta >> i & 1) ? 1 : -1;
			bool flag = 1;
			for (int l = 0; l < n; ++l)
			{
				for (int i = 0; i < 7 && l + prime[i] <= n; ++i)
				{
					int sum = 0;
					for (int j = l + prime[i] - 1; j >= l; --j)sum += s[j];
					if (sum < 0) { flag = 0; break; }
				}
				if (!flag)break;
			}
			ans[n] += flag;
		}
		printf("%d\n", ans[n]);

	}
}

const int G = 3;
struct MX
{
	int v[G][G];
	void O() { MS(v, 0); }
	void E() { MS(v, 0); for (int i = 0; i < G; ++i)v[i][i] = 1; }
	void P()
	{
		for (int i = 0; i < G; ++i)
		{
			for (int j = 0; j < G; ++j)printf("%d ", v[i][j]); puts("");
		}
	}
	MX operator * (const MX &b) const
	{
		MX c; c.O();
		for (int k = 0; k < G; ++k)
		{
			for (int i = 0; i < G; ++i) if (v[i][k])
			{
				for (int j = 0; j < G; ++j)
				{
					c.v[i][j] = (c.v[i][j] + (LL)v[i][k] * b.v[k][j]) % Z;
				}
			}
		}
		return c;
	}
	MX operator + (const MX &b) const
	{
		MX c; c.O();
		for (int i = 0; i < G; ++i)
		{
			for (int j = 0; j < G; ++j)
			{
				c.v[i][j] = (v[i][j] + b.v[i][j]) % Z;
			}
		}
		return c;
	}
	MX operator ^ (LL p) const
	{
		MX y; y.E();
		MX x; memcpy(x.v, v, sizeof(v));
		while (p)
		{
			if (p & 1)y = y * x;
			x = x * x;
			p >>= 1;
		}
		return y;
	}
}a, b;

int main()
{
	//table(); 
	//f[i] = f[i - 1] + f[i - 3];

	a.v[0][0] = 2; a.v[0][1] = 3; a.v[0][2] = 4;

	b.v[0][0] = 0; b.v[0][1] = 0; b.v[0][2] = 1;
	b.v[1][0] = 1; b.v[1][1] = 0; b.v[1][2] = 0;
	b.v[2][0] = 0; b.v[2][1] = 1; b.v[2][2] = 1;

	scanf("%d", &casenum);
	for (casei = 1; casei <= casenum; ++casei)
	{
		LL n; scanf("%lld", &n); --n;
		MX c = a * (b ^ n);
		printf("%lld\n", c.v[0][0]);
	}
	return 0;
}
/*
【题意】
有一串珍珠，长度为n（1e18）
每个珍珠要不染色成红色，要不染色成蓝色。
要求任何连续素数长度的珍珠，都必须是红色个数>=蓝色个数
让你求出有多少种对这串珍珠的染色方案。

【分析】
我们用f[i]表示长度为i的珍珠串的合法染色方案数。
显然，如果第i颗珍珠染色为红色，f[i-1]的都依然合法、
如果第i颗珍珠染色为蓝色，要求这连续三颗必须为红红蓝，于是收获f[i-3]的贡献。
而只要2、3素数满足要求，所有素数都会满足要求（因为它们可以拆成2与3）。
所以得到递推式：f[i] = f[i - 1] + f[i - 3]
矩阵快速幂即可求解。

【时间复杂度&&优化】
O(logn * 27)

*/

【2017CCPC女生赛 I】【LCA 时间戳】Innumerable Ancestors

Innumerable Ancestors

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

There is a tree having  n  nodes, labeled from 1 to  n . The root of the tree is always 1, and the depth of a node  p  is the number of nodes on the shortest path between node  p  and the root.
In computer science, the Lowest Common Ancestor (LCA) of two nodes  v  and  w  in a tree is the lowest (i.e. deepest) node that has both  v  and  w  as descendants, where we define each node to be a descendant of itself (so if  v  has a direct connection from  w ,  w  is the lowest common ancestor).
You have to answer  m  queries. Each query gives two non-empty node sets  A  and  B , there might be some nodes in both sets.
You should select one node  x  from set  A , and one node  y  from set  B ,  x  and  y  can be the same node. Your goal is to maximize the depth of the LCA of  x  and  y .
Please write a program to answer these queries.

 

Input

The input contains several test cases, no more than 5 test cases.
In each test case, the first line contains two integers  n(1≤n≤100000)  and  m(1≤m≤100000) , denoting the number of nodes and queries.
For the next  n−1  lines,each line contians two integers  a  and  b , denoting a bi-directional edge between node  a  and  b .
Then there are  2m  lines, every two lines describes one query.
For each query, the first line describes the set A.
The first integer  k(1≤k≤n)  denotes the number of nodes in set  A , and the next  k  integers describing the nodes in set  A . There might be some nodes appear multiple times in the set.
The second line describes the set  B  in the same format of set  A .

It is guaranteed that  ∑k≤100000  in each test case.

 

Output

For every query, print a number denoting the answer, which means the maximum depth of the LCA.

 

Sample Input

   
   
  
  

   
   
    
    7 3
    
    
   
   
1 2
    
    
   
   
1 3
    
    
   
   
3 4
    
    
   
   
3 5
    
    
   
   
4 6
    
    
   
   
4 7
    
    
   
   
1 6
    
    
   
   
1 7
    
    
   
   
2 6 7
    
    
   
   
1 7
    
    
   
   
2 5 4
    
    
   
   
2 3 2
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    3
    
    
   
   
4
    
    
   
   
2
   
   
  
  

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
int ga, gb;
int a[N], b[N];

vector<int>w[N];				//记录边
int dep[N];						//记录深度
int f[N][20];					//f[i][j]表示与i的距离为2^j的祖先

int dfn[N], tim;
void dfs(int x)
{
	dfn[x] = ++tim;
	for (auto y : w[x])
	{
		if (y == f[x][0])continue;
		f[y][0] = x;
		dep[y] = dep[x] + 1;
		dfs(y);
	}
}

void LCAinit()
{
	for (int j = 1; (1 << j) < n; ++j)
	{
		for (int i = 1; i <= n; ++i) if (f[i][j - 1])
		{
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
}
int LCA(int x, int y)
{
	//步骤一，使得x与y在相同深度
	if (dep[x] < dep[y])swap(x, y);
	int i; for (i = 0; (1 << i) <= dep[x]; ++i); --i;
	for (int j = i; dep[x] > dep[y]; --j)if (dep[x] - (1 << j) >= dep[y])x = f[x][j];
	if (x == y)return x;

	//步骤二，在倍增祖先不同的情况下向上跳，最后使得f[x][0] = f[y][0]
	for (int j = i; f[x][0] != f[y][0]; --j)if (f[x][j] != f[y][j])
	{
		x = f[x][j];
		y = f[y][j];
	}
	return f[x][0];
}

bool cmp(int x, int y)
{
	return dfn[x] < dfn[y];
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		for (int i = 1; i <= n; ++i)w[i].clear();
		for (int i = 1; i < n; ++i)
		{
			int x, y; scanf("%d%d", &x, &y);
			w[x].push_back(y);
			w[y].push_back(x);
		}
		MS(f, 0);
		tim = 0; dep[1] = 1; dfs(1);
		LCAinit();

		for (int i = 1; i <= m; ++i)
		{
			scanf("%d", &ga); for (int i = 1; i <= ga; ++i)scanf("%d", &a[i]);
			scanf("%d", &gb); for (int i = 1; i <= gb; ++i)scanf("%d", &b[i]);
			sort(a + 1, a + ga + 1, cmp);
			sort(b + 1, b + gb + 1, cmp);

			int ans = 0;
			int j = 1;
			for (int i = 1; i <= ga; ++i)
			{
				while (j < gb && dfn[b[j]] < dfn[a[i]])++j;
				if (j > 1)
				{
					gmax(ans, dep[LCA(a[i], b[j - 1])]);
				}
				gmax(ans, dep[LCA(a[i], b[j])]);
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}
/*
【题意】
一棵树，有n（1e5）个节点。
同时存在m（1e5）个询问。每个询问给你2个集合。
要你求出
for(第一个集合中的点x)
{
	for(第一个集合中的点y)
	{
		max(dep[ lca(x,y) ]);
	}
}

【分析】
这道题要大胆猜！
显然，如果我们考虑了x，哪个点y，会可能产生尽可能大的dep[ lca(x,y) ]呢?
一定是与x时间戳（dfs序）最接近的节点y。

因为要知道一棵子树的dfs序必然是连续的一段。

所以如果y是x或者是x的子孙，都一样会收获对于x最好的y，产生的dep[ lca(x,y) ]就等于dep[x]
而如果y不是x的子孙，则还是基于dfs序定理，最接近的一定可以获取到最大的dep[ lca(x,y) ]（可以画一棵树标上dfs序脑补一下！）

然而双log，在树上二分也是可以过的哦~

【时间复杂度&&优化】
O(nlogn)

*/

【2017CCPC女生赛 J】【DP博弈】Judicious Strategy

Judicious Strategy

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

Alice and Bob is now playing a game about strings.
There is a dictionary containing  n  words (words might be same). Alice choose a lowercase English letter arbitrarily first, but this letter should appear in at least one of these  n  words. Then Bob choose a lowercase English letter arbitrarily to add it before or after the letter Alice chose. So Bob gets a new string now. This new string should also be a substring (consecutive subsequence) of at least one strings in the dictionary. After that, it's Alice's turn. Alice should do the same thing, choosing a letter and add it before or after the current string, making a new string. At every moment, the string they made should always be a substring of at least one strings in the dictionary. The player who can't operate first lose the game and the other one win.
Besides, each player has a score. The score is calculated by the following rule:
If the string  S  is now made, the current player will get  score(S)  points. It means that Alice will score in the first round, then Bob, then Alice...

score(S)=⎡⎣⎛⎝∑i=1|S|value(Si)⎞⎠×maxi=1|S|value(Si)⎤⎦+occ(S)

where

1.  |S|  means the length of  S .
2.  value(c)  represents the value of letter  c . The score of letter ``a'' is 1, ``b'' is 2, ..., ``z'' is 26.
3.  occ(S)  means the time that  S  occurs as a substring in the dictionary, each word is counted just once.

Alice and Bob will play with best strategy. That is to say, they will consider to win first and then maximize their score, after that they will consider to minimize the score of others.
Please determine who will win the game, and report the final scores they will earn during the whole game.

 

Input

The input contains several test cases, no more than 10 test cases.
In each test case, the first line contains an integer  n(1≤n≤30) , denoting the number of words in the dictionary.
In the next  n  lines, each line contains a non-empty string  wordi , denoting a word in the dictionary. The string is composed of lowercase English letters and its length will not exceed 30.

 

Output

For each test case, output a string in the first line. If Alice will win ,output ''Alice'', otherwise output ''Bob''.
Then print two integers  A  and  B  in second line, denoting the final score of Alice and Bob.

 

Sample Input

   
   
  
  

   
   
    
    2
    
    
   
   
aba
    
    
   
   
abac
    
    
   
   
3
    
    
   
   
artem
    
    
   
   
nik
    
    
   
   
max
   
   
  
  

 

Sample Output

   
   
  
  

   
   
    
    Bob
    
    
   
   
29 35
    
    
   
   
Alice
    
    
   
   
2403 1882
   
   
  
  

 

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
char s[32];
struct A
{
	int win;
	int me;
	int enemy;
	bool operator > (const A & b)
	{
		if (win != b.win)return win > b.win;
		if (me != b.me)return me > b.me;
		return enemy < b.enemy;
	}

	A Ene(int sco)
	{
		return{ 1 - win, enemy + sco, me };
	}
};
map<string, A>mop;
map<string, int>occ;
map<string, int>dfn;
int score(string s)
{
	int ret = 0;
	int mx = 0;
	for (int i = 0, sz = s.size(); i < sz; ++i)
	{
		ret += (s[i] - 'a' + 1);
		gmax(mx, s[i] - 'a' + 1);
	}
	return ret * mx + occ[s];
}

bool cmp(string a, string b)
{
	return a.size() < b.size();
}
int main()
{
	while (~scanf("%d", &n))
	{
		mop.clear(); occ.clear(); dfn.clear();
		for (int i = 1; i <= n; ++i)
		{
			scanf("%s", s);
			for (int l = 0; s[l]; ++l)
			{
				for (int r = l; s[r]; ++r)
				{
					char tmp = s[r + 1]; s[r + 1] = 0;
					if (dfn[s + l] != i)
					{
						dfn[s + l] = i;
						++occ[s + l];
					}
					s[r + 1] = tmp;
				}
			}
		}

		vector<string>vt;
		for (auto it : occ)vt.push_back(it.first);
		vt.push_back("");
		sort(vt.begin(), vt.end(), cmp);
		for (int i = vt.size() - 1; ~i; --i)
		{
			string s = vt[i];
			A now = { 0, 0, 0 };
			for (char ch = 'a'; ch <= 'z'; ++ch)
			{
				if (mop.count(s + ch))
				{
					gmax(now, mop[s + ch].Ene(score(s + ch)));
				}
				if (mop.count(ch + s))
				{
					gmax(now, mop[ch + s].Ene(score(ch + s)));
				}
			}
			mop[s] = now;
		}
		auto it = mop[""];
		printf("%s\n", it.win == 1 ? "Alice" : "Bob");
		printf("%d %d\n", it.me, it.enemy);
	}
	return 0;
}
/*
【题意】
给你n（30）个串，每个串的长度也不超过30。
Alice和Bob博弈，Alice先手，初始是空串。
每次要在串前或串后任意加一个小写字符，使得原始串中，至少存在一个串包含该子串。不能操作就输了。
双方博弈的关键字是（胜败，自己分数尽可能高，对手分数尽可能低）
让你输出Alice的最优结局。

【分析】
直接按照基本SG博弈的方法，从终止态退回初始态（空串）就好啦!
可以看看我是怎么写的，用到了很多小技巧。
先预处理好所有合法串，再按长度排序得到DP的顺序。
接着直接做DP，这么写20分钟就写完1A啦！

【时间复杂度&&优化】
O(n^3 * log(n^3) )

*/