gfoj

Problem 720: Chess

Time Limit: 1000 ms Memory Limit: 255998 KB

Problem Description 在一个n*m的棋盘上，要求每一行每一列都至少有一个棋子的总方案数是多少？由于答案有可能很大，所以输出答案对1000000007取模。

Input 两个整数n和m。

30% 1<=n,m<=5 100% 1<=n,m<=50

Output 一个整数表示总方案数模1000000007的值。

Sample Input 2 3

Sample Output 25

本题各种做法

dp(n^3)

dp[ i ] [ j ] 表示前i行中有j列放有棋子的方案数

#include<cstdio> #include<iostream> #define MOD 1000000007 #define N 60 using namespace std; typedef long long LL; LL a[N],dp[N][N],p,c[N][N]; int n,m; int main(){ scanf("%d%d",&n,&m); c[0][0]=1; for(int i=1;i<=m;i++) for(int j=0;j<=i;j++) if(j==0)c[i][j]=1; else c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD; a[0]=1; for(int i=1;i<=50;i++)a[i]=a[i-1]*2%MOD; dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=0;k<j;k++){ p=(dp[i-1][k]*a[k]%MOD)*c[m-k][j-k]%MOD; dp[i][j]=(dp[i][j]+p)%MOD; } p=dp[i-1][j]*(a[j]-1)%MOD; dp[i][j]=(dp[i][j]+p)%MOD; } } cout<<dp[n][m]; }

lzk(n^4)

#include<cstdio> #define ll long long using namespace std; const int N=50+5; const ll mod=1e9+7; ll c[N][N]; ll f[N][N]; ll qpow(int x) { if(x==0) return 1ll; ll ans=qpow(x/2); ans=ans*ans%mod; if(x&1) ans=ans*2%mod; return ans%mod; } int main() { c[0][0]=1; for(int i=1; i<=50; i++) { c[i][0]=1; for(int j=1; j<=i; j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } int n, m; scanf("%d%d", &n, &m); f[1][1]=1; for(int x=1; x<=n; x++) for(int y=1; y<=m; y++) { if(x==1&&y==1) continue; f[x][y]=qpow(x*y); for(int i=0; i<x; i++) for(int j=0; j<y; j++) { if(i==0&&j==0) continue; f[x][y]=(f[x][y]+mod-c[x][i]*c[y][j]%mod*f[x-i][y-j]%mod)%mod; } f[x][y]=(f[x][y]-1)%mod; } printf("%lld\n", f[n][m]); /* printf("\n"); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) printf("%lld ", f[i][j]); printf("\n"); } */ return 0; }

hz 容斥原理

∑i=0n(−1)i×Cin×(2n−i−1)m (2n−1)m−C(n,1)∗(2n−1−1)m+C(n,2)∗(2n−2−1)m−....+... 最后是加或减要看n的奇偶

#define mod 1000000007 using namespace std; typedef long long ll; int m,n,i; ll ans; ll pow(ll t,int k) { ll res = 1; for (int i=0;(k>>i);i++) { if ((k>>i)&1) res = (res * t) % mod; t = (t * t) % mod; } return res; } ll C(int a,int b) { ll res = 1; if (b*2 > a) b = a - b; for (int i=0;i<b;i++) res = ((res * (a-i)) % mod) * pow(i+1,mod-2) % mod; return res; } int main() { cin >> n >> m; for (i=n;i;i--) { if ((n-i) & 1) ans = (ans + mod - (C(n,n-i) * pow(pow(2,i)-1,m) % mod)) % mod; else ans = (ans + C(n,n-i) * pow(pow(2,i)-1,m)) % mod; } cout << ans; }

ssn&lsb 递归

#include<iostream> #include<cstring> #define ll long long using namespace std; const int maxn=60, MOD=1000000007; ll f[maxn], ys[maxn], n, m; ll mi(ll a, ll k) { if(k == 0) return 1; if(k == 1) return a%MOD; ll l = mi(a, k/2)%MOD; if(k & 1) return ((l*l%MOD)*a)%MOD; else return (l*l)%MOD; } ll C(ll a, ll k) { memset(ys, 0, sizeof(ys)); ll ret = 1; for(int i = a; i >= a-k+1; i--) { int b = i; for(int j = 2; j <= b; j++) while(b%j == 0) {ys[j]++; b /= j; } } for(int i = k; i >= 1; i--) { int b = i; for(int j = 2; j <= b; j++) while(b%j == 0) {ys[j]--; b /= j; } } for(int i = 1; i <= 50; i++) while(ys[i]--) ret = (ret*i)%MOD; return ret%MOD; } ll solve(ll x) { if(f[x]) return f[x]; ll ret; ret = mi(mi((ll)2, x)-1, m); for(int i = 1; i <= x; i++) ret = (ret-C(x, i) * solve(x-(ll)i)+MOD)%MOD; f[x] = ret; return ret%MOD; } int main() { cin >> n >> m; cout << solve(n) << endl; return 0; }

Problem 721: INTSUB

Time Limit: 1000 ms Memory Limit: 255999 KB

Problem Description 给出一个大小为2n的集合X=｛1，2，3，…，2n-1，2n｝，问该集合中有趣子集的数目，答案mod1e9+7。

x的有趣子集定义为，该子集中至少有两个数，a和b，b是a的倍数且a是集合中最小的元素。

Input 输入一个整数n

40% 1<=n<=50

100% 1<=n<=1000

Output 输出子集数目mod1e9+7的结果

Sample Input 3 Sample Output 47

分析

b是a的倍数 b有【n/a】个 所以答案为

∑i=1n2n/i−1∗2n−i−n/i+1

完整AC代码

其实不用快速幂

#include<cstdio> #include<iostream> #define MOD 1000000007 #define N 1010 using namespace std; typedef long long LL; int n,p; LL a[2*N],ans,q; LL Qpow(int q){ LL p=2,ans=1; while(q!=0){ if(q%2)ans=(ans*p)%MOD; p=(p*p)%MOD; q/=2; } return ans; } int main(){ scanf("%d",&n); n*=2; // for(int i=0;i<=n;i++)a[i]=Qpow(i); // for(int i=0;i<=n;i++)cout<<a[i]<<'\n'; for(int i=1;i<=n/2;i++){ p=(n/i)-1; if(!a[p])a[p]=Qpow(p); if(!a[n-i-p])a[n-i-p]=Qpow(n-i-p); q=((a[p]-1)*a[n-i-p])%MOD; ans=(ans+q)%MOD; // cout<<ans<<'\n'; } cout<<ans; }

Problem 722: MINSUB

Time Limit: 3000 ms Memory Limit: 256000 KB

Problem Description 给一个n*m矩阵M，和一个整数k，对于矩阵M的子矩阵M’，定义min(M’)为M’矩阵中元素的最小值。

我们需要找出这样一个子矩阵，该矩阵的面积至少为K，且min(M’)最大化。在min(M’)相同的情况下，面积越大越好。面积的定义为该矩阵的行数*列数。

Input 第一行两个整数n和m，表示矩阵的大小。

30% 1<=n,m<=50 100% 1<=n,m<=1000 1<=k<=n*m

Output 输出两个值，第一个是最大的min(M’)，第二个是该矩阵的最大面积。

Sample Input 3 3 2 1 2 3 4 5 6 7 8 9 Sample Output 8 2

分析

二分矩阵元素大小最小值 把矩阵转换为0-1矩阵 扫描线用单调队列（栈）统计比当前小的元素的位置 反过来再扫一边 统计答案 继续二分 时限3s

完整AC程序(3s,stl栈)

#include<cstdio> #include<iostream> #include<stack> #define N 1010 using namespace std; struct Node{ int v,w; }; stack<Node>s; int n,m,a[N][N],f[N][N],b[N],l,r,mid,c[N],k,ans,num,w; int Solve(int x){ int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]>=x)f[i][j]=f[i-1][j]+1; else f[i][j]=0; for(int i=1;i<=n;i++){ while(!s.empty()) s.pop(); for(int j=1;j<=m;j++){ while(!s.empty()&&s.top().v>f[i][j]) s.pop(); if(!s.empty()){ if(s.top().v==f[i][j])b[j]=b[s.top().w]; else b[j]=s.top().w+1; } else b[j]=j; s.push((Node){f[i][j],j}); } while(!s.empty()) s.pop(); for(int j=m;j>=1;j--){ while(!s.empty()&&s.top().v>f[i][j]) s.pop(); if(!s.empty()){ if(s.top().v==f[i][j])c[j]=b[s.top().w]; else c[j]=s.top().w-1; } else c[j]=j; s.push((Node){f[i][j],j}); } for(int j=1;j<=m;j++) ans=max(ans,(c[j]-b[j]+1)*f[i][j]); } return ans; } int main(){ freopen("data.txt","r",stdin); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); r=max(r,a[i][j]); } l=0; while(l<r){ int mid=(l+r)/2; if((w=Solve(mid))>=k){ if(mid>ans){ ans=mid; num=w; } l=mid+1; } else r=mid; } if((w=Solve(l))>=k){ if(l>ans){ ans=l; num=w; } } printf("%d %d\n",ans,num); }

标程（二分经我优化，可以跑进2s，类似kmp自配函数的单调队列）

#include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> using namespace std; int n, m, a[1001][1001], test, k, f[1001][1001], U[1001], D[1001],ma; int calc(int now) { memset(f, 0, sizeof(f)); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] >= now) f[i][j] = f[i][j - 1] + 1; else f[i][j] = 0; int area = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { int now = j - 1; for (; now && f[j][i] <= f[now][i]; now = U[now]); U[j] = now; } for (int j = n; j; --j) { int now = j + 1; for (; now != n + 1 && f[j][i] <= f[now][i]; now = D[now]); D[j] = now; } for (int j = 1; j <= n; j++) area = max(area, (D[j] - U[j] - 1) * f[j][i]); } return area; } int main() { freopen("data.txt","r",stdin); scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++){ scanf("%d", &a[i][j]); ma=max(ma,a[i][j]); } int Left = 0, Right = ma, Mid = (Left + Right) >> 1; for (; Left + 1 < Right; Mid = (Left + Right) >> 1) if (calc(Mid) >= k) Left = Mid; else Right = Mid; printf("%d %d\n", Left, calc(Left)); }