[SDOI2016]储能表

时间：2025-03-12 23:37:01

Description

有一个 n 行 m 列的表格，行从 0 到 n−1 编号，列从 0 到 m−1 编号。每个格子都储存着能量。最初，第 i 行第 j 列的格子储存着 (i xor j) 点能量。所以，整个表格储存的总能量是，

[SDOI2016]储能表
随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都会减少 1。显然，一个格子的能量减少到 0 之后就不会再减少了。
也就是说，k 个时间单位后，整个表格储存的总能量是，
[SDOI2016]储能表
给出一个表格，求 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]$

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long lol;

 lol f[][][][],g[][][][],n,m,Mod,k,pw[],t1,t2,S,t3;

 void dfs(lol x,int a,int b,int c)

 {lol i,j;

   if (f[x][a][b][c]!=-||g[x][a][b][c]!=-) return;

   g[x][a][b][c]=f[x][a][b][c]=;

   if (x==)

     {

       f[][a][b][c]=;

       g[][a][b][c]=;

       return;

     }

   for (i=;i<=;i++)

     {

       int xx=(n>>x-)&;

       int yy=(m>>x-)&;

       int zz=(k>>x-)&;

       if (a&&i>xx) continue;

       for (j=;j<=;j++)

     {

       if (b&&j>yy) continue;

       lol p=i^j;

       if (c&&p<zz) continue;

       int aa=a&(xx==i);

       int bb=b&(yy==j);

       int cc=c&(zz==p);

       dfs(x-,aa,bb,cc);

       g[x][a][b][c]=(g[x][a][b][c]+g[x-][aa][bb][cc])%Mod;

       f[x][a][b][c]=((f[x][a][b][c]+g[x-][aa][bb][cc]*p*(pw[x-]%Mod)%Mod)%Mod+f[x-][aa][bb][cc])%Mod;

     }

     }

 }

 lol solve()

 {

   memset(f,-,sizeof(f));

   memset(g,-,sizeof(g));

   t1=;S=n;

   if (n==&&m==) return ;

   while (S)

     {

       S>>=;

       t1++;

     }

   t2=;S=m;

   while (S)

     {

       S>>=;

       t2++;

     }

   t3=;S=k;

   while (S)

     {

       S>>=;

       t3++;

     }

   t1=max(t1,max(t2,t3));

   dfs(t1,,,);

   return f[t1][][][]-(k%Mod)*g[t1][][][]%Mod;

 }

 int main()

 {int T,i;

   cin>>T;

   pw[]=;

   for (i=;i<=;i++)

     pw[i]=pw[i-]*;

   while (T--)

     {

       cin>>n>>m>>k>>Mod;

       n--;m--;

       printf("%lld\n",(solve()+Mod)%Mod);

     }

 }

相关文章