题目：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
#define O3 __attribute__((optimize("O3")))
#define IN inline
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();} return x*f; } const int N=,M=,p=,inf=0x3f3f3f3f; const int dx[]={,,,-},dy[]={,-,,}; 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]=; for(int d=;d<;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[]=dp[tox][toy][]+;
for(int i=;i<=k;i++){
t[i]=dp[tox][toy][i];
for(int j=;j<=i;j++){
t[i]+=((j&)?:-)*c[i][j]*t[i-j];
t[i]%=p;
}
}
for(int i=;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=;i<=n+;i++) a[i][]=a[i][m+]=inf;
for(int i=;i<=m;i++) a[][i]=a[n+][i]=inf;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
a[i][j]=read();
}
}
for(int i=;i<=k;i++){
c[i][]=;
for(int j=;j<=i;j++){
c[i][j]=c[i-][j]+c[i-][j-];
c[i][j]%=p;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(!vis[i][j]) dfs(i,j);
for(int t=;t<=k;t++){
ans[t]+=dp[i][j][t];
ans[t]%=p;
}
}
}
for(int i=;i<=k;i++) if(ans[i]<) ans[i]+=p;
for(int i=;i<=k;i++) printf("%d\n",ans[i]);
fclose(stdin);fclose(stdout);
return ;
}

knapsack

/*
离线预处理：多重背包正扫一遍，反扫一遍
ans=max(f[k1][j]+f_rev[k1+2][t1-j]){0<=j<=t1} attention: 习惯了一维的二进制拆分，二位的多重背包居然不会了~~ */ #include
#include
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();} return x*f; } const int N=; int n,m,v[N],w[N],c[N],f[N][N],f_rev[N][N]; void pre_deal(){ for(int i=,tmp;i<=n;i++){ tmp=c[i]; for(int j=;j<=;j++) f[i][j]=f[i-][j]; for(int j=;tmp!=;j<<=){ j=min(j,tmp); tmp-=j; for(int k=;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>=;i--){
tmp=c[i];
for(int j=;j<=;j++) f_rev[i][j]=f_rev[i+][j]; for(int j=;tmp!=;j<<=){ j=min(j,tmp); tmp-=j; for(int k=;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=;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=;
for(int j=;j<=t1;j++) ans=max(ans,f[k1][j]+f_rev[k1+][t1-j]);
printf("%d\n",ans);
}
fclose(stdin);fclose(stdout);
return ;
}

remainder

//思路很好懂，然而还要套二项式,~~
#include
#include
using namespace std;
typedef long long ll;
const ll N=,mod=;
ll n,m,ans,sum,tmp,f[N][N*N/];//f(i,j)=长为i,余数和为j
#define name "remainder"
int main(){
freopen(name".in","r",stdin);
freopen(name".out","w",stdout);
cin>>n>>m;
f[][]=;
for(int k=;k=;i--){
for(int j=k*(k-)/;j>=;j--){
f[i+][j+k]+=f[i][j];
f[i+][j+k]%=mod;
}
}
}
for(int i=;i<=m*(m-)/;i++){
if((n-i)%m) continue;
for(int j=;j<=m;j++){
tmp=(n-i)/m+j-;
tmp%=mod;
sum=;
for(int k=;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 ;
}