? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?#22. 【UR #1】外星人

2044年，Picks建成了人類第一臺基于量子理論的銀河系信息傳遞機。

Picks游遍了宇宙，雇用了?nn?個外星人來幫他作為信息傳遞機的中轉站。我們將外星人依次編號為?11?到?nn，其中?ii?號外星人有?aiai?根手指。

外星人都是很低級的，于是Picks花費了很大的精力，才教會他們學會扳手指數數。

Picks現在準備傳遞?xx?個脈沖信號給VFleaKing，于是他把信號發給11號外星人，然后11號外星人把信號發送給22號外星人，22號外星人把信號發送給33號外星人，依次類推，最后nn號外星人把信號發給VFleaKing。

但是事情沒有Picks想象的那么順利，由于外星人手指個數有限，所以如果?ii?號外星人收到了?tt?個脈沖信號，他會錯誤的以為發送過來的是?tmodaitmodai?個脈沖信號，導致只發送了?tmodaitmodai?個脈沖信號出去。

Picks希望他發送出去的脈沖信號數量?xx?與VFleaKing收到的脈沖信號數量?yy?的差的絕對值盡量小。于是他決定通過重新排列這些外星人的順序來達到這一目的。請你求出與?xx?之差最小的?yy。除此之外，請求出有多少種排列外星人的方式能達到最優解，你只需要輸出方案數對?998244353998244353（7×17×223+17×17×223+1，一個質數）取模后的結果。

輸入格式

第一行兩個正整數n,xn,x。

接下來一行有?nn?個正整數?aiai，表示?ii?號外星人的手指數。

輸出格式

第一行一個整數表示最優情況下VFleaKing收到的脈沖數量。

第二行一個整數表示達到最優情況的方案數。

樣例一

input

2 15 7 10

output

5 1

explanation

共兩種可行方案：

15mod7=115mod7=1，1mod10=11mod10=1

15mod10=515mod10=5，5mod7=55mod7=5

顯然第二種方案更優。

樣例二

input

7 33 2 4 6 8 16 16 32

output

1 5040

explanation

每個排列方案都是最優解。

樣例三

見樣例數據下載

限制與約定

對于每個測試點，答對第一問可獲得 40% 的分數，答對第二問可獲得 60% 的分數。

請注意你必須輸出兩個整數否則會判0分。假如你只做了第一問，那么你應該輸出你第一問的答案，然后再隨便輸出一個第二問的答案。

測試點編號nn的規模xx?和?aiai的規模

1	n≤10n≤10	x,ai≤20x,ai≤20
2	n≤50n≤50	x,ai≤100x,ai≤100
3
4	n≤100n≤100	x,ai≤500x,ai≤500
5
6
7	n≤1000n≤1000	x,ai≤5000x,ai≤5000
8
9
10

時間限制：1s1s

空間限制：256MB

?

詳解

f[i][j]代表 處理a[i] 能否得到 j?

g[i][j] 記錄方案數?

考慮取模運算。一個非?；A的性質是：當?x≥ai?時，x?mod?ai<ai。當?x?<?ai?時，x?mod?ai=x?。

那么對于每個ai，要么就把它放在當前位置，現在生效，要么把它放在后面的n?i個位置，使它永不生效，因為如果你先模了一個小于ai的數，再模ai結果是不會變的。

?

1 #include <cstdio> 2 #include <cctype> 3 #include <algorithm> 4 5 typedef long long LL; 6 7 const int mod=998244353; 8 const int MAXN=1010; 9 const int MAXM=5010; 10 11 int n,s; 12 13 int a[MAXM]; 14 15 bool f[MAXN][MAXM]; 16 17 LL g[MAXN][MAXM]; 18 19 inline bool cmp(int a,int b) {return a>b;} 20 21 inline void read(int&x) { 22 int f=1;register char c=getchar(); 23 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 24 for(;isdigit(c);x=x*10+c-48,c=getchar()); 25 x=x*f; 26 } 27 28 inline void running() { 29 f[0][s]=1;g[0][s]=1; 30 for(int i=1;i<=n;++i) { 31 for(int j=s;j>=0;--j) { 32 f[i][j%a[i]]|=f[i-1][j]; 33 g[i][j%a[i]]=(g[i][j%a[i]]+g[i-1][j])%mod; 34 } 35 if(i!=n) { 36 for(int j=s;j>=0;--j) { 37 f[i][j]|=f[i-1][j]; 38 g[i][j]=(g[i][j]+g[i-1][j]*(n-i))%mod; 39 } 40 } 41 } 42 for(int i=s;i>=0;--i) 43 if(f[n][i]) { 44 printf("%d\n",i); 45 printf("%lld\n",g[n][i]); 46 break; 47 } 48 return; 49 } 50 51 int hh() { 52 read(n);read(s); 53 for(int i=1;i<=n;++i) read(a[i]); 54 std::sort(a+1,a+1+n,cmp); 55 running(); 56 return 0; 57 } 58 59 int sb=hh(); 60 int main(int argc,char**argv) {;} 代碼

?

轉載于:https://www.cnblogs.com/whistle13326/p/7507351.html

總結

以上是生活随笔為你收集整理的#22. 【UR #1】外星人的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。