国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

【GDKOI2017模擬1.21】Equation

2019-11-11 03:32:22
字體:
來源:轉載
供稿:網友

Description

聽著自己美妙的曲子,小Z進入了夢鄉。在夢中,小Z仿佛又回到了自己縱橫考場的年代。在夢中,小Z參加了一場考試,這場考試一共有n道題,每道題的最終得分都是一個大于等于0的整數。然而醒來后,小Z忘記了自己每道題的得分。他只記得自己計算過m次一些題目的分數和,每道題都被計算過,并且只被計算過一次。除此之外他還記得其中t道題的滿分分別是多少(一道題的得分不會超過滿分)。現在小Z想知道他這場考試有多少種得分情況(至少有一道題的得分不同就算不同的情況),因為這個答案可能很大,你只需要輸出答案對1,000,000,007取模后的結果即可。

Input

第一行兩個整數n,m表示題目個數與求和次數。 接下來m行,每行以一個整數k開頭,表示小Z這次對k道題進行了求和。然后k個整數a1~ak,表示這次求和的都是哪些題。最后一個整數c表示求和后的結果。 一行一個整數t,含義見題目描述。 t行,每行兩個整數r,L,表示第r道題的滿分是L。

Output

一行一個整數表示答案模1,000,000,007的結果。

Sample Input

5 2 2 1 2 5 3 3 4 5 7 1 3 4

Sample Output

180

Data Constraint

對于30%的數據:n,c≤8。 對于另外40%的數據:t=0。 對于100%的數據:1≤n,m≤1,000,000,0≤c,L≤1,000,000,0≤t≤20。

題解

沒有限制時,顯然可以直接組合數 當有限制時,發現限制數量很少,所以考慮使用容斥來解決這個問題 對于一個子要求a[i]<r(不滿足),可以把它看成滿足a[i]>=r,那么可以把a[i]分解為x+r+1的形式(x>0)這樣就可以直接用沒有限制的方法求出總的方案數

貼代碼

const md=1000000007;var a,go:array[0..1000005]of longint; cc,tt:array[0..1000005]of longint; f:array[0..1100005]of int64; yu:array[0..2000005]of int64; p:array[0..25,1..2]of longint; i,j,k,l,m,n,x,y,z,t,o,c:longint; zong,ans,tot,tmp:int64;function quickmi(x,y:int64):int64;var a,b:int64;begin a:=x; b:=1; while y>0 do begin if y mod 2=1 then b:=(b*a) mod md; a:=(a*a) mod md; y:=y div 2; end; exit(b);end;begin //assign(input,'t3.in'); reset(input); assign(input,'equation.in'); reset(input); assign(output,'equation.out'); rewrite(output); readln(n,m); yu[0]:=1; yu[1]:=1; for i:=2 to 2000000 do yu[i]:=(yu[i-1]*i) mod md; z:=0; zong:=1; for i:=1 to m do begin read(k); cc[i]:=k; for j:=1 to k do begin read(a[z]); go[a[z]]:=i; end; readln(tt[i]); tmp:=(yu[k-1]*yu[tt[i]]) mod md; tmp:=quickmi(tmp,md-2); tmp:=(tmp*yu[k+tt[i]-1]) mod md; zong:=(zong*tmp) mod md; end; readln(t); for i:=1 to t do readln(p[i,1],p[i,2]); f[0]:=zong; ans:=zong; for i:=1 to 1<<t-1 do begin z:=1; for j:=1 to t do if i and (1<<(j-1))<>0 then z:=z*(-1); for j:=1 to t do if i and (1<<(j-1))<>0 then begin c:=tt[go[p[j,1]]]; l:=i xor (1<<(j-1)); for k:=1 to t do if (go[p[k,1]]=go[p[j,1]]) and (j<>k) then begin c:=(c-p[k,2]-1) mod md; if c<0 then break; end; if c<0 then continue; k:=cc[go[p[j,1]]]; tmp:=(yu[k-1]*yu[c]) mod md; tmp:=quickmi(tmp,md-2); tmp:=(tmp*yu[k+c-1]) mod md; tmp:=quickmi(tmp,md-2); c:=(c-p[j,2]-1) mod md; if c<0 then continue; f[i]:=(f[l]*tmp) mod md; tmp:=(yu[k-1]*yu[c]) mod md; tmp:=quickmi(tmp,md-2); tmp:=(tmp*yu[k+c-1]) mod md; f[i]:=(f[i]*tmp) mod md; ans:=(ans+z*f[i]+md) mod md; break; end; end; writeln(ans); close(input); close(output);end.
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 绥宁县| 托克逊县| 永昌县| 沙河市| 乌苏市| 潜山县| 全南县| 金塔县| 土默特右旗| 墨江| 南陵县| 和硕县| 和田市| 濮阳县| 山丹县| 夏河县| 孟连| 怀化市| 宜黄县| 东阳市| 宁晋县| 红桥区| 福安市| 新民市| 台中县| 罗田县| 福贡县| 根河市| 湘阴县| 康马县| 门源| 长阳| 徐汇区| 铅山县| 杭锦后旗| 岢岚县| 威海市| 金昌市| 仪征市| 隆安县| 和政县|