/*f[nowx][nowy]=sigma(f[tox][toy]); k=0:ans=sigma(f[nowx][nowy])以上动态转移显然全部数据要+ 二项式定理：bilibala…… //数学弱，日后再推吧 */#include<cstdio>#define O3 __attribute__((optimize("O3")))#define IN inlineusing 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\n",ans[i]);    fclose(stdin);fclose(stdout);    return 0; }

/*离线预处理：多重背包正扫一遍，反扫一遍 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\n",ans);    }    fclose(stdin);fclose(stdout);    return 0;}

//思路很好懂，然而还要套二项式,~~ #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;}