| by XianKa | No comments

### 【数论】蓝桥杯历届试题 小数第n位

http://lx.lanqiao.cn/problem.page?gpid=T456

问题描述
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。

本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。

一行三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置（0<a,b,n<1000000000）

一行3位数字，表示：a除以b，小数后第n位开始的3位数字。

1 8 1

125

1 8 3

500

282866 999000 6

914

$\frac{a}{b} \mod p = \frac{a \mod b \times p}{b} 所以本题： \frac{a}{b} \times 10^{n+2} \mod 10^3 = \frac{a \times 10^{n+2} \mod b \times 10^3}{b} = \frac{(a \mod b \times 10^3) \times (10^{n+2} \mod b \times 10^3)}{b} n取1e10，所以快速幂一下。就做完了，简单数论 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a,b,n,mod; ll ksm(ll  Read the rest Read More | by XianKa | No comments ### 蓝桥杯历届试题 小计算器 http://lx.lanqiao.cn/problem.page?gpid=T459 问题描述 模拟程序型计算器，依次输入指令，可能包含的指令有 1. 数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数 2. 运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余 3. 进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36) 4. 输出指令：'EQUAL'，以当前进制输出结果 5. 重置指令：'CLEAR'，清除当前数字 指令按照以下规则给出： 数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出 运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令 重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令 进制转换指令可能出现在任何地方 运算过程中中间变量均为非负整数，且小于2^63。 以大写的'A'~'Z'表示10~35 输入格式 第1行：1个n，表示指令数量 第2..n+1行：每行给出一条指令。指令序列一定以'CLEAR'作为开始，并且满足指令规则 输出格式 依次给出每一次'EQUAL'得到的结果 样例输入 7 CLEAR NUM 1024 CHANGE 2 ADD NUM 100000 CHANGE 8 EQUAL 样例输出 2040 按题意模拟就可以了。由于是整数，所以把所有进制化为十进制计算，省去了自己写运算的东西。输出的时候转再转换一下就可以了。有个坑点是在ADD等运算之间可能转换进制。 #include<bits/stdc++.h> using namespace std; typedef long long ll; map<ll,char> eco; map<char,ll> deco; int k=10; ll ans=0; char num; void init() { for(ll i=0;i<=9;i++) { eco[i]=i+'0'; deco[i+'0']=i; } for(ll i='A';i<='Z';i++) { eco[i-'A'+10]=i; deco[i]=i-'A'+10; } } ll getnum() {  Read the rest Read More | by XianKa | No comments ### 【二分图匹配-最小边覆盖】mz语考试 Description jswf夺冠后 cc: tql gj: tggl mz：tlrxml frz: bksjs wjjj: whnzmqa ...... js: ??? js: nmflb ————节选自某次mz语等级测试 mz语等级测试即将到来。然而mz语十分难，用词灵活多变，导致作弊人数众多。而防止考生作弊的一个有效的途径是让考生之间保持一定的距离。 某考场有R（行）*C（列）个座位，坐在(r, c)的考生可能会看到(r,c-1)、(r,c+1)、(r-1,c-1)、(r-1,c+1)（即左、右、左前、右前）4个位置的考生的答案。 为了防止这种情况发生，就要保证一个考生周围的这4个位置中无其他考生。 而由于这个考场年久失修，有一些座位已经损坏，是无法使用的。 现在，fls想知道，在保证无人能看到别人答案的前提下，这个考场最多能安排多少名考生？ Input 多组数据 第一行有一个整数T(T<=30)，代表数据组数。 对每组数据，第一行有两个整数R、C(1 <= R, C <= 50)，表示考场规模。 接下来R行，每行有一个长度为C的字符串，描述考场内每个位置。'.'表示该位置可用，'x'则表示已损坏。 Output 对每组数据，输出该考场内最多能安排的考生数。 Sample Input 1 2 3 ... .x. Sample Output 4 相隔两列的人是看不见对方的。所以把有冲突的座位连边即为二分图。 任意两个冲突的位置只能有一个地方坐人，即任意点只能有一条边相连。边数就是能坐下的人。转化为了最小边覆盖问题。 答案就是 点数-最大匹配数 注意link vis这些变量名有可能会与STL冲突 #include<vector> #include<stdio.h> #include<iostream> #include<cstring> #include<string> using namespace std; int dx[]={-1, 0, 1,-1,0,1}; int dy[]={-1,-1,-1, 1,1,1}; char tsr; vector<int> G; int id; int visa={0}; int linka={0}; int r,c; int lig(int  Read the rest Read More | by XianKa | No comments ### 【计算几何-技巧】射击游戏 Description js在ak了一套cf后，打开了一款新出的射击游戏。 这个射击游戏在一个二维平面进行,js控制的人物处于坐标原点(0,0)。平面上共有n只怪物,每个怪物所在的坐标为(x[i], y[i])。js进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。 而高贵的js是这个游戏的VIP玩家,他拥有两项特权操作: 1、让平面内的所有怪物向任意一个相同的方向移动相同的距离d。 2、让平面内的所有怪物以js为中心旋转相同的角度θ。 js在进行射击前,可以无限次的使用这两项特权操作。js想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮伟大的js吧。 Input 输入包括三行。 第一行中有一个正整数n(1 <= n <= 100),表示平面内的怪物数量。 第二行包括n个由空格分隔的整数x[i](-1,000,000 <= x[i] <= 1,000,000),表示每只怪物的横坐标。 第二行包括n个由空格分隔的整数y[i](-1,000,000 <= y[i] <= 1,000,000),表示每只怪物的纵坐标。 Output 输出js一次性最多能消灭的怪物数。 Sample Input 5 0 -1 1 1 -1 0 -1 -1 1 1 Sample Output 5 枚举两个点，连成一条线。每次检查在线上有多少点，不在线上的点往线上作投影，当线上的点+某个投影的坐标的所有点>答案的时候，更新答案。 是否三点一线用向量是否平行，投影也用向量坐标运算。 技巧：投影用map来存储，遍历的时候用map的迭代器进行遍历。重载运算符实现坐标相减得到向量的功能。 答案初始化为1；因为如果没有能构成线点，那么将不运算 #include<bits/stdc++.h> #include<vector> #include<map> using namespace std; typedef long long ll; struct point{ ll x, y; point(){} point(ll x,ll y):x(x),y(y){} point operator -(point tp) { return point(x-tp.x,y-tp.y); } }p; ll dot(point a,point b) {  Read the rest Read More | by XianKa | No comments ### 【生成函数】果苣拼盘 Description 果苣是一类高贵的水果的统称。 而果苣拼盘则是使用这些高贵的水果制成的拼盘。制作一份果苣拼盘，需要满足如下限制： 1. 必须使用特定的n种果苣。 2. 第i种果苣的数量不能少于li 份，也不能多于ri 份 3. 果苣的总份数要恰好为m份 果苣想知道，一共有多少种不同的果苣拼盘的制作方案？ Input 多组数据 第一行有一个整数T(T<=20)，代表数据组数。 对每组数据，第一行有两个由空格分隔的整数n和m(1<=n<=20, 1<=m<=100)，表示果苣的种类和拼盘需要的果苣总份数。 接下来n行，每行有两个由空格分隔的整数li 和ri (0<= li <= ri <= 10)，描述第i种果苣数量的限制。 Output 对每组数据，输出满足限制条件的方案数。 Sample Input 2 2 3 1 2 1 2 3 5 0 3 0 3 0 3 Sample Output 2 12 HINT 对于两种方案，当有任意一种水果的份数不同时，则两种方案不同。  每种水果无论取几个都只有一种取法。生成函数，最后[latex]x^n$的系数就是答案，即多项式的乘法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a={0};
ll t,n,m,l,r;
ll ans,tmp;
int main()
{
scanf("%lld",&t);
while(t--)
{
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(ans,0,sizeof(ans));
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++)
{
scanf("%lld%lld",&l[i],&r[i]);
m-=l[i];

| by XianKa | No comments

### 【矩阵快速幂】hyper Fibonacci 数列

Description

S1(i)表示F数列的前i项和。
S2(i)表示S1数列的前i项和。
S3(i)表示S2数列的前i项和。
S4(i)表示S3数列的前i项和。
S5(i)表示S4数列的前i项和。
S6(i)表示S5数列的前i项和。
S7(i)表示S6数列的前i项和。
S8(i)表示S7数列的前i项和。

Input

Output

Sample Input
4
1
2
3
4
Sample Output
1
9
46
175
HINT
F数列前四项：1 1 2 3

S1数列前四项：1 2 4 7

S2数列前四项：1 3 7 14

S3数列前四项：1 4 11 25

S4数列前四项：1 5 16 41

S5数列前四项：1 6 22 63

S6数列前四项：1 7 29 92

S7数列前四项：1 8 37 129

S8数列前四项：1 9 46 175 

#include
using namespace std;
typedef long long ll;
ll p=1000000007;
struct Mat{
ll a;
Mat(){
memset(a,0,sizeof(a));
}
};
Mat mul(Mat a,Mat b)
{
Mat res=Mat();
for(ll i=0;i<10;i++)
{
for(ll j=0;j<10;j++)
{
for(ll k=0;k<10;k++)
{
if(a.a[i][k]&&b.a[k][j])
res.a[i][j]+=(a.a[i][k]%p)*(b.a[k][j]%p)%p;
}
}
}
return res;
}
Mat ksm(Mat n,ll k)
{
Mat ans=Mat();
for(ll i=0;i<10;i++)
ans.a[i][i]=1;
while(k)
{
if(k&1) ans=mul(n,ans);
n=mul(n,n);
k>=1;
}
return ans;
}
int main()
{
ll t;
ll temp1={
{1,1,1,1,1,1,1,1,1,0},
{0,1,1,1,1,1,1,1,1,0},
{0,0,1,1,1,1,1,1,1,0},
{0,0,0,1,1,1,1,1,1,0},
{0,0,0,0,1,1,1,1,1,0},
{0,0,0,0,0,1,1,1,1,0},
{0,0,0,0,0,0,1,1,1,0},
{0,0,0,0,0,0,0,1,1,0},
{0,0,0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,1,0}
};
ll temp2={
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0}
};

| by XianKa | No comments

### 【欧拉函数||容斥】gcd之和

Description

Input
多组数据。

Output

Sample Input
3
3
2 1 3
4
4 3 9 6
7
7 7 7 7 7 7 7
Sample Output
3
13
147
HINT
对于第一组数据:

gcd(2,1)+gcd(2,3)+gcd(1,3)=1+1+1=3

gcd(4,3)+gcd(4,9)+gcd(4,6)+gcd(3,9)+gcd(3,6)+gcd(9,6)=1+1+2+3+3+3=13

gcd(7,7)*(6+5+4+3+2+1)=7*21=147 

1.容斥

2.欧拉函数

n*C 2 \choose num(n)

(0+1+2+..+num(n)-1) * \sum\limits_{d|n}φ(d)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+233;
ll phi[maxn+23]={0};
ll a[maxn+23];
vector<ll> d[maxn+23];
void phi_t()
{
for(ll i=2;i<=maxn;i++) phi[i]=0;
phi=1;
for(ll i=2;i<=maxn;i++)
if(!phi[i])
{
for(ll j=i;j<=maxn;j+=i)
{
if(!phi[j]) 
| by XianKa | No comments

### 【矩阵快速幂-构造】I – Algebraic Problem LightOJ – 1070

Given the value of a+b and ab you will have to find the value of an+bn. a and b not necessarily have to be real numbers.

Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be 
| by XianKa | No comments

### 【组合数求模】K – Combinations LightOJ – 1067

Given n different objects, you want to take k of them. How many ways to can do it?

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.

Take 1, 2

Take 1, 3

Take 1, 4

Take 2, 3

Take 2, 4

Take 3, 4

Input
Input starts with an integer T (≤ 2000), denoting the number of test cases.

Each test case contains two integers n (1 
A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move vertically or horizontally from its current position and two rooks attack each other if one is on the path of the other. In the following figure, the dark squares represent the reachable locations for rook R1 from its current position. The figure also shows that the rook R1 and R2 are in attacking positions where