解析
再次被“组合数问题”吊打qwq
和上一次不一样的是，这次更加被恶心到了。
一方面受上一个组合数问题影响，另外出题人也十分阴间，一开始还给了个组合数的公式，更加使我坚定的认为这是一道数学推柿子题。
然后就开始各种打表+玩泥巴，没有任何卵用。
不过这题啥都不会暴力+几个部分分就有80，非常的棒，这考场谁还想正解啊。
让我们回归组合数的最基本的意义：
(
n
m
)
\binom n m
(mn?) 表示从
n
n
n 个物品中选
m
m
m 个的方案数。
那么题目要求的其实就是：从
n
n
n 个物品中选出物品个数模
k
k
k 结果为
r
r
r 的方案数。
能想到这里这题基本就做完了。
这个东西似乎 openjudge 上还有一个题，当时是直接
O
(
n
k
?
k
)
O(nk*k)
O(nk?k) 的复杂度来暴力做。
而这个背包的合并显然是具有结合律的，所以可以直接像快速幂一样倍增的求出答案。
总复杂度
O
(
k
2
log
?
(
n
k
)
)
O(k^2\log(nk))
O(k2log(nk))。
（如果那个卷积用 FFT 的话也许可以做到
O
(
k
log
?
k
log
?
(
n
k
)
)
O(k\log k\log (nk))
O(klogklog(nk))？）
但巨大常数感觉可能甚至跑不过暴力卷积。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
using namespace std;
const int N=1e6+100;
const int M=2e5+100;
const int inf=1e9;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,k,r;
int mod;
struct node{
ll w[55];
node(){memset(w,0,sizeof(w));}
};
node operator * (const node &a,const node &b){
node res;
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
(res.w[(i+j)%k]+=a.w[i]*b.w[j])%=mod;
}
}
return res;
}
node ksm(node x,ll k){
node res;
res.w[0]=1;
while(k){
if(k&1) res=res*x;
x=x*x;
k>>=1;
}
return res;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();mod=read();k=read();r=read();
node x;
x.w[1%k]++;x.w[0]++;
node ans=ksm(x,1ll*n*k);
printf("%lld\n",ans.w[r]);
return 0;
}
|