列表

详情

NC17693. Rikka with Rotate

描述

To improve Rikka's math, Yuta designs a simple game which requires a lot of calculating. The game has several steps:
1. At first, the terminal chooses n points with integer coordinates in the two-dimensional Cartesian coordinate system and an integer K. And then, the terminal shows them to Rikka.
2. Rikka needs to color the n points using K different colors. Different points may have the same color, and some colors may not be used.
3. Rikka needs to count the number of different colorings.

Two colorings c1,c2 are the same if and only if there are some point o(may have real value coordinates) and angle which satisfies if we rotate the n points in c1 degrees counterclockwise with the center o, the result will look exactly the same (including colors and positions) as c2.

For example, when the points are (1,0),(0,1) and K is 2, coloring c1=(1,2) and c2=(2,1) are the same, because if we rotate the points in c1 180 degrees counterclockwise with the center , the result will be exactly the same as c2. And in this case, there are 3 different colorings: (1,1),(1,2),(2,2).

After playing this game several times, Rikka finds that the terminal always chooses points from a fixed point set P. So there are exactly different games (all P's subsets except ).

Let f(S,K) be the answer of the game when the point set chosen by the terminal is S and the number of colors is K. Now, given P and K, Rikka wants to calculate .

输入描述

The first line contains one single integer t(1 ≤ t ≤ 3), the number of the testcases.

For each testcase, the first line contains two integers n,K(1 ≤ n ≤ 3000, 1 ≤ K ≤ 109).

Then n lines follow, each line contains two integers (xi,yi)(|xi|,|yi| ≤ 108), describe the points in P.

The input guarantees that no two points have the same coordinates, i.e., , (xi,yi) ≠ (xj,yj)

输出描述

For each testcase, output a single integer, the answer modulo 998244353.

示例1

输入: 

2
2 2
1 0
0 1
5 3
0 0
2 0
0 2
2 2
1 1

输出: 

7
747

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4540ms, 内存消耗: 223704K, 提交时间: 2018-08-19 21:11:37 

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
#include <map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int N=5100;
struct point{
	int x,y;
	void scan(){
		scanf("%d%d",&x,&y);
		x*=2; y*=2;
	}
	long long h(){
		return 1ll*x*1000000000+y;
	}
}A[N];
point operator + (const point &k1,const point &k2){return (point){k1.x+k2.x,k1.y+k2.y};}
point operator - (const point &k1,const point &k2){return (point){k1.x-k2.x,k1.y-k2.y};}
point operator / (const point &k1,int k2){return (point){k1.x/k2,k1.y/k2};}
int operator == (const point &k1,const point &k2){return k1.x==k2.x&&k1.y==k2.y;}
point norm(point k1){
	while (k1.x<=0||(k1.x>0&&k1.y<0)){
		swap(k1.x,k1.y); k1.x=-k1.x;
	}
	return k1;
}
const int Mo=1e7+19,key=10007,M=7000000,mo=998244353,inv2=(mo+1)/2,inv4=748683265;
int *fir,len,*ne,n,*pd,sign,c,*f,C[N];
pair<point,point>* w;
int I[N],nI[N];
int quick(int k1,int k2){
	int k3=1;
	while (k2){
		if (k2&1) k3=1ll*k3*k1%mo;
		k2>>=1; k1=1ll*k1*k1%mo;
	}
	return k3;
}
int getloc(pair<point,point> k1){
	int k=(k1.fi.h()%Mo*key+k1.se.h())%Mo;
	if (k<0) k+=Mo;
	if (pd[k]!=sign){
		pd[k]=sign; fir[k]=0;
	}
	for (int i=fir[k];i;i=ne[i])
		if (w[i]==k1) return i;
	len++; ne[len]=fir[k]; fir[k]=len; f[len]=0; w[len]=k1;
	return len;
}
void insert(point k1,point k2){
	int where=getloc(mp(k1,k2));
	f[where]+=2;
	if (f[where]==4){
		where=getloc(mp(k1,(point){0,0}));
		f[where]+=4;
	}
}
int ans;
int num[N][3];
int getw1(int size){
	return C[size];
}
int getw4(int size){
	//cout<<size<<" "<<2ll*C[size]<<" "<<C[(size>>1)+(size&1)]<<" "<<C[(size>>2)+(size&1)]<<endl;
	return (C[size]+C[(size>>1)+(size&1)]+2ll*C[(size>>2)+(size&1)])%mo*inv4%mo;
}
int getw2(int size){
	return (1ll*C[size]+C[(size>>1)+(size&1)])%mo*inv2%mo;
}
int CC(int k1,int k2){
	return 1ll*I[k1]*nI[k2]%mo*nI[k1-k2]%mo;
}
void calc4(int k1){
	int ans=0;
	for (int i=0;i<=(k1&1);i++)
		for (int j=0;j<=k1;j+=4)
			if (i+j>1){
				int way=CC(k1/4,j/4);
				num[i+j][2]=(num[i+j][2]+way)%mo;
				num[i+j][1]=(num[i+j][1]-way+mo)%mo;
			}
}
void calc2(int k1){
	for (int i=0;i<=(k1&1);i++)
		for (int j=0;j<=k1;j+=2)
			if (i+j>1){
				int way=CC(k1/2,j/2);
				num[i+j][1]=(num[i+j][1]+way)%mo;
				num[i+j][0]=(num[i+j][0]-way+mo)%mo;
			}
}
map<pair<int,int>,int>MM;
void solve(){
	scanf("%d%d",&n,&c); ans=0; C[0]=1;
	assert(1<=n&&n<=3000&&1<=c&&c<=1000000000);
	for (int i=1;i<=n;i++) C[i]=1ll*C[i-1]*c%mo;
	MM.clear();
	for (int i=1;i<=n;i++){
		A[i].scan(); assert(MM[make_pair(A[i].x,A[i].y)]==0);
		MM[make_pair(A[i].x,A[i].y)]=1;
	}
	len=0; sign++;
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++){
			assert(A[i].x!=A[j].x||A[i].y!=A[j].y);
			point o=(A[i]+A[j])/2;
			point del=A[i]-o;
		//	cout<<i<<" "<<j<<" "<<o.x<<" "<<o.y<<" "<<norm(del).x<<" "<<norm(del).y<<endl;
			insert(o,norm(del));
		}
	for (int i=1;i<=n;i++){
		int where=getloc(mp(A[i],(point){0,0})); f[where]++;
	}
	int ans=0;
	memset(num,0x00,sizeof num);
	for (int i=1;i<=n;i++) num[i][0]=CC(n,i);
	for (int i=1;i<=len;i++)
		if (w[i].se==(point){0,0}) calc4(f[i]);
	len=0; sign++;
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++){
			point o=(A[i]+A[j])/2;
			int where=getloc(mp(o,(point){0,0})); f[where]+=2;
		}
	for (int i=1;i<=n;i++){
		int where=getloc(mp(A[i],(point){0,0})); f[where]++;
	}
	for (int i=1;i<=len;i++) calc2(f[i]);
	/*for (int i=1;i<=n;i++){
		for (int j=0;j<3;j++) cout<<num[i][j]<<" "; cout<<endl;
	}*/
	for (int i=1;i<=n;i++)
		ans=(ans+1ll*getw1(i)*num[i][0]%mo+1ll*getw2(i)*num[i][1]%mo+1ll*getw4(i)*num[i][2])%mo;
	printf("%d\n",ans);
}
int main(){
	w=new pair<point,point>[M];
	fir=new int[Mo];
	ne=new int[M];
	pd=new int[Mo];
	f=new int[M];
	int t; scanf("%d",&t); assert(1<=t&&t<=3);
	I[0]=1;
	for (int i=1;i<=5000;i++) I[i]=1ll*I[i-1]*i%mo;
	for (int i=0;i<=5000;i++) nI[i]=quick(I[i],mo-2);
	for (;t;t--) solve();
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 2403ms, 内存消耗: 163360K, 提交时间: 2018-08-21 23:28:45 

#include<bits/stdc++.h>

typedef long long ll;
const int moder = 998244353;
const int inv2 = (moder + 1) >> 1;
const int inv4 = 1ll * inv2 * inv2 % moder;
const int N = 3010;

int powermod(int a, int exp){
    int ret = 1;
    for ( ; exp > 0; exp >>= 1){
        if (exp & 1){
            ret = 1ll * ret * a % moder;
        }
        a = 1ll * a * a % moder;
    }
    return ret;
}

ll Hash(int x, int y){
    return 500000000ll * x + y;
}

const int MOD = (int) 1e7 + 1563;

int first[MOD], next[N * N];
int valuex[N * N], valuey[N * N];
int u[N * N], v[N * N];
int hcnt;

void insert(int x, int y){
    int sit = (x * 500000000 + y) % MOD;
    sit += sit < 0 ? MOD : 0;
    next[hcnt] = first[sit];
    first[sit] = hcnt;
    valuex[hcnt] = x;
    valuey[hcnt] = y;
    ++ hcnt;
}

int get(int x, int y){
    int sit = (x * 500000000 + y) % MOD;
    sit += sit < 0 ? MOD : 0;
    for (int u = first[sit]; u != -1; u = next[u]){
        if (valuex[u] == x && valuey[u] == y){
            return u;
        }
    }
    return -1;
}

int x[N], y[N];
int power[6][N];

int calc(int coe, int n){
    int ret = power[coe][n] - 1;
    ret += ret < 0 ? moder : 0;
    return ret;
}

int calc2(int coe, int n){
    int ret = (power[coe << 1][n] - 1 + power[coe][n] - 1) % moder;
    ret += ret < 0 ? moder : 0;
    return 1ll * ret * inv2 % moder;
}

int calc4(int coe, int n){
    int ret = (power[coe << 2][n] - 1 + power[coe << 1][n] - 1 + 2ll * (power[coe][n] - 1)) % moder;
    ret += ret < 0 ? moder : 0;
    return 1ll * ret * inv4 % moder;
}

void add(int &a, int b){
    a += b;
    a -= a >= moder ? moder : 0;
}

void minus(int &a, int b){
    a -= b;
    a += a < 0 ? moder : 0;
}

void solve(){
    memset(u, 0, sizeof(u));
    memset(v, 0, sizeof(v));
    memset(first, -1, sizeof(first));
    hcnt = 0;
    std::unordered_map <ll, int> Hash1;
    int n, k;
    scanf("%d%d", &n, &k);
    k %= moder;
    for (int i = 0; i < 6; ++ i){
        power[i][0] = 1;
        power[i][1] = (powermod(k, i) + 1) % moder;
        for (int j = 2; j < N; ++ j){
            power[i][j] = 1ll * power[i][j - 1] * power[i][1] % moder;
        }
    }
    for (int i = 0; i < n; ++ i){
        scanf("%d%d", &x[i], &y[i]);
        x[i] <<= 1;
        y[i] <<= 1;
        Hash1[Hash(x[i], y[i])] = 1;
    }
    for (int i = 0; i < n; ++ i){
        for (int j = i + 1; j < n; ++ j){
            int midx = (x[i] + x[j]) >> 1, midy = (y[i] + y[j]) >> 1;
            int sit = get(midx, midy);
            if (sit == -1){
                insert(midx, midy);
                sit = hcnt - 1;
            }
            ++ u[sit];
            if (Hash1.count(Hash(midx + y[j] - midy, midy - x[j] + midx)) && Hash1.count(Hash(midx - y[j] + midy, midy + x[j] - midx))){
                ++ v[sit];
            }
        }
    }
    int ans = calc(1, n);
    for (int i = 0; i < hcnt; ++ i){
        int two = u[i], four = v[i] >> 1;
        add(ans, calc4(1, four));
        minus(ans, calc2(2, four));
        add(ans, calc2(1, two));
        minus(ans, calc(2, two));
        if (Hash1.count(Hash(valuex[i], valuey[i]))){
            add(ans, 1ll * calc4(1, four) * k % moder);
            minus(ans, 1ll * calc2(2, four) * k % moder);
            add(ans, 1ll * calc2(1, two) * k % moder);
            minus(ans, 1ll * calc(2, two) * k % moder);
        }
    }
    ans %= moder;
    printf("%d\n", ans);
}

int main(){
    /*for (int i = 1001000; i < 1002000; ++ i){
        bool flag = true;
        for (int j = 2; j * j <= i; ++ j){
            if (i % j == 0){
                flag = false;
                break;
            }
        }
        if (flag){
            printf("%d\n", i);
        }
    }*/
    int test;
    scanf("%d", &test);
    while (test --){
        solve();
    }
    return 0;
}

上一题

© 2025 nowcoder.com