XianKa

120

XianKa 's Posts

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

Description
经过不懈的努力，你在后山挖出了一个宝箱，旁边还有一张纸条，上面写着两个数字还有一段话：“我是九头龙晗源，想要我的资源吗？如果想要的话，那就到oj.cqupt.edu.cn.cqu.pt去找吧，我全部都放在那里。密码是满足由N位数字组成，且每连续M个数字之和都是质数的数字串的个数。N和M我写在纸上了。”
Input
每个输入包含一个测试用例。 每个测试用例包括两个整数N(1<=N<=12)和M(1<=M<=4)。
Output
输出一个整数，表示密码，即满足由N位数字组成，且每连续M个数字之和都是质数的数字串的个数。 这N位数字每一位可以是0~9，数字串可以有前导0。
Sample Input
2 2
Sample Output
37
HINT
当M>N时，密码为0

无脑滚表虽然过了，但和MZJJ学到了很多数位dp的技巧。

比如如何取位，如何快速加和一个3位数，如何巧妙的避开判断m的大小。

#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;
… Read the rest

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


1518: 熄灯的工作
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 471  Solved: 19
[Submit][Status][Web Board]
Description
重庆游戏与电子竞技大学的熄灯时间是11点半。每天晚上，宿管嬢嬢都是用总开关来关灯的。但是今天总开关坏了，只有一些分开关，每个开关控制一些灯，灯都有可能被多个开关控制。按一次开关，所有它所控制的灯都会切换一次状态，即亮的灯变灭，灭的灯变亮。一开始所有灯都是亮的，宿管嬢嬢想把所有的灯都灭了，但是她面对一堆开关头皮发麻，只好找来了头铁的你来解决这个问题。
Input
每个输入包含一个测试用例。 每个测试的第一行包括两个正整数，表示灯的数量N(1<=N<=100)和开关的数量M(1<=M<=100)。灯的编号从1到N。 接下来M行，每行的开头是一个整数，表示这个开关控制的灯的数量X(0<=X<=N)，接下来是X个不相同的数字，表示这个开关控制的灯的编号。
Output
如果可以用这些开关关掉所有灯，输出”YES”。否则，输出”NO”。
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;
… Read the rest

Playing with Paper CodeForces – 527A

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

求GCD，答案是每次加上a/b；

#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);
}

 … Read the rest

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
… Read the rest

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
… Read the rest

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
… Read the rest

线性同余方程组的合并

类似于

[latex][/latex]

a_ix\equiv b_i\mod m_i

的方程组就是线性同余方程组
根据同余的可加性，可令

x\equiv B \mod lcm(m_i)

所以答案就转化为了求B和lcm

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

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)

把t带入

x=B_1+m_1*t

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

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);
… Read the rest

【容斥原理】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},
… Read the rest

【矩阵快速幂】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
… Read the rest

【离线并查集】问题集合

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

并查集维护每个点右边最近的未修改的点，把操作全部读入以后倒序处理，因为是倒着处理所以每个点只能被修改一次，直接用数组记录就可以了。初始f[i]=i;当l..r合并以后区间内每个f[i]=i+1;查询函数加上路径压缩，当遇见一个被改变过的点可以立刻跳过后面所有被改变了的点

#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]);
}

 … Read the rest