标签存档：数学题

【题目】

Description

　　有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边，一共有 n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。如图0所示是一个4-五角形圈。
现在给定一个n五角形圈，你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗？一个图的生成树是保留原图的所有顶点以及顶 点的数目减去一这么多条边,从而生成的一棵树。
注意：在给定的n五角形圈中所有顶点均视为不同的顶点。

Input

输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组测试数据包含一个整数n( )，代表你需要求解的五角形圈中心的边数。

Output

对每一组测试数据，输出一行包含一个整数x，表示n五角形圈的生成树数目模2007之后的结果。

Sample Input

1
2

Sample Output

40

【算法分析】
把每一个五边形当成一个状态，并按顺时针进行编号。
那么第i个状态和其它状态连接的就只有在中心圈中对应的两个点。
然后我们考虑最终必然是有且仅有一个状态是中心圈对应的点并非通过该五边形连接的。
这个特殊的状态必然是去掉圈上边和剩下四条边的任意一条。所以有4种删边法。
除了这个状态以后，其它状态都是独立的，并且应当只去掉1条边。
一共五条边，所以就是有5种情况。
所以，根据乘法原理，答案应该是4*5^(n-1)。
又由于那个特殊的状态可以分步在n个状态中的任意一个，并且所得结果必然都是不同的。
所以最终结果：4*n*5^(n-1)。
【CODE】
#include #include #include const int mod=2007;
int n,ans;

void solve(){
ans=1;
for (int i=1;i ans=ans*4%mod;
ans=ans*n%mod;
printf("%dn",ans);
}

int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%d",&n);
solve();
}
}

【题目地址】http://acm.fzu.edu.cn/problem.php?pid=1833
【题目大意】
求P(sum(Ai),n*n) / (A1! * A2! * A3! …… * Ak!)
根据出题人福大核武的指示，本题考的是数论，并不是组合数学，而由于这个公式已经水得连我都能推出来，就直接写算了。。。
【算法分析】
首先做之前应该清楚几点：
1、一个数n的素因子是O(lg n)级别的。
2、没有任何辅助工具(素数表之类)的时候，将一个数分解质因数的复杂度是O(sqrt(n))级别的。
3、AC大神的 n! 质因数分解模板的复杂度是好吧，你也许会觉得这非常脑残，但是，我就是脑残地没搞清。。。

做法：
1、对M分解质因数
2、对公式的分母中红字部分分解质因数，并且分开自己拥有的质因数和M所拥有的质因数。
3、由于Sum<=100*5000，所以可以暴力求P(sum,n*n)。就是直接从n*n乘到n*n-sum+1。
乘的过程中把M所含的质因子也分离开来，和上面的那个蓝色的进行幂减。幂减以后，把各部分再分别合起来，弄成分子s1和分母s2，我们就可以惊讶地发现。。。gcd(s2，M)=1。
4、由于gcd(s2，M)=1，那么对应的 s1 = s2*x (mod M) 的解就变成了唯一的。（这个不知道对不对=_=，不会证明）
5、对于那个模线性方程，变形得 s1= s2*x + M*y。这个用欧几里得拓展算法搞定。

【其他】
Orz AC大神~
据其指示，时间和第一名居然是一样的~
1WA、1TLE。。。
WA：
最后一步搞了一会儿，一开始以为直接 s1 * s2^(M-2) % M，但是原来M必须为质数才能搞。
上面的第4步得到的gcd(s2,M)=1并不能让这个公式成立。。。
TLE：
我脑残地不听AC大神的劝告，直接枚举答案求逆元去了。。。

再Orz 一下我的各种脑残。。。果然数论我已经水到一种境界了。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
int n,mod,cn,mtot,tot2;
int a[105];
int pl[50],cl[50],pl2[5005],cl2[5005];
bool ss[5005],hash[5005];
lld s1,s2;

void init(){
int i,j;
tot2=0;
memset(ss,true,sizeof(ss));
for (i=2;i*i<=5000;i++)
for (j=2;i*j<=5000;j++)
ss[i*j]=false;
for (i=2;i<=5000;i++)
if (!hash[i] && ss[i])
pl2[++tot2]=i;
}

void dealm(){
int i,j,x=mod;
bool flag;
for (i=2;i*i<=mod;i++){
flag=true;
while (x%i==0){
if (i<=5000) hash[i]=true;
if (flag) pl[++mtot]=i;
x/=i;
flag=false;
}
}
if (x!=1){
pl[++mtot]=x;
if (x<=5000) hash[x]=true;
}
}

void Div(int *list,int n){
if (!n) return;
int i,tmp;
for (i=1;i<=mtot && pl[i]<=n;i++){
tmp=n;
while (tmp/pl[i]){
list[i]-=tmp/pl[i];
tmp/=pl[i];
}
}
}

void Div2(int *list,int n){
if (!n) return;
int i,tmp;
for (i=1;i<=tot2 && pl2[i]<=n;i++){
tmp=n;
while (tmp/pl2[i]){
list[i]+=tmp/pl2[i];
tmp/=pl2[i];
}
}
}

void Fen(int x){
if (!x) return;
int i;
for (i=1;i<=mtot && x>=pl[i];i++)
while (x%pl[i]==0){
cl[i]++;
x/=pl[i];
}
s1=s1*x%mod;
}

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

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

void solve(){
lld x,y,rate=s1/exgcd(s2,mod,x,y);
x=x%mod*rate%mod;
x=(x+mod)%mod;
cout << x << endl;
}

int main(){
while (scanf("%d%d%d",&n,&mod,&cn)!=EOF){
mtot=0; tot2=0;
s1=1; s2=1;
memset(cl,0,sizeof(cl));
memset(hash,false,sizeof(hash));
memset(cl2,0,sizeof(cl2));
int sum=0;
for (int i=1;i<=cn;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
if (mod==1){
cout << 0 << endl;
continue;
}
dealm();
init();
for (int i=1;i<=cn;i++){
Div(cl,a[i]);
Div2(cl2,a[i]);
}
for (int i=n*n;i>n*n-sum;i–) Fen(i);
for (int i=1;i<=mtot;i++)
s1=s1*pow_mod(pl[i],cl[i])%mod;
for (int i=1;i<=tot2;i++)
s2=s2*pow_mod(pl2[i],cl2[i])%mod;
solve();
}
}

【题目】

Description

lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数 不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

Input

输入数据是一行，包括2个数字n和m

Output

输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数

Sample Input

2 2

Sample Output

2

Hint

对于30%的数据，保证1<=m<=n<=1000
对于100%的数据，保证1<=m<=n<=1000000 【算法分析】
容易推得公式是C(n,n+m)-C(m-1,n+m)
然后就是求组合数问题。
然后n!有一个快速质因数分解的方法，按照那个分解，然后将除法变为幂减，最终再将个因子乘起来（要用快速幂）。就可以得解。
【CODE】
#include #include #include #include using namespace std;
const int N=2000000;
const int mod=20100403;
typedef long long lld;
bool ss[N+5];
int n1[N/10],n2[N/10],n3[N/10],pl[N/10];
int n,m,tot;
lld s1,s2;

void init(){
int i,j;
memset(ss,true,sizeof(ss));
for (i=2;i*i<=N;i++)
if (ss[i])
for (j=2;i*j<=N;j++)
ss[i*j]=false;
tot=0;
for (i=2;i<=N;i++)
if (ss[i]) pl[tot++]=i;
}

void Div(int *list,int n){
int i,j,tmp;
for (i=0;i for (i=0;i tmp=n;
while (tmp/pl[i]){
list[i]+=tmp/pl[i];
tmp/=pl[i];
}
}
}

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

int main(){
init();
scanf("%d%d",&n,&m);
Div(n1,m+n);
Div(n2,n);
Div(n3,m);
for (int i=0;i n1[i]-=n2[i];
n1[i]-=n3[i];
}
s1=1;
for (int i=0;i s1*=pow(pl[i],n1[i]);
s1%=mod;
}
Div(n1,m+n);
Div(n2,n+1);
Div(n3,m-1);
for (int i=0;i n1[i]-=n2[i];
n1[i]-=n3[i];
}
s2=1;
for (int i=0;i s2*=pow(pl[i],n1[i]);
s2%=mod;
}
lld ans=s1-s2;
ans=((ans%mod)+mod)%mod;
cout << ans << endl;
}

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1041
【算法分析】
以下内容来自师傅AekdyCoin的blog以及口授
现在给定了一个方程a^2+b^2=c^2  （c已知）
这，就是勾股数。
然后勾股数有一个很霸气的定理。
1、a=m^2-n^2
2、b=2*m*n
3、c=m^2+n^2
4、gcd(n,m)=1。
5、gcd(a,b,c)=1。
同时满足这五条式的是一组勾股数，而且对于所有满足这五条式的(m,n)乘一个k(k>=1)，即(km,kn)。就可以表示所有的勾股数，并且勾股数和三元对(m,n,k)一一对应。
换句话说，每个勾股数都只能表示为一个三元对(m,n,k)。

好了，现在回到这题的算法上。
我们枚举k^2（程序中是变量：div），但是k这里有一个小技巧，并不需要枚举1<=k^2<=r，
只要枚举1<=k^2<=sqrt(r)即可。因为我们可以保证拆成的两个乘数的大小顺序。
然后枚举了k^2以后，
问题转化成能不能找到一对二元对(m,n)，满足：
1、gcd(m,n)=1
2、m^2+n^2==r/(k^2)
3、gcd(m^2-n^2,2*m*n,m^2+n^2)=1
然后这样暴力还是会很慢的，于是师傅就把第三个条件直接抽出来先判断。
我们可以从：1、3两式推出  r%4=1！
于是直接预先判断，里面那个复杂度为O(sqrt(r))的部分就很少会执行了！
然后算法甚至达到了接近O(sqrt(r))的复杂度。

【其它】
时间到了0MS。空间也没用什么。
膜拜AekdyCoin大神。。。
【CODE】
#include #include using namespace std;
int ans=0;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

void solve(int r){
if (r==1 || r%4!=1) return;
int m,n;
for (n=1;n*n*2 m=(int)(sqrt(r-n*n)+1e-5);
if (m*m+n*n!=r) continue;
if (gcd(m,n)==1 && m>n) ans++;
}
}

int main(){
int r,div;
cin >> r;
ans=0;
for (div=1;div*div<=r;div++){
if (r%div) continue;
solve(r/div);
solve(div);
}
ans*=8;
ans+=4;
cout << ans << endl;
}

【题目大意】

给定N个标号为1~N的点，让你求出对于这N个点，连一些边使得它成为无向连通图的方案有多少种。

【算法分析】

= =看了一下别人的思考过程。。。公式还是自己推的。。。

要利用补集思想，首先连边方案一共有2^(n*(n-1)/2)这么多种。（每条边取或者不取）

然后我们以于1连通的点的个数i为划分状态。

ans[n]=2^(n*(n-1)/2)-Q;

Q=SUM(ans[i]*C(i-1,n-1)*2^((n-i)*(n-i-1)/2))   1<=i

就是固定住1这个点，然后在剩下的n-1个点里取i-1个，总共i个点是1的联通块上的。

然后i个点的连通图有ans[i]这么多方案，所以乘起来，然后根据乘法原理，剩下有n-i个点，

能构成2^((n-i)*(n-i-1)/2)种方案，也都乘起来。

【其他】1A

跑得非常慢，在最后一面= =

【CODE】

#include #include #include using namespace std;
const int ml=372;

int n;
int C[55][55][ml+1];
int ans[55][ml+1];
int cf[1311][ml+1];
int tmp[ml+1],tmp2[ml+1];

struct BNT{
       void plus(int *x,int *y){
            for (int i=1;i<=ml;i++) x[i]+=y[i];
            for (int i=1;i                x[i+1]+=x[i]/10;
                x[i]%=10;
            }
       }

       void mul(int *x,int *y){
            memset(tmp,0,sizeof(tmp));
            for (int i=1;i<=ml;i++)
              for (int j=1;i+j-1<=ml;j++) tmp[i+j-1]+=x[i]*y[j];
            for (int i=1;i                tmp[i+1]+=tmp[i]/10;
                tmp[i]%=10;
            }
       }

       void dec(int *x,int *y){
            for (int i=1;i<=ml;i++) x[i]-=y[i];
            for (int i=1;i                while (x[i]<0){x[i]+=10; x[i+1]--;}
                while (x[i]>9){x[i]-=10; x[i+1]++;}
            }
       }
}Big;

void deal(int m){
     memcpy(ans[m],cf[m*(m-1)/2],sizeof(ans[m]));
     for (int i=1;i         Big.mul(ans[i],C[m-1][i-1]);
         memcpy(tmp2,tmp,sizeof(tmp));
         int q=m-i;
         Big.mul(tmp2,cf[q*(q-1)/2]);
         Big.dec(ans[m],tmp);
     }
}

void init(){
     memset(C,0,sizeof(C));
     memset(cf,0,sizeof(cf));
     C[0][0][1]=1;
     for (int i=1;i<=50;i++)
       for (int j=0;j<=i;j++){
           if (j) Big.plus(C[i][j],C[i-1][j-1]);
           Big.plus(C[i][j],C[i-1][j]);
       }
     cf[0][1]=1;
     for (int i=1;i<=1300;i++){
         for (int j=1;j<=ml;j++) cf[i][j]=cf[i-1][j]*2;
         for (int j=1;j             cf[i][j+1]+=cf[i][j]/10;
             cf[i][j]%=10;
         }
     }
     for (int i=1;i<=50;i++)
       deal(i);
}

void output(){
     int i=ml;
     while (!ans[n][i]) i–;
     for (int j=i;j>=1;j–) printf("%d",ans[n][j]);
     printf("n");
}

int main(){
    init();
    while (cin >> n && n) output();
}