网站用品推广网页,公司网站建设 意义,搜索引擎收录提交,联盟网站Description 有一个 n 行 m 列的表格#xff0c;行从 0 到 n−1 编号#xff0c;列从 0 到 m−1 编号。每个格子都储存着能量。最初#xff0c;第 i 行第 j 列的格子储存着 (i xor j) 点能量。所以#xff0c;整个表格储存的总能量是#xff0c; 随着时间的推移#xff0…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 T5000n≤10^18m≤10^18k≤10^18p≤10^9 令$f[i][a][b][c]和g[i][a][b][c]$表示第i位表示x后i-1位是否等于ny后i-1位是否等于mx^y后i-1位是否等于k的异或和以及方案数 如果a1且第i位大于n的第i位那么超过上界舍去 b同理 c比较特殊如果c1如果第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 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 #includecmath6 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 (x0)
14 {
15 f[0][a][b][c]0;
16 g[0][a][b][c]1;
17 return;
18 }
19 for (i0;i1;i)
20 {
21 int xx(nx-1)1;
22 int yy(mx-1)1;
23 int zz(kx-1)1;
24 if (aixx) continue;
25 for (j0;j1;j)
26 {
27 if (bjyy) continue;
28 lol pi^j;
29 if (cpzz) continue;
30 int aaa(xxi);
31 int bbb(yyj);
32 int ccc(zzp);
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)%Modf[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 t10;Sn;
44 if (n0m0) return 0;
45 while (S)
46 {
47 S1;
48 t1;
49 }
50 t20;Sm;
51 while (S)
52 {
53 S1;
54 t2;
55 }
56 t30;Sk;
57 while (S)
58 {
59 S1;
60 t3;
61 }
62 t1max(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 cinT;
69 pw[0]1;
70 for (i1;i60;i)
71 pw[i]pw[i-1]*2;
72 while (T--)
73 {
74 cinnmkMod;
75 n--;m--;
76 printf(%lld\n,(solve()Mod)%Mod);
77 }
78 } 转载于:https://www.cnblogs.com/Y-E-T-I/p/8577883.html
