T3

Portkey

1.1 $1\le n,k\le 30$

递推算组合数 （似乎这种方法还能再A一个点）

差评zgs的机子 不给这点分

1.2 特殊点

$p=2$判断奇偶性 $k=1$二项式定理 $k=2$跟二项式定理差不多

1.3

用一些稍微高级的方法 预处理啊，阶乘逆元啊之类的 不要暴力就行了

1.4

冯巨来也！

来一个生成函数 $$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=(1+z{)}^n[z^m]$$ 这道题里： $$\sum _{i=0}^{\infty }{C}_{nk}^{ik+r}=\sum _{i=0}^{\infty }(1+z{)}^{nk}[z^{ik+r}]$$ 右边是个卷积 然后有一个循环卷积的高级东西

只是下标模了$T$

其实不需要什么高级的方法 因为这里$k$很小，直接暴力乘就行

1.5

还有更多的高级方法

矩阵快速幂 DP来推柿子 等等

1.6 Code

代码第27~31行 $k=1$就是二项式定理，所有系数和为$2^k$ $k\ne 1$是二项式展开，就是杨辉三角

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } typedef long long ll; typedef vector<ll> poly; int n,p,k,r; poly operator * (const poly &a,const poly &b){ poly c(k); for(int i=0;i<a.size();++i) for(int j=0;j<b.size();++j) (c[(i+j)%k]+=a[i]*b[j])%=p; return c; } int main(){ n=in,p=in,k=in,r=in; poly a(k),ans(k); if(k==1){ a[0]=2%p; }else{ a[0]=a[1]=1; } ans[0]=1; ll e=1ll*n*k; while(e){ if(e&1) ans=ans*a; a=a*a; e>>=1; } cout<<ans[r]; return 0; }