题目：http://files.cnblogs.com/files/shenben/2017-01-20problems.pdf
数据包（含解题报告）：http://files.cnblogs.com/files/shenben/2017-01-20_%E6%B5%8B%E8%AF%95%E5%8C%85.zip
plane
/* f[nowx][nowy]=sigma(f[tox][toy]); k=0:ans=sigma(f[nowx][nowy]) 以上动态转移显然 全部数据要+ 二项式定理：bilibala…… //数学弱，日后再推吧 */ #include<cstdio> #define O3 __attribute__((optimize("O3"))) #define IN inline using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int N=310,M=25,p=12345,inf=0x3f3f3f3f; const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; int n,m,k,c[M][M],a[N][N],dp[N][N][M],t[M],ans[M]; bool vis[N][N]; O3 IN void dfs(int nowx,int nowy){ vis[nowx][nowy]=1; for(int d=0;d<4;d++){ int tox=nowx+dx[d],toy=nowy+dy[d]; if(a[nowx][nowy]>a[tox][toy]){ if(!vis[tox][toy]) dfs(tox,toy); t[0]=dp[tox][toy][0]+1; for(int i=1;i<=k;i++){ t[i]=dp[tox][toy][i]; for(int j=1;j<=i;j++){ t[i]+=((j&1)?1:-1)*c[i][j]*t[i-j]; t[i]%=p; } } for(int i=0;i<=k;i++){ dp[nowx][nowy][i]+=t[i]; dp[nowx][nowy][i]%=p; } } } } #define name "plane" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();m=read();k=read(); for(int i=0;i<=n+1;i++) a[i][0]=a[i][m+1]=inf; for(int i=1;i<=m;i++) a[0][i]=a[n+1][i]=inf; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j]=read(); } } for(int i=0;i<=k;i++){ c[i][0]=1; for(int j=1;j<=i;j++){ c[i][j]=c[i-1][j]+c[i-1][j-1]; c[i][j]%=p; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(!vis[i][j]) dfs(i,j); for(int t=0;t<=k;t++){ ans[t]+=dp[i][j][t]; ans[t]%=p; } } } for(int i=0;i<=k;i++) if(ans[i]<0) ans[i]+=p; for(int i=0;i<=k;i++) printf("%d ",ans[i]); fclose(stdin);fclose(stdout); return 0; }
knapsack
/* 离线预处理：多重背包正扫一遍，反扫一遍 ans=max(f[k1][j]+f_rev[k1+2][t1-j]){0<=j<=t1} attention: 习惯了一维的二进制拆分，二位的多重背包居然不会了~~ */ #include<cstdio> #include<iostream> using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int N=1005; int n,m,v[N],w[N],c[N],f[N][N],f_rev[N][N]; void pre_deal(){ for(int i=1,tmp;i<=n;i++){ tmp=c[i]; for(int j=1;j<=1000;j++) f[i][j]=f[i-1][j]; for(int j=1;tmp!=0;j<<=1){ j=min(j,tmp); tmp-=j; for(int k=1000;k>=j*v[i];k--){ f[i][k]=max(f[i][k],f[i][k-j*v[i]]+j*w[i]); } } } for(int i=n,tmp;i>=1;i--){ tmp=c[i]; for(int j=1;j<=1000;j++) f_rev[i][j]=f_rev[i+1][j]; for(int j=1;tmp!=0;j<<=1){ j=min(j,tmp); tmp-=j; for(int k=1000;k>=j*v[i];k--){ f_rev[i][k]=max(f_rev[i][k],f_rev[i][k-j*v[i]]+j*w[i]); } } } } #define name "knapsack" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read(); for(int i=1;i<=n;i++) v[i]=read(),w[i]=read(),c[i]=read(); pre_deal(); m=read(); for(int k1,t1,ans;m--;){ k1=read();t1=read();ans=0; for(int j=0;j<=t1;j++) ans=max(ans,f[k1][j]+f_rev[k1+2][t1-j]); printf("%d ",ans); } fclose(stdin);fclose(stdout); return 0; }
remainder
//思路很好懂，然而还要套二项式,~~ #include<cstdio> #include<iostream> using namespace std; typedef long long ll; const ll N=305,mod=905229641; ll n,m,ans,sum,tmp,f[N][N*N/2];//f(i,j)=长为i,余数和为j #define name "remainder" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); cin>>n>>m; f[0][0]=1; for(int k=0;k<m;k++){ for(int i=k;i>=0;i--){ for(int j=k*(k-1)/2;j>=0;j--){ f[i+1][j+k]+=f[i][j]; f[i+1][j+k]%=mod; } } } for(int i=0;i<=m*(m-1)/2;i++){ if((n-i)%m) continue; for(int j=1;j<=m;j++){ tmp=(n-i)/m+j-1; tmp%=mod; sum=1; for(int k=1;k<j;k++){//C(n-tot+x-1,x-1) sum*=tmp; sum%=mod; tmp--; } sum*=j*f[j][i]%mod; sum%=mod; ans+=sum; ans%=mod; } } cout<<ans; fclose(stdin);fclose(stdout); return 0; }