牛客練習(xí)賽52

C烹飪

鏈接：https://ac.nowcoder.com/acm/contest/1084/C來源：牛客網(wǎng)

時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld

題目描述

“你已經(jīng)是一個(gè)成熟的孩子了，要學(xué)會自己烹飪了！”

小 Y 上山拜師學(xué)藝，經(jīng)過 年之長的廚藝練習(xí)，已成為當(dāng)世名廚，今天他接受邀請，在眾人面前展示自己高超的廚藝。

人們給小 Y 提供了 種食物，每種食物無限量供應(yīng)，每種食物都有一個(gè)美味值，記為 aia_iai?。

小 Y 為了展示他的廚藝，他需要挑選出食材，使自己可以烹飪出任意正整數(shù)美味值的菜肴，初始時(shí)菜肴的美味值為 ，每次加入一種食材，他可以選擇讓菜肴的美味值上升 aia_iai?，也可以選擇讓菜肴的美味值下降 aia_iai?（或許最后會弄出來黑暗料理？）。

作為當(dāng)世名廚，小 Y 自然知道該怎么挑選食材最佳。可是他并不知道有多少種最佳的挑選食材方案，于是他找到了你來幫忙。

我們使用無序數(shù)列(b1,b2,…,bm)(b_1,b_2,\ldots,b_m)(b1,b2,…,bm)來表示從原來的n種食材中挑選出了m種食材，第i種食材編號為bib_ibi的方案。同時(shí)你需要注意，和為同一種方案且當(dāng)i=?ji \not =ji=j時(shí)，bi=?bjb_i \not = b_jbi=bj。

最佳的挑選食材方案指，挑選出 種食材（1≤m≤n1\leq m\leq n1≤m≤n），讓他們能夠組合出任意正整數(shù)美味值的菜肴。

例如，當(dāng)n=2,a1=1,a2=2n=2,a_1=1,a_2=2n=2,a1=1,a2=2時(shí)，(1),(1,2)\left( 1\right),\left( 1,2\right)(1),(1,2)都是最佳的挑選食材方案。

答案對 取模。

輸入描述:

第一行一個(gè)正整數(shù) 。第二行 個(gè)正整數(shù) ai(1≤ai≤2 000)a_i(1\le a_i\le2\ 000)ai(1≤ai≤2 000)。

輸出描述:

輸出一個(gè)數(shù)表示最佳的挑選食材方案的數(shù)量對 取模。

示例1

輸入

復(fù)制

5 1 2 3 4 5

輸出

復(fù)制

26

示例2

輸入

復(fù)制

1 2

輸出

復(fù)制

0

思路：

有一個(gè)結(jié)論十分顯然，即能組合出[1,n][1,n][1,n]的任意正整數(shù)的充要條件時(shí)能組成1

根據(jù)裴蜀定理ax+by=gcd(a,b)，顯然這擴(kuò)展到n元組也成立

于是問題轉(zhuǎn)換成為：選出一個(gè)集合，集合中每個(gè)數(shù)可以選多次，并且這個(gè)集合gcd為1,

設(shè)f[i]表示組成集合gcd為i的方案數(shù)

顯然f[gcd(x,j)]=∑f[j]

注意方案多算了一倍，除以二就行了

于是O(nmlogm)解決了

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl #define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define du2(a,b) scanf("%d %d",&(a),&(b)) #define du1(a) scanf("%d",&(a)); using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;} void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}} void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}inline void getInt(int* p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ const ll mod = 998244353ll;ll f[maxn]; ll a[maxn];int n;int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;cin >> n;repd(i, 1, n){cin >> a[i];}repd(i, 1, n){f[a[i]]++;repd(j, 1, 2000){ll x = gcd(a[i], j);f[x] += f[j];f[x] %= mod;}}cout << f[1]*powmod(2, mod - 2ll, mod) % mod << endl;return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/11633119.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛52 | C | [烹饪] （DP，裴蜀定理，gcd）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。