做个网站多少钱一年,青岛网站建设哪家更好,canvas可画网页版,shopex网站首页空白文章目录题目描述解析代码题目描述 解析
第一感觉#xff1a;啥都没感觉出来。。。 直接拿动态规划高精做的 但是只能拿40 重新分析一下这道题#xff1a; g#xff08;x#xff09;首先可以拿快速幂很容易的求出来 问题就转化为了**把g(x)个东西分成k份的方案数 其实答案…
文章目录题目描述解析代码题目描述 解析
第一感觉啥都没感觉出来。。。 直接拿动态规划高精做的 但是只能拿40 重新分析一下这道题 gx首先可以拿快速幂很容易的求出来 问题就转化为了**把g(x)个东西分成k份的方案数 其实答案就是C(k-1,n-1) 为什么是这样 介绍一种新的方法隔板法 本题画一下就是 那么不难发现一共有n-1个空隙插入k-1个板题目已经说明1,1,2和2,1,1是不一样的方案 所以就可以得出组合数的结论了
代码
#includeiostream
#includecstdio
#includecstringusing namespace std;typedef long long ll;const int maxn 1000;
const int BIT 4;
const int MOD 1e4;struct bign {int num[maxn], len;bool flag;friend bign abs(const bign x) {bign k x;k.flag true;return k;}friend void remove(bign x) {while (x.num[x.len] 0 x.len 1)x.len--;}bign() {memset(num, 0, sizeof(num));flag true;len 1;}bign(const int x) {*this bign();if (x) {int k x;if (k 0)k -k, flag false;len 0;while (k) {num[len] k % MOD;k / MOD;}}}bign(const ll x) {*this bign();if (x) {ll k x;if (k 0)k -k, flag false;len 0;while (k) {num[len] k % MOD;k / MOD;}}}bign(const char *x) {int l strlen(x), s, t 0, p 0, k 1;*this bign();if (x[0] -)flag false, s 1;len 0;for (int i l - 1; i s; i--) {p k * (x[i] - 0);k * 10;t;if (t 4) {t 0;num[len] p;p 0;k 1;}}if (p)num[len] p;}bign(const string x) {int l x.length(), s 0, t 0, p 0, k 1;*this bign();if (x[0] -)flag false, s 1;len 0;for (int i l - 1; i s; i--) {p k * (x[i] - 0);k * 10;t;if (t BIT) {t 0;num[len] p;p 0;k 1;}}if (p)num[len] p;}bign operator(const int x) {return *this bign(x);}bign operator(const ll x) {return *this bign(x);}bign operator(const char *x) {return *this bign(x);}bign operator(const string x) {return *this bign(x);}bool operator(const bign x) const {if (flag ! x.flag)return flag x.flag;if (len ! x.len)return (len x.len) ^ flag ^ 1;for (int i len; i 1; i--) {if (num[i] ! x.num[i]) {return (num[i] x.num[i]) ^ flag ^ 1;}}return false;}bool operator(const int x) const {return *this bign(x);}bool operator(const ll x) const {return *this bign(x);}bool operator(const bign x) const {return x *this;}bool operator(const int x) const {return *this bign(x);}bool operator(const ll x) const {return *this bign(x);}bool operator(const bign x) const {return !(*this x);}bool operator(const int x) const {return *this bign(x);}bool operator(const ll x) const {return *this bign(x);}bool operator(const bign x) const {return !(*this x);}bool operator(const int x) const {return *this bign(x);}bool operator(const ll x) const {return *this bign(x);}bool operator(const bign x) const {if (flag ! x.flag)return false;if (len ! x.len)return false;for (int i len; i 1; i--) {if (num[i] ! x.num[i]) {return false;}}return true;}bool operator(const int x) const {return *this bign(x);}bool operator(const ll x) const {return *this bign(x);}bool operator!(const bign x) const {return !(*this x);}bool operator!(const int x) const {return *this ! bign(x);}bool operator!(const ll x) const {return *this ! bign(x);}friend istream operator(istream in, bign x) {string s;in s;x s;return in;}friend ostream operator(ostream out, const bign x) {if (x.flag false x ! 0)out -;out x.num[x.len];for (int i x.len - 1; i 1; i--)printf(%0*d, BIT, x.num[i]);return out;}bign operator-() const {bign k *this;k.flag ^ 1;return k;}bign operator(const bign x) const {if (flag x.flag) {bign k bign();k.len 0;for (int i 1, g 0; g || i len || i x.len; i) {int p num[i] x.num[i] g;k.num[k.len] p % MOD;g p / MOD;}return k;}if (flag !x.flag)return *this - (-x);if (!flag x.flag)return x - (-*this);return -((-x) (-*this));}bign operator(const int x) const {return *this bign(x);}bign operator(const bign x) {return *this *this x;}bign operator(const int x) {return *this bign(x);}bign operator(const ll x) {return *this bign(x);}bign operator() {return *this 1;}bign operator(int) {bign k *this;*this 1;return k;}bign operator-(const bign x) const {if (flag x.flag *this x) {bign k bign();k.len 0;for (int i 1, g 0; g || i len; i) {int p num[i] - x.num[i] g;if (p 0)g -1;else g 0;k.num[k.len] (p % MOD MOD) % MOD;}remove(k);return k;}if (flag x.flag)return -(x - *this);if (flag !x.flag)return *this (-x);if (!flag x.flag)return -((-*this) x);return (-x) - (-*this);}bign operator-(const bign x) {*this *this - x;return *this;}bign operator-(const int x) {return *this - bign(x);}bign operator-(const ll x) {return *this - bign(x);}bign operator--() {return *this - 1;}bign operator--(int) {bign k *this;*this - 1;return k;}bign operator*(const bign x) const {bign k;k.flag (flag x.flag);k.len len x.len 1;for (int i 1; i len; i) {for (int j 1; j x.len; j) {k.num[i j - 1] num[i] * x.num[j];k.num[i j] k.num[i j - 1] / MOD;k.num[i j - 1] % MOD;}}remove(k);return k;}bign operator*(const int x) const {bign k bign();k.len 0;long long t[maxn];memset(t, 0, sizeof(t));for (int i 1; i len; i)t[i] num[i] * x;for (int i 1, g 0; i len || g; i) {k.num[k.len] (g t[i]) % MOD;g (g t[i]) / MOD;}return k;}bign operator*(const ll x) const {bign k bign();k.len 0;long long t[maxn];memset(t, 0, sizeof(t));for (int i 1; i len; i)t[i] num[i] * x;for (int i 1, g 0; i len || g; i) {k.num[k.len] (g t[i]) % MOD;g (g t[i]) / MOD;}return k;}bign operator*(const bign x) {return *this *this * x;}bign operator*(const int x) {return *this *this * x;}bign operator*(const ll x) {return *this *this * x;}bign operator/(const bign x) const {if (x 0)return bign();bign k bign(), a bign();k.flag (flag x.flag);k.len len;for (int i len; i 1; i--) {a a * MOD num[i];while (a abs(x)) {a - abs(x);k.num[i];}}
// if ((flag ! x.flag) a ! 0)
// k--; //取模remove(k);return k;}bign operator/(const int x) const {if (x 0)return bign();bign k bign();int a 0;k.flag (flag (x 0));k.len len;for (int i len; i 1; i--) {a a * MOD num[i];k.num[i] a / x;a % x;}
// if ((flag ! x.flag) a ! 0)
// k--; //取模remove(k);return k;}bign operator/(const ll x) const {if (x 0)return bign();bign k bign();int a 0;k.flag (flag (x 0));k.len len;for (int i len; i 1; i--) {a a * MOD num[i];k.num[i] a / x;a % x;}
// if ((flag ! x.flag) a ! 0)
// k--; //取模remove(k);return k;}bign operator/(const bign x) {return *this *this / x;}bign operator/(const int x) {return *this *this / x;}bign operator/(const ll x) {return *this *this / x;}bign operator%(const bign x) const {if (x 0)return bign();bign a bign();for (int i len; i 1; i--) {a a * MOD num[i];while (a abs(x))a - abs(x);}
// if (a 0)return a;
// if (flag x.flag)return a;
// if (flag !x.flag)return a x;
// if (!flag x.flag)return x - a;
// return -a;//取模if (flag)return a;return -a;}bign operator%(const int x) const {return *this % bign(x);}bign operator%(const ll x) const {return *this % bign(x);}bign operator%(const bign x) {return *this *this % x;}bign operator%(const int x) {return *this % bign(x);}bign operator%(const ll x) {return *this % bign(x);}friend bign pow(const bign x, const bign y) {bign ans 1, cnt x, w y;while (w 0) {if (w % 2 1)ans * cnt;cnt * cnt;w / 2;}return ans;}friend bign pow(const int x, const bign y) {bign ans 1, cnt x, w y;while (w 0) {if (w % 2 1)ans * cnt;cnt * cnt;w / 2;}return ans;}friend bign pow(const bign x, const int y) {bign ans 1, cnt x;int w y;while (w) {if (w 1)ans * cnt;cnt * cnt;w 1;}return ans;}friend bign powmod(const bign x, const bign y, const bign z) {bign ans 1, cnt x, w y;while (w 0) {if (w % 2 1)ans ans * cnt % z;cnt cnt * cnt % z;w / 2;}return ans;}friend bign powmod(const int x, const bign y, const bign z) {bign ans 1, cnt x, w y;while (w 0) {if (w % 2 1)ans ans * cnt % z;cnt cnt * cnt % z;w / 2;}return ans;}friend bign powmod(const bign x, const int y, const bign z) {bign ans 1, cnt x;int w y;while (w) {if (w 1)ans ans * cnt % z;cnt cnt * cnt % z;w 1;}return ans;}friend bign powmod(const bign x, const bign y, const int z) {bign ans 1, cnt x, w y;while (w 0) {if (w % 2 1)ans ans * cnt % z;cnt cnt * cnt % z;w / 2;}return ans;}friend bign powmod(const int x, const bign y, const int z) {bign ans 1, cnt x, w y;while (w 0) {if (w % 2 1)ans ans * cnt % z;cnt cnt * cnt % z;w / 2;}return ans;}friend bign powmod(const bign x, const int y, const int z) {bign ans 1, cnt x;int w y;while (w) {if (w 1)ans ans * cnt % z;cnt cnt * cnt % z;w 1;}return ans;}friend bign max(const bign x, const bign y) {return x y ? x : y;}friend bign min(const bign x, const bign y) {return x y ? x : y;}
};#define ll bign
const int N4e5100;
const int mod1000;
int t,k,x;
int n;
long long ksm(int x,int p){long long tot1,resx;while(p){if(p1) tottot*res%mod;resres*res%mod;p1;}return tot%mod;
}
int main(){scanf(%d%d,k,x);nksm(x,x);//n-k;ll ans1;for(int i2;in-1;i) ans*i;for(int i2;ik-1;i) ans/i;for(int i2;in-k;i) ans/i;coutans;
}
/*
WW.WBBBBB
*/
