HDU 5832 A water problemHDU 5833 Zhu and 772002HDU 5838 Mountain

HDU 5832 A water problem

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } char n[10000000+10]; int main() { // freopen("A.in","r",stdin); // freopen(".out","w",stdout); int kcase=1; while(~scanf("%s",n)) { printf("Case #%d: ",kcase++); int t=0; int len=strlen(n); Rep(i,len) { t=t*10+n[i]-'0'; t%=10001; } if (!t) puts("YES") ; else puts("NO"); } return 0; }

HDU 5833 Zhu and 772002

There are n numbers a1,a2,…,an. The value of the prime factors of each number does not exceed 2000, you can choose at least one number and multiply them, then you can get a number b.

How many different ways of choices can make b is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007. (1≤n≤300),(1≤ai≤10^18).

想到xor方程就行

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase) printf("Case #%d:\n",kcase); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (2000+10) int p[MAXN],tot; bool b[MAXN]={0}; void make_prime(int n) { tot=0; Fork(i,2,n) { if (!b[i]) p[++tot]=i; For(j,tot) { if (i*p[j]>n) break; b[i*p[j]]=1; if (i%p[j]==0) break; } } } ll A[400]; int n; ull a[400][10]; bool cmp(int i,int j) { Rep(k,10) if (a[i][k]^a[j][k]) return a[i][k]<a[j][k]; return 0; } void swap2(int i,int j) { Rep(k,10) if (a[i][k]^a[j][k]) swap(a[i][k],a[j][k]); } bool is_0(int i) { Rep(k,10) if (a[i][k]) return 0; return 1; } void upd_min(int K,int i) { // a[k]=min(a[k],a[k]^a[i]); int p=305; Rep(k,10) a[p][k]=a[K][k]^a[i][k]; if (cmp(p,K)) swap2(p,K); } int gauss(int n) { For(i,n) { Fork(j,i+1,n) if (cmp(i,j)) swap2(i,j); if (is_0(i)) return i-1; For(k,n) if (i^k) { upd_min(k,i); // a[k]=min(a[k],a[k]^a[i]); } } return n; } ll pow2(ll a,ll b) { if (b==1) return a%F; if (!b) return 1%F; ll p=pow2(a,b/2); p=mul(p,p); if (b&1) p=mul(p,a); return p; } int main() { // freopen("B.in","r",stdin); // freopen(".out","w",stdout); int T=read(); make_prime(2000); For(kcase,T) { n=read(); For(i,n) scanf("%I64d",&A[i]); MEM(a) For(i,n) { ull t=1; For(j,tot) { int p1=(j-1)/50,p2=(j-1)%50; if (!p2) t=1; bool b=0; while(A[i]%p[j]==0) { A[i]/=p[j]; b=!b; } if (b) a[i][p1]|=t; t*=2; } } int p0=n-gauss(n); ll ans=pow2(2,p0); ans=sub(ans,1); Pr(kcase); // printf("%I64d\n",ans); cout<<ans<<endl; } return 0; }

HDU 5838 Mountain

同BZOJ 2669([cqoi2012]局部极小值-状态压缩+dp) http://blog.csdn.net/nike0good/article/details/52207269

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> #include<iomanip> #include<vector> #include<string> #include<queue> #include<stack> #include<map> #include<sstream> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (772002) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase) printf("Case #%d: ",kcase); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN (100) int n,m; int p2[30]; ll f[MAXN][1<<9]; int g[MAXN],g2[MAXN],dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; bool inside(int x,int y) { return 1<=x&&1<=y&&x<=n&&y<=m; } int id[MAXN][MAXN]; int idx(int i,int j) { return (i-1)*m+j-1; } int x[MAXN],y[MAXN],siz=0; int b[30]; int calc() { memset(b,-1,sizeof(b)); For(i,n) For(j,m) id[i][j]=idx(i,j); MEM(g) MEM(g2) Rep(i,siz) { int X=x[i],Y=y[i]; g2[i]=1<<idx(X,Y); b[id[X][Y]]=i; Rep(di,8) { int a=X+dir[di][0],b=Y+dir[di][1]; if (inside(a,b)) { int p=1<<idx(a,b); g[i]|=p; } } } MEM(f) f[0][0]=1; int S=1<<siz; int all=(1<<(n*m))-1; Rep(i,n*m) { Rep(st,S) if (f[i][st]) { int now=all; Rep(j,siz) if (st&p2[j]) { now-=now&g2[j]; } else { now-=now&g[j]; } int tot=0; int tot1=0,tot2=0; Rep(p,n*m) if (now&p2[p]) { tot++; if (-1 == b[p]) tot2++; else tot1++; } int lef=n*m-i; int choseX=siz-tot1; int useBlank=i-choseX; tot2-=useBlank; tot2=min(tot2,lef-tot1); if (tot2>0) upd(f[i+1][st],mul(tot2,f[i][st])); Rep(p,n*m) { if (now&p2[p]) { if (b[p]==-1) { } else { upd(f[i+1][st|p2[b[p]]],f[i][st]); } } } } } // Rep(p,S) cout<<f[n*m][p]<<endl; return f[n*m][S-1]; } bool ma[6][6]; ll ans=0; void dfs(int dep,int l) { if (dep==1) upd(ans,calc()); else ans=sub(ans,calc()); For(i,n) For(j,m) if (idx(i,j)>=l && !ma[i][j]){ bool fl=0; Rep(di,8) { int a=i+dir[di][0],b=j+dir[di][1]; if (!inside(a,b)) continue; if (ma[a][b]) { fl=1; break; } } if (!fl) { ma[i][j]=1; x[siz]=i,y[siz]=j; ++siz; dfs(-dep,idx(i,j)+1); ma[i][j]=0; --siz; } } } int main() { // freopen("F.in","r",stdin); // freopen("F.out","w",stdout); p2[0]=1; For(i,25) p2[i]=p2[i-1]*2; int kcase=1; while(cin>>n>>m) { siz=0; For(i,n) { char s[10]; scanf("%s",s); Rep(j,m) if (s[j]=='X') { x[siz]=i; y[siz]=j+1; ++siz; ma[i][j+1]=1; } else ma[i][j+1]=0; } Pr(kcase++); ans=0; if (siz<=9) dfs(1,0); cout<<ans<<endl; } return 0; }