C++(g++ 7.5.0) 解法, 执行用时: 821ms, 内存消耗: 192540K, 提交时间: 2022-08-18 13:42:14

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
inline unsigned int in()
{
	char ch=getchar();
	unsigned int f=1,x=0;
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return f*x;
}

//need changing
const int inf=(1<<30);
const int mod=1e9+7;
const int N=7010;
unsigned int n,a[N][N],p;

unsigned int x, y, z, w;
unsigned int xorshift()
{     
	unsigned int t = x;
	t ^= t << 11;
	t ^= t >> 8; 
	x = y; y = z; z = w;     
	w ^= w >> 19;     
	w ^= t;     
	return w & ((1 << 24) - 1); 
} 

LL ww[N];

LL qmi(LL a,LL b)
{
	LL ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}

int main()
{
	n = in();
	unsigned int Aa = in(),Ab = in(),Ac = in(),Ad = in(),Ba = in(),Bb = in(),Bc = in(),Bd = in();
	p = in();
	
	x = Aa; y = Ab; z = Ac; w = Ad;     
	for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)  
            a[i][j] = xorshift();
    
	x = Ba; y = Bb; z = Bc; w = Bd;     
	LL ans=0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			ww[i] *= p;
			ww[i] += xorshift();
			ww[i] %= mod;
		}
	}

	for (int i = 0; i < n; ++i)
	{
		LL v = qmi(p, n * (n - 1 - i));
		for (int j = 0; j < n; ++j)
		{
			LL ret = 1ll * a[i][j] * ww[j] % mod;
			ret = ret * v %mod;
			ans += ret ;
			ans %= mod ;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 641ms, 内存消耗: 616K, 提交时间: 2018-08-11 18:08:18

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=7000;
const int mod = 1000000007;
int A[maxn],B[maxn];
uint32_t x, y, z, w;
uint32_t xorshift()
{
    uint32_t t = x;
    t ^= t << 11;
    t ^= t >> 8;
    x = y; y = z; z = w;
    w ^= w >> 19;
    w ^= t;
    return w & ((1 << 24) - 1);
}
int add(int a,int b)
{
    return a+b>=mod?a+b-mod:a+b;
}
int mul(int a,int b)
{
    ll z=1ll*a*b;
    return z-z/mod*mod;
}
int Pow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}
int main()
{
    int n,p;
    uint32_t Aa,Ab,Ac,Ad,Ba,Bb,Bc,Bd;
    scanf("%d%u%u%u%u%u%u%u%u%d",&n,&Aa,&Ab,&Ac,&Ad,&Ba,&Bb,&Bc,&Bd,&p);
    x = Aa; y = Ab; z = Ac; w = Ad;
    int P=Pow(p,n*(n-1)),invp=Pow(Pow(p,n),mod-2);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            A[j]=add(A[j],mul(xorshift(),P));
        P=mul(P,invp);
    }
    x = Ba; y = Bb; z = Bc; w = Bd;
    P=Pow(p,n-1),invp=Pow(p,mod-2);
    for(int i=0;i<n;i++)
        {
            int PP=P;
            for(int j=0;j<n;j++)
            B[i]=add(B[i],mul(xorshift(),PP)),PP=mul(PP,invp);
        }
    int ans=0;
    for(int k=0;k<n;k++)ans=add(ans,mul(A[k],B[k]));
    printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 372ms, 内存消耗: 612K, 提交时间: 2018-10-08 12:52:35

#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned uint32_t;
const int maxn=7000;
uint32_t x,y,z,w;
uint32_t xorshift() 
{
    uint32_t t=x;
    t^=t<<11;
    t^=t>>8;
    x=y;y=z;z=w;
    w^=w>>19;
    w^=t;
    return w&((1<<24)-1);
}
#define mod 1000000007
int mul(int x,int y)
{
	ll z=1ll*x*y;
	return z-z/mod*mod;
}
int add(int x,int y)
{
	x+=y;
	if(x>=mod)x-=mod;
	return x;
}
uint32_t Aa,Ab,Ac,Ad,Ba,Bb,Bc,Bd,p;
int n,f[maxn],g[maxn],A[maxn],B[maxn];
int main()
{
	scanf("%d%u%u%u%u%u%u%u%u%u",&n,&Aa,&Ab,&Ac,&Ad,&Ba,&Bb,&Bc,&Bd,&p);
	p%=mod;
	f[0]=g[0]=1;
	for(int i=1;i<n;i++)f[i]=mul(f[i-1],p);
	p=mul(f[n-1],p);
	for(int i=1;i<n;i++)g[i]=mul(g[i-1],p);
	x=Aa,y=Ab,z=Ac,w=Ad;
	for(int i=0;i<n;i++)
		for(int k=0;k<n;k++)
			A[k]=add(A[k],mul(xorshift(),g[n-1-i]));
	x=Ba,y=Bb,z=Bc,w=Bd;
	for(int k=0;k<n;k++)
		for(int j=0;j<n;j++)
			B[k]=add(B[k],mul(xorshift(),f[n-1-j]));
	int ans=0;
	for(int k=0;k<n;k++)ans=add(ans,mul(A[k],B[k]));
	printf("%d\n",ans);
	return 0;
}