标签存档：数学题

【题目大意】
给定一个Q，让你输出最小的n，使得n!末位的0的个数=Q。
n>=1。
如果没有，那么输出无解。
【算法分析】
显然末位0的个数随关于n单调递增，那么二分答案，并分解n!，看里面有多少个·素因子5就等于知道末位有多少个0了。
首先n!里，2肯定比5要多。而只有2*5=10。所以看5有多少个就可以了。
然后对于这个求法，你可以先把n化为5进制数，然后一位一位截过去，很容易理解这个做法。
【其它】原来外国的自然数是从1开始的，怎么我们的教材是从0开始的呢T_T。
【CODE】C++ CODE   :SGU154 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930313233 #include

【题目大意】
求 % m
【算法分析】
首先我们发现答案是指关于n的一个函数。
那么我们把小数据暴力一下，得到下表：
0 0 0
1 1 1
2 3 2
3 8 5
4 21 13
5 55 34
6 144 89
7 377 233
8 987 610
9 2584 1597
10 6765 4181
11 17711 10946
12 46368 28657
13 121393 75025
14 317811 196418
15 832040 514229
16 2178309 1346269
17 5702887 3524578
18 14930352 9227465
19 39088169 24157817
20 102334155 63245986
21 267914296 165580141
22 701408733 433494437
23 1836311903 1134903170
24 4807526976 2971215073
25 12586269025 7778742049
26 32951280099 20365011074
27 86267571272 53316291173
28 225851433717 139583862445
29 591286729879 365435296162
30 1548008755920 956722026041
其中第一个是序号，第二个是答案，第三个是ans[i]-ans[i-1]。
设第三个是p[i]，那么容易发现p[i]=3*p[i-1]-p[i-2]。
然后列出矩阵求解即可。
【其它】
居然WA了好多遍。。。真不可饶恕啊= =。
WA的原因是：n=0时没有答案输出来。。。。
【CODE】
#include #include #include #include using namespace std;
typedef __int64 lld;
lld n,mod;
lld a[1][3];
lld c[3][3],p[3][3],res[3][3];

void Pow(lld cf){
if (cf==1){
memcpy(p,c,sizeof(c));
return;
}
lld i,j,k;
Pow(cf/2);
memset(res,0,sizeof(res));
for (i=0;i<3;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=(res[i][j]+p[i][k]*p[k][j])%mod;
memcpy(p,res,sizeof(res));
if (cf%2){
memset(res,0,sizeof(res));
for (i=0;i<3;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=(res[i][j]+p[i][k]*c[k][j])%mod;
memcpy(p,res,sizeof(res));
}
}

void solve(){
a[0][0]=1; a[0][1]=1; a[0][2]=2;
c[0][0]=1; c[0][1]=0; c[0][2]=0;
c[1][0]=0; c[1][1]=0; c[1][2]=-1;
c[2][0]=1; c[2][1]=1; c[2][2]=3;
Pow(n-1);
lld i,j,k;
memset(res,0,sizeof(res));
for (i=0;i<1;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=((res[i][j]+a[i][k]*p[k][j])%mod+mod)%mod;
cout << (res[0][0]+mod)%mod << "n";
}

int main(){
lld Tc;
cin >> Tc;
for (lld i=0;i cin >> n >> mod;
if (n==0) cout << "0n";
if (n==1) cout << 1%mod << "n";
if (n>=2) solve();
}
}

【题目】

提交文件：tri.pas/.cpp

输入文件：tri.in

输出文件：tri.out

 

　　把3个相同的小三角形按如下方式连接起来就形成了一个一级三角阵。

　　我们把位于顶端的小三角形标记为T，位于左端的小三角形标记为L，位于右端的小三角形标记为R。

　　把3个一级三角阵按同样的方式连接起来就形成了一个二级三角阵。

　　我们为顶端的三角阵的标记添加前缀T，为左端的三角阵的标记添加前缀L，为右端的三角阵的标记添加前缀R。

把3个二级三角阵按同样的方式连接起来就形成了一个三级三角阵。

同样地为顶端的三角阵的标记添加前缀T，为左端的三角阵的标记添加前缀L，为右端的三角阵的标记添加前缀R。

依次类推，可以构建一个N级三角阵。

如果两个小三角形有公共点，则认为这两个小三角形相邻，可以一步到达。

你的任务是求从一个小三角形走到另一个小三角形至少需要多少步。

 

输入格式：

第一行是三角阵的等级Ｎ（Ｎ≤30）。

第二行和第三行都是一个长度为N的字符串，由大写字母“L”、“R”、“T”组成，表示两个小三角形的标号。

 

输出格式：

输出一个数，表示从一个小三角形走到另一个小三角形所需的最少步数。

 

输入样例：

3

TRL

RLR

 

输出样例：

5

 

样例解释：

从“TRL”出发，途经“TRR”、“RTT”、“RTL”、“RLT”，最后到达“RLR”，一共需要5步。

【算法分析】
首先我们围观它走一步的话，那个字符串会有什么变化。
第一种可能："abc"->"abk" 然后这个这个c和k是可以任意的。
第二种可能："xyzabbbbbbb…bbbbb"->"xyzbaaaaaaa…aaaaa"，当然，这个a和b不能相同。
于是可以很直接地得到一个走到本三角顶点的算法。
那就是从高位到低位，一位一位地处理，具体自己YY吧，不难。
并且容易发现他是最优的。（怎么发现？看图。。。）
然后对于A串和B串，我们先把相同的前缀删掉。
对于剩下的东西而言。有两种可能。
剩下的设长度为n。
1、从我所属于的这个(n-1)级三角形直接走到对象的那个(n-1)级三角形。
2、从我所属于的这个(n-1)级三角形绕路另一个(n-1)级三角形，再跑到对象的那个(n-1)三角形。
于是分开两种情况，min一下即可。
【CODE】
#include #include #include typedef __int64 lld;
const int N=55;
int n;
char str1[N],str2[N],s1[N],s2[N];

lld solve(char *ss1,char *ss2){
memcpy(s1,ss1,sizeof(s1));
memcpy(s2,ss2,sizeof(s2));
int i,j,k;
lld ans=0;
for (i=1;i<=n;i++)
if (s1[i]!=s2[i]){
for (j=n;j>i;j–)
if (s2[i]!=s1[j]){
ans+=(lld)(1)<<(n-j);
s1[j]=s2[i];
}
ans++;
for (j=n;j>i;j–) s1[j]=s1[i];
s1[i]=s2[i];
}
return ans;
}

void work(){
if (strcmp(str1+1,str2+1)==0) puts("0");
else{
lld ans=solve(str1,str2);
char str[N];
memcpy(str,str2,sizeof(str));
int i=1,j;
while (str1[i]==str2[i]) i++;
if (str1[i]==’T’){
if (str2[i]==’L’) str[i]=’R’;
if (str2[i]==’R’) str[i]=’L’;
}
if (str1[i]==’L’){
if (str2[i]==’T’) str[i]=’R’;
if (str2[i]==’R’) str[i]=’T’;
}
if (str1[i]==’R’){
if (str2[i]==’L’) str[i]=’T’;
if (str2[i]==’T’) str[i]=’L’;
}
for (j=i+1;j<=n;j++) str[j]=str1[i];
lld now=solve(str1,str)+solve(str,str2);
if (now printf("%I64dn",ans);
}
}

int main(){
freopen("tri.in","r",stdin);
freopen("tri.out","w",stdout);
scanf("%d%s%s",&n,str1+1,str2+1);
work();
return 0;
}

【题目大意】
给定n个工作，m条通道。
然后这m条通道要么全部一起完成工作，要么只有1条在完成工作，求把n个工作全部做完至少需要多长时间。
【算法分析】
http://hi.baidu.com/pojoflcc/blog/item/a5e757816511ccdb9123d9b4.html
Lcc大神也写了解题报告，但是他的方法思路过于繁杂。。。虽然也可以做到排序的复杂度。
实际上，我们就是要让n个工作的并行时间尽可能地长。

姑且设这个并行时间为ans。
本题容易得到一个二分ans的算法。
具体是：
先二分ans。
然后将大于ans的工作时间置为ans。最后判定所有工作时间的和是否>=ans*m
是，则可行，否则不可行。
（想象你在填一个m*ans的表，就很容易理解）

然后现在根据GXX神牛的指示。
实际上不需要二分答案。

我们现在来看。假设我们将工作时间Ai已经按降序排列。
并再次假设A[i]<=ans<=A[i+1]
那么类似二分的判定的地方得到一个不等式
S[i+1,n]+i*ans>=m*ans     （S[i,j]表示从a[i]到a[j]的和）
于是我们整理一下，得出3个不等式：
ans>=A[i]           ——————①
ans<=A[i+1]       ——————②
ans<=S/(m-i)     ——————③
然后解它们看在这个区间有无解就行了。
可能大家觉得第③式有点问题。就是那个(m-i)的正负不知道，所以不等式不知道要不要变号。
实际上，在i递增到m=i时，必然就有解，所以不会出现m于是问题得到完美解决。
【时间复杂度】排序O(n lg n)+处理O(n)
【空间复杂度】O(n)
【其它】
1、深深地YM GXX神牛
2、注意到那个二分的解法，本题精度要求是1e-9，所以很容易挂。。。当然也是有可能AC的。
【CODE】
#include #include #include #define AA (*((double*)A))
#define BB (*((double*)B))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const int N=1005;
int m,n;
double a[N],s[N],ans,x;

void solve(){
ans=0;
a[n+1]=s[n+1]=0;
a[0]=1e20;
for (int i=n;i>=1;i–) s[i]=s[i+1]+a[i];
for (int i=0;i<=n;i++)
if (i==m){
ans=a[i];
break;
}else
if (m>i){
x=min(a[i],s[i+1]/(m-i));
if (x>=a[i+1]){
ans=x;
break;
}
}
printf("%.9lfn",s[1]-ans*m+ans);
}

int cmp(const void *A,const void *B){
if (AA if (AA>BB) return -1;
return 0;
}

int main(){
while (scanf("%d%d",&m,&n)!=EOF){
for (int i=1;i<=n;i++) scanf("%lf",&a[i]);
qsort(a+1,n,sizeof(double),cmp);
solve();
}
}

【题目大意】
求G^(Sum(C(n,i))) % 999911659
其中i | n。
【算法分析】
我们来围观999911659这个数字。
首先他是一个素数。其次，它-1以后是一个square free number。
素数有什么性质呢？
那就是a^x = a^(x % phi(p)) (mod p)。其中p是素数。
然后phi(素数)=这个素数-1。
现在问题聚焦成求 Sum(C(n,i)) % 999911658。  其中 i | n
由于那个可爱的999911658是square free number，于是我们将他分解质因数。
发现只有4个素因子，分别是2、3、4679、35617
然后呢？
因为是分解质因数，所以它们都是素数（废话=.=）
我们单独对这4个素因子求Sum(C(n,i)) % p。
于是乎因为p是素数，所以我们来一个Lucas定理，就可以很方便的算出组合数。
当然，期间还要用到我以前说的“不知名定理”（实际上叫“欧拉定理”）。
（不知道的同学看这里：http://hi.baidu.com/edwardmj/blog/item/24c2e52c0133625c4fc2264a.html）
最后呢，我们得出4个同余方程：
X=A1 (mod 2)
X=A2 (mod 3)
X=A3 (mod 4679)
X=A4 (mod 35617)
好嘞，由于mod的都是素数，所以必然它们是两两互质的。
所以直接上中国剩余定理。
不知道的同学可以参照《算法艺术与信息学竞赛》 （黑书）的P231。
当然这里面涉及到的拓展欧几里得算法在黑书里也有，位于P219。
【其它】
这里面有个小技巧，就是由于算组合数时要用到那个阶乘，可以预处理出来。
由于使用了Lucas定理，所以每个阶乘都不会超过要mod的那个数字。
于是只用处理4个数组，它们的长度分别是2、3、4679、35617。
令人激动的是：1A。
更令人激动的是：
1 27533 edward_mj 632K 15MS G++ 2.04K 2010-06-02 21:14:09 2 27541 AekdyCoin 404K 30MS G++ 2.30K 2010-06-02 21:33:18 3 27538 AekdyCoin 456K 30MS G++ 2.78K 2010-06-02 21:27:11 4 27543 AekdyCoin 400K 45MS G++ 2.17K 2010-06-02 21:36:11 5 27546 AekdyCoin 396K 60MS G++ 2.14K 2010-06-02 21:41:21 6 26437 sonicmisora 412K 230MS G++ 1.92K 2010-05-28 10:56:15 7 26483 zxytim 384K 307MS G++ 2.50K 2010-05-28 14:05:33 8 26349 root 1344K 384MS G++ 2.67K 2010-05-27 20:19:52 9 27515 sevenk 348K 762MS G++ 3.55K 2010-06-02 20:48:10 10 26890 AekdyCoin 348K 777MS G++ 3.04K 2010-05-30 20:43:11 11 26886 AekdyCoin 352K 808MS G++ 2.90K 2010-05-30 20:32:14 12 26438 hyf042 844K 929MS G++ 2.69K 2010-05-28 11:05:21 13 26891 AekdyCoin 288K 933MS G++ 3.31K 2010-05-30 20:52:39 当然，师傅由于之前写疵，所以后面那堆是他在疵状态下写的。
前面的是在使用了那个小技巧之后的时间。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const int phi=999911658;
int mm=999911659;
const int N=200000;
struct zys{int L[N],Num[N],t;}pz,nz;
int n,G;
lld a[N];
lld JC[5][37777];

void Div(zys &p,int x){
p.t=0;
for (int i=2;i*i<=x;i++)
if (x%i==0){
p.L[++p.t]=i;
p.Num[p.t]=0;
while (x%i==0){
p.Num[p.t]++;
x/=i;
}
}
if (x!=1) {p.L[++p.t]=x; p.Num[p.t]=1;}
}

void makejc(){
int i,j;
for (i=1;i<=4;i++){
JC[i][0]=1;
for (j=1;j<=pz.L[i];j++)
JC[i][j]=JC[i][j-1]*j%pz.L[i];
}
}

lld Pow_mod(lld x,lld cf,int &mod){
if (cf==0) return 1;
lld res=Pow_mod(x,cf/2,mod);
res=res*res%mod;
if (cf%2) res=res*x%mod;
return res;
}

lld Normal_C(int m,int n,int i){
int p=pz.L[i];
return JC[i][m]*Pow_mod(JC[i][n]*JC[i][m-n]%p,p-2,p)%p;
}

lld C(int m,int n,int i){
if (!n) return 1;
int p=pz.L[i];
if (m%p return Normal_C(m%p,n%p,i)*C(m/p,n/p,i)%p;
}

void deal(int sum){
for (int i=1;i<=4;i++)
a[i]=(a[i]+C(n,sum,i))%pz.L[i];
}

void dfs(int dep,int sum){
if (dep>nz.t){
deal(sum);
return;
}
dfs(dep+1,sum);
for (int i=1;i<=nz.Num[dep];i++){
sum*=nz.L[dep];
dfs(dep+1,sum);
}
}

lld exgcd(lld a,lld b,lld &x,lld &y){
if (!b){
x=1; y=0;
return a;
}
lld res=exgcd(b,a%b,x,y),t;
t=x;
x=y;
y=t-a/b*y;
}

void solve(){
lld i,j,Mi,ans=0,p,q,M=phi;
for (i=1;i<=4;i++){
Mi=M/pz.L[i];
exgcd(Mi,pz.L[i],p,q);
ans=(ans+Mi*p*a[i])%M;
}
if (ans<0) ans+=M;
cout << Pow_mod(G,ans,mm) << "n";
}

int main(){
cin >> n >> G;
G%=mm;
if (G==0) {printf("0n"); return 0;}
Div(pz,phi);
Div(nz,n);
makejc();
dfs(1,1);
solve();
return 0;
}