Description

有一個 n 行 m 列的表格，行從 0 到 n?1 編號，列從 0 到 m?1 編號。每個格子都儲存著能量。最初，第 i 行第 j 列的格子儲存著 (i xor j) 點能量。所以，整個表格儲存的總能量是，

隨著時間的推移，格子中的能量會漸漸減少。一個時間單位，每個格子中的能量都會減少 1。顯然，一個格子的能量減少到 0 之后就不會再減少了。 也就是說，k 個時間單位后，整個表格儲存的總能量是， 給出一個表格，求 k 個時間單位后它儲存的總能量。 由于總能量可能較大，輸出時對 p 取模。

Input

第一行一個整數 T，表示數據組數。接下來 T 行，每行四個整數 n、m、k、p。

Output

?共 T 行，每行一個數，表示總能量對 p 取模后的結果

Sample Input

3
2 2 0 100
3 3 0 100
3 3 1 100

Sample Output

2
12
6

HINT

?T=5000，n≤10^18，m≤10^18，k≤10^18，p≤10^9

令$f[i][a][b][c]和g[i][a][b][c]$表示第i位，表示x后i-1位是否等于n，y后i-1位是否等于m，x^y后i-1位是否等于k的異或和以及方案數

如果a==1，且第i位大于n的第i位，那么超過上界，舍去

b同理

c比較特殊，如果c==1，如果第i為小于k的第i位，那么異或結果必定小于k，答案為0，舍去

$g[i][a][b][c]+=g[i-1][aa][bb][cc]$

$f[i][a][b][c]+=f[i-1][aa][bb][cc]+[第i位異或值為1]*2^{i}*g[i-1][aa][bb][cc]$

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef long long lol; 8 lol f[81][2][2][2],g[81][2][2][2],n,m,Mod,k,pw[61],t1,t2,S,t3; 9 void dfs(lol x,int a,int b,int c) 10 {lol i,j; 11 if (f[x][a][b][c]!=-1||g[x][a][b][c]!=-1) return; 12 g[x][a][b][c]=f[x][a][b][c]=0; 13 if (x==0) 14 { 15 f[0][a][b][c]=0; 16 g[0][a][b][c]=1; 17 return; 18 } 19 for (i=0;i<=1;i++) 20 { 21 int xx=(n>>x-1)&1; 22 int yy=(m>>x-1)&1; 23 int zz=(k>>x-1)&1; 24 if (a&&i>xx) continue; 25 for (j=0;j<=1;j++) 26 { 27 if (b&&j>yy) continue; 28 lol p=i^j; 29 if (c&&p<zz) continue; 30 int aa=a&(xx==i); 31 int bb=b&(yy==j); 32 int cc=c&(zz==p); 33 dfs(x-1,aa,bb,cc); 34 g[x][a][b][c]=(g[x][a][b][c]+g[x-1][aa][bb][cc])%Mod; 35 f[x][a][b][c]=((f[x][a][b][c]+g[x-1][aa][bb][cc]*p*(pw[x-1]%Mod)%Mod)%Mod+f[x-1][aa][bb][cc])%Mod; 36 } 37 } 38 } 39 lol solve() 40 { 41 memset(f,-1,sizeof(f)); 42 memset(g,-1,sizeof(g)); 43 t1=0;S=n; 44 if (n==0&&m==0) return 0; 45 while (S) 46 { 47 S>>=1; 48 t1++; 49 } 50 t2=0;S=m; 51 while (S) 52 { 53 S>>=1; 54 t2++; 55 } 56 t3=0;S=k; 57 while (S) 58 { 59 S>>=1; 60 t3++; 61 } 62 t1=max(t1,max(t2,t3)); 63 dfs(t1,1,1,1); 64 return f[t1][1][1][1]-(k%Mod)*g[t1][1][1][1]%Mod; 65 } 66 int main() 67 {int T,i; 68 cin>>T; 69 pw[0]=1; 70 for (i=1;i<=60;i++) 71 pw[i]=pw[i-1]*2; 72 while (T--) 73 { 74 cin>>n>>m>>k>>Mod; 75 n--;m--; 76 printf("%lld\n",(solve()+Mod)%Mod); 77 } 78 }

?

轉載于:https://www.cnblogs.com/Y-E-T-I/p/8577883.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[SDOI2016]储能表的全部內容，希望文章能夠幫你解決所遇到的問題。

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