游戏网站建站,网站开发 群,HTMT超链接网站怎么做,挖矿网站怎么免费建设loj#2143. 「SHOI2017」组合数问题
题目描述
Solution
考虑转化一下我们要求的东西。 ∑i0n(nkikr)∑i0n(nki)[i≡r(modk)]\sum_{i0}^{n}\binom{nk}{ikr}\sum_{i0}^{n}\binom{nk}{i}[i \equiv r \;\;(mod\;\;k)]∑i0n(ikrnk)∑i0n(ink)[i≡r(modk)]
这个式子是什么…loj#2143. 「SHOI2017」组合数问题
题目描述
Solution
考虑转化一下我们要求的东西。 ∑i0n(nkikr)∑i0n(nki)[i≡r(modk)]\sum_{i0}^{n}\binom{nk}{ikr}\sum_{i0}^{n}\binom{nk}{i}[i \equiv r \;\;(mod\;\;k)]∑i0n(ikrnk)∑i0n(ink)[i≡r(modk)]
这个式子是什么呢 这不就是nknknk个物品中选择iii个物品且i≡r(modk)i \equiv r\;\;(mod\;\;k)i≡r(modk)的方案数吗
考虑dpdpdp设fi,jf_{i,j}fi,j表示前iii个物品选择jjj个的方案数jjj是在模kkk意义下的有 fi,jfi−1,jfi−1,(j−1k)%kf_{i,j}f_{i-1,j}f_{i-1,(j-1k)\%k} fi,jfi−1,jfi−1,(j−1k)%k 这里的kkk只有505050所以可以直接倍增或者矩阵快速幂优化。 我用了矩阵快速幂直接贴板子就行啦 时间复杂度O(k3lg(nk))O(k^3\;lg\;(nk))O(k3lg(nk))
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int MAXN100005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int n,mods,k,r;
inline int upd(int x,int y) { return xymods?xy-mods:xy; }
struct Matrix
{int n,A[55][55];void init() { for (int i0;in;i) A[i][i]1; }Matrix(int _n0) { n_n; memset(A,0,sizeof A); }Matrix operator * (const Matrix y) {Matrix Ans(n);for (int k0;kn;k)for (int i0;in;i)for (int j0;jn;j) Ans.A[i][j]upd(Ans.A[i][j],1ll*A[i][k]*y.A[k][j]%mods);return Ans;}Matrix operator ^ (ll y){Matrix ret(n),x*this;ret.init();for (;y;y1){if (y1) retret*x;xx*x;}return ret;}void print(){for (int i0;in;i){for (int j0;jn;j) coutA[i][j] ;coutendl;}}
};
int main()
{nread(),modsread(),kread(),rread();Matrix f(k);for (int i0;ik;i) f.A[i][i],f.A[i][(ik-1)%k];ff^(1ll*n*k);
// f.print();printf(%d\n,f.A[0][r]);return 0;
}
