## 【数位DP-技巧】长度为N的数串每M个和都为质数

Description

Input

Output

Sample Input
2 2
Sample Output
37
HINT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,md;
int pri[55];
int g[10001];
ll dp[55][5555];
void init()
{
for(int i=1;i<=49;i++) pri[i]=1;
pri[0]=0;pri[1]=0;
for(int i=2;i<=7;i++)
{
if(pri[i])
{
for(int j=i*i;j<=49;j+=i) pri[j]=0;
}
}
for(int i=1;i<=9999;i++) g[i]=g[i/10]+i%10;
}
ll dfs(int pos,int num)
{
if(pos==0) return 1;
ll &ans=dp[pos][num];
if(~ans) return ans;
ans=0;
for(int i=0;i<=9;i++)
{
if(pos+m-1>n||pri[g[num]+i]==1)
{
ans+=dfs(pos-1,(num*10+i)%md);
}
}
return ans;


## 【高斯消元解异或方程组】开关问题


1518: 熄灯的工作
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 471  Solved: 19
[Submit][Status][Web Board]
Description

Input

Output

Sample Input
3 2
2 1 2
2 1 3
Sample Output
NO

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[202][202]={0};
void gauss()
{
for(int i=1;i<=n;i++)
{
int j=i;
while(j<=n&&!a[j][i]) j++;
if(j>n) continue;
if(i!=j) for(int k=1;k<=m+1;k++) swap(a[i][k],a[j][k]);
for(int l=1;l<=n;l++)
if(l!=i&&a[l][i])
for(int k=1;k<=m+1;k++) a[l][k]^=a[i][k];
}
}
int main()
{
int ans=1;
scanf("%d%d",&n,&m);
//a[n][m];
for(int i=1;i<=n;i++) a[i][m+1]=1;


## Playing with Paper CodeForces – 527A

http://codeforces.com/problemset/problem/527/A

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
typedef long long ll;
ll ans=0;
ll gcd(ll a,ll b)
{
if(b==0)
{
return a;
}
else
{
ans+=a/b;
return gcd(b,a%b);
}
}
ll aa,bb;
int main()
{
scanf("%lld%lld",&aa,&bb);
gcd(aa,bb);
printf("%lld",ans);
} 

## LightOJ – 1282 求取数字前三位和后三位

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of nk.

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

Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).

Output
For each case, print the case number and the three leading digits (most significant) and three trailing 

## LightOJ – 1138 Trailing Zeroes (III)

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

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

Each case contains an integer Q (1 ≤ Q ≤ 108) in a line.

Output
For each case, print the case number and N. If 

## LightOJ – 1045 K进制的位数

Factorial of an integer is defined by the following function

f(0) = 1

f(n) = f(n - 1) * n, if(n > 0)

So, factorial of 5 is 120. But in different bases, the factorial may be different. For example, factorial of 5 in base 8 is 170.

In this problem, you have to find the number of digit(s) of the factorial of an integer in a certain base.

Input
Input starts with an integer T (≤ 50000), denoting the 

## 线性同余方程组的合并



a_ix\equiv b_i\mod m_i

x\equiv B \mod lcm(m_i)

a_1x \equiv b_1 \mod m1

x\equiv (b_1/\gcd(a_1,m_1))*(a_1^{-1}/gcd(a_1,m_1)) \mod (m_1/gcd(a_1,m_1))

x \equiv B_1 \mod m1

x=B_1+m_1*t 此时的m1*t是未知的

a(B_1+m_1t) \equiv b_2 \mod m_2

am_1t \equiv b_2-aB_1 \mod m_2

t \equiv (b_2-aB_1)/gcd(am_1,m_2) * (am_1)^{-1}/gcd(am_1,m_2) \mod (m_2)/gcd(am_1,m_2)

x=B_1+m_1*t

$此时的x在\mod m1和\mod m2的意义下都是成立的。B1_+m_1*t变成了新的B_2$

x\equiv B_2 \mod lcm(m_1,m_2)

x=B_2+lcm*t

//返回一个b，m对
pair<int, int> inner_congruence(const vector<int> &A,const vector<int> &B,const vector<int> &M)
{
int x=0,m=1;
for(int i-9;i<A.size();i++)
{
int a=A[i]*m,b=B[i]-A[i]*x,d=gcd(a,M[i]);
if(b%d!=0) return make_pair(0,-1); 

## 【容斥原理】Arrange the Numbers LightOJ – 1095

Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate the number of arrangement of first N natural numbers, where in first M positions; exactly K numbers are in their initial position.

For Example, N = 5, M = 3, K = 2

You should count this arrangement {1, 4, 3, 2, 5}, 

## 【矩阵快速幂】nth Term LightOJ – 1096

You have to find the nth term of the following function:

f(n) = a * f(n-1) + b * f(n-3) + c, if(n > 2)

= 0, if(n ≤ 2)

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

Each case contains four integers n (0 ≤ n ≤ 108), a b c (1 ≤ a, b, c ≤ 10000).

Output
For each case, print the case number and f(n) modulo 10007.

Sample Input


## 【离线并查集】问题集合

• 有 N 个数，初始均为 0。有 Q 个操作，第 i 个操作会把第 Li 到第 Ri 个数改为 Ci。问，所有操作结束后，每个数的值

#include<iostream>
#include<stdio.h>
using namespace std;
int f[1001]={0};
int qm[1001][3]={0};
int a[1001]={0};
int n=0,q=0;
int ff(int x)
{
if(f[x]==x) return x;
else return f[x]=ff(f[x]);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n+2;i++) f[i]=i;
for(int i=q;i>0;i--)
{
scanf("%d%d%d",&qm[i][1],&qm[i][2],&qm[i][0]);
}
for(int i=1;i<=q;i++)
{
int l=qm[i][1],r=qm[i][2],v=qm[i][0];
while(l<=r)
{
l=ff(l);
if(l<=r)
{
a[l]=v;
f[l]=l+1;
l+=1;
}
else
{
break;
}
}
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}