BC div2補題以及 復習模除 逆元__BestCoder Round #78 (div.2)

　第一題沒話說 智商欠費 加老柴輔導終于過了

需要在意的是數據范圍為2的63次方-1 三個數相加肯定爆了

?? 四邊形的定義　　任意邊小于其余三邊之和

換句話說就是　　最長邊小于其余三邊之和

?? 這樣的話問題轉化為 最長邊依次減其余三邊的結果是否小于等于0

還有一點是題目出現0邊 即最小邊不為0 想得太多反而把0也算為合法。。。。

?? 問題只需要 sort一下 判斷a[0]==0||a[3]-a[2]-a[1]-a[0]>=0 輸出NO //存在0邊且最大邊大于其他邊之和

第二題 好多種姿勢 題目鏈接http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=683&pid=1002

官方題解

　　我們令dp[i][j]表示在前i個數中，選出若干個數使得它們的gcd為j的方案數，于是只需要枚舉第i+1個數是否被選中來轉移就可以了

令第i+1個數為v，當考慮dp[i][j]的時候，我們令$dp[i+1][j] += dp[i]j,dp[i+1][gcd(j,v)] += dp[i]j

復雜度O(N*MaxV) MaxV 為出現過的數的最大值

其實有O(MaxV *log(MaxV))的做法，我們考慮記f[i]表示從這些數中選擇若干個數，使得他們的gcd是i的倍數的方案數。假如有K個數是i的倍數，則 f[i]=2^K-1，再用g[i]表示從這些數中選擇若干個數，使得他們的gcd是i的方案數，則g[i]=f[i] - g[j] (對于所有j是i的倍數)。

由調和級數可以得到復雜度為O(MaxV *log(MaxV))

DP之二維數組轉移

　　我們把dp[i][j]作為考慮了第i個數GCD為j的方案數

直接gcd會超時 所以我們打個表GCD

　　那么dp[i][j]+=dp[i-1][j]; dp[i][GCD[j][v[i]]]+=dp[i-1][j]; 然后就可以轉移辣；

#include<cstdio>
#include<map>
//#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<queue>
#include<cstdlib>
#include<climits>
#define PI acos(-1.0)
#define INF 0x3fffffff
using namespace std;
typedef long long ll;
typedef __int64 int64;
const ll mood=1e9+7;
const int64 Mod=100000007;
const double eps=1e-9;
const int N=1005;
const int MAXN=250050;
typedef int rl;
inline void r(rl&num){num=0;rl f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}
int v[N];
int GCD[N][N];
int64 dp[N][N];
int main()
{for(int i=1;i<1001;i++){for(int j=1;j<=i;j++){GCD[i][j]=GCD[j][i]=gcd(i,j);}}int ci;r(ci);while(ci--){int n;r(n);int mx=-1;for(int i=1;i<=n;i++){r(v[i]);mx=max(mx,v[i]);dp[i][v[i]]=1;}for(int i=2;i<=n;i++){for(int j=1;j<=mx;j++){dp[i][j]+=dp[i-1][j];dp[i][j]%=Mod;dp[i][GCD[j][v[i]]]+=dp[i-1][j];dp[i][GCD[j][v[i]]]%=Mod;}}int64 ans=0;for(int i=1;i<=mx;i++){ans+=(dp[n][i]*i)%Mod;ans%=Mod;}memset(dp,0,sizeof(dp));memset(v,0,sizeof(v));printf("%I64d\n",ans);}return 0;
}

仔細想了一下 覺得可以優化為滾動數組 試了好久不對 最后瞎蒙

每個數都多考慮了一次 所以/2需要乘逆元 正好1e8+7是素數

Mod為素數，那么還可以根據費馬小定理得到逆元為 2的（Mod-2）次方%Mod

　　即除2等于乘2的（Mod-2）次方%Mod

所以加了一個快速冪 但是優化為滾動數組后 時間增加了一丟丟 但空間大幅度減少

16757862	2016-04-03 12:45:34	Accepted	5656	2511MS	5504K	1925 B	G++	zxMrlc
16755798	2016-04-03 00:36:10	Accepted	5656	2449MS	13404K	1722 B	G++	zxMrlc

但是姿勢老感覺有問題 等wtw學長指點后我再改改 還有官方的第二個姿勢還沒有學會。。。衰

#include<cstdio>
#include<map>
//#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<queue>
#include<cstdlib>
#include<climits>
#define PI acos(-1.0)
#define INF 0x3fffffff
using namespace std;
typedef long long ll;
typedef __int64 int64;
const ll mood=1e9+7;
const int64 Mod=100000007;
const double eps=1e-9;
const int N=1005;
const int MAXN=250050;
typedef int rl;
inline void r(rl&num){num=0;rl f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}
int v[N];
int GCD[N][N];
int64 dp[N];
int main()
{int64 xx=Mod-2;int64 an=1,t=2;while(xx>0){if(xx&1) an*=t;xx/=2;an%=Mod;t*=t;t%=Mod;}for(int i=1;i<1001;i++){for(int j=1;j<=i;j++){GCD[i][j]=GCD[j][i]=gcd(i,j);}}int ci;r(ci);while(ci--){int n;r(n);int mx=-1;for(int i=1;i<=n;i++){r(v[i]);mx=max(mx,v[i]);}for(int i=1;i<=n;i++){dp[v[i]]++;for(int j=1;j<=mx;j++){// dp[i][j]+=dp[i-1][j];dp[j]%=Mod;dp[GCD[j][v[i]]]+=dp[j];dp[GCD[j][v[i]]]%=Mod;}}int64 ans=0;//for(int i=1;i<=mx;i++) cout<<dp[i]<<endl;for(int i=1;i<=mx;i++){ans+=(dp[i]*i)%Mod;ans%=Mod;}memset(dp,0,sizeof(dp));memset(v,0,sizeof(v));printf("%I64d\n",ans*an%Mod);}return 0;
}

?我們每次加入的數據會導致翻倍 所以剛才改為加完/2；

因為添加的v[i]導致的影響就是 當前位置dp[v[i]]多1 即方案數多了選自己的 所以在循環結尾-1就ok了 。。。根本不需要模除 但時間特么變大了

還是有點模糊的 不太清楚到底怎么回事。

16758163

2016-04-03 13:17:49

Accepted

5656

2636MS

5504K

1730 B

G++

zxMrlc

?

#include<cstdio>
#include<map>
//#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<queue>
#include<cstdlib>
#include<climits>
#define PI acos(-1.0)
#define INF 0x3fffffff
using namespace std;
typedef long long ll;
typedef __int64 int64;
const ll mood=1e9+7;
const int64 Mod=100000007;
const double eps=1e-9;
const int N=1005;
const int MAXN=250050;
typedef int rl;
inline void r(rl&num){num=0;rl f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}
int v[N];
int GCD[N][N];
int64 dp[N];
int main()
{for(int i=1;i<1001;i++){for(int j=1;j<=i;j++){GCD[i][j]=GCD[j][i]=gcd(i,j);}}int ci;r(ci);while(ci--){int n;r(n);int mx=-1;for(int i=1;i<=n;i++){r(v[i]);mx=max(mx,v[i]);}for(int i=1;i<=n;i++){dp[v[i]]++;for(int j=1;j<=mx;j++){// dp[i][j]+=dp[i-1][j];dp[j]%=Mod;dp[GCD[j][v[i]]]+=dp[j];dp[GCD[j][v[i]]]%=Mod;}dp[v[i]]--;}int64 ans=0;for(int i=1;i<=mx;i++){ans+=(dp[i]*i)%Mod;ans%=Mod;}memset(dp,0,sizeof(dp));memset(v,0,sizeof(v));printf("%I64d\n",ans%Mod);}return 0;
}

?