假設今天我想吃冰，而眼前共有$n$種冰品可以選擇但是我又有選擇障礙不知道該如何決定，請問若我今天決定吃其中恰好$k$種冰，有幾種不同的選擇?
由於輸入龐大，為了增加IO的效率，本題將壓縮輸入與輸出，方法如下:
每筆測資輸入6個數字: $q,m,s0,s1,s2,s3$，分別代表詢問數(int)、值域(int)、以及4個random seed(uint64_t)，之後請用以下程式碼來產生實際測資:
struct{ struct{ static uint64_t rotl(const uint64_t x, int k) { return (x << k) | (x >> (64 - k)); } uint64_t s[4]; uint64_t operator()(){ const uint64_t result=rotl(s[0]+s[3],23)+s[0]; const uint64_t t=s[1]<<17; s[2]^=s[0]; s[3]^=s[1]; s[1]^=s[2]; s[0]^=s[3]; s[2]^=t; s[3] = rotl(s[3], 45); return result; } }rng; int m; void init(int _m,uint64_t s0,uint64_t s1,uint64_t s2,uint64_t s3){ m=_m; rng.s[0]=s0; rng.s[1]=s1; rng.s[2]=s2; rng.s[3]=s3; } pair<int,int> operator()(){ int n=rng()%m+1,k=rng()%(n+1); return make_pair(n,k); } }testcase;
一開始先呼叫 testcase.init(m,s0,s1,s2,s3) ，之後執行$q$每次呼叫 testcase() 即可得到一個pair分別為該筆詢問的$n,m$。
除此之外為了減少輸出，假設$q$筆詢問的答案依序是$ans_{1..q}$，那麼請輸出$\sum\limits_{i=1}^{q}ans_ix^i\mod 998244353$，其中$x=880301$。
完整使用方式範例如下(僅需實作出 C(n,k) 即可，當然或許你會需要做些預處理或額外變數自己加):
int main() { int q,m,base=1,res=0; uint64_t s0,s1,s2,s3; const int mod=998244353,x=880301; cin>>q>>m>>s0>>s1>>s2>>s3; testcase.init(m,s0,s1,s2,s3); while(q--){ pair<int,int> tmp=testcase(); int n=tmp.first,k=tmp.second; int ans=C(n,k); base=(long long)base*x%mod; res=(res+(long long)ans*base)%mod; } cout<<res<<"\n"; return 0; }
每筆測資輸入6個數字$q,m,s0,s1,s2,s3$，其中$q,m$是int型態而$s0,s1,s2,s3$是uint64_t型態。
測資點0的$q=100,m=500$。
測資點1的$q=500,m=100000$。
測資點2的$q=10000000,m=100$
測資點3的$q=10000000,m=5000$
測資點4的$q=5000000,m=30000000$
測資點5的$q=30000000,m=5000000$
測資點6~9的$q=30000000,m=30000000$
每筆測資輸出一個非負整數如題敘所述。
10 10 87 8787 878787 87878787 8787878787 878787878787
571541984
範例測資的十個詢問分別是:
$C(10,7)=120$
$C(3,2)=3$
$C(7,4)=35$
$C(7,1)=7$
$C(9,1)=9$
$C(7,2)=21$
$C(5,3)=10$
$C(1,0)=1$
$C(5,4)=5$
$C(6,4)=15$
$(n+1)!=(n+1)\times n!\Rightarrow \frac{1}{n!}=...$
本題記憶體用量可能不小，請好好計算使用的記憶體大小並且請盡量節省記憶體用量
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||