QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#351690#8340. 3 SumLynkcatWA 412ms78912kbC++202.0kb2024-03-12 11:33:142024-03-12 11:33:14

Judging History

你现在查看的是最新测评结果

  • [2024-09-20 10:20:30]
  • hack成功,自动添加数据
  • (/hack/848)
  • [2024-03-18 21:48:05]
  • hack成功,自动添加数据
  • (/hack/579)
  • [2024-03-18 21:45:33]
  • hack成功,自动添加数据
  • (/hack/578)
  • [2024-03-12 11:33:14]
  • 评测
  • 测评结果:WA
  • 用时:412ms
  • 内存:78912kb
  • [2024-03-12 11:33:14]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define sz(x) ((int)((x).size()))
// #define int ll
// #define N 
using namespace std;
const int N=505;
const int mod[3]={998244353,1000000007,19260817};
poly a[N];
int n,m;
poly val[N];
poly md[3];
void BellaKira()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		string st;
		cin>>st;
		reverse(st.begin(),st.end());
		a[i].resize(m);
		for (int j=0;j<sz(st);j++)
		{
			int o=j%m;
			a[i][o]+=st[j]-'0';
		}
		// for (auto u:a[i]) cout<<u<<",";
		// cout<<endl;
		while (1)
		{
			bool bl=0,bl1=1;
			for (int j=0;j<m;j++)
				if (a[i][j]>9)
				{
					int t=a[i][j]/10;
					a[i][j]%=10;
					a[i][(j+1)%m]+=t;
					bl=1;
				}
			for (int j=0;j<m;j++)
				bl1&=(a[i][j]==9);
			if (bl1)
			{
				for (int j=0;j<m;j++) a[i][j]=0;
				a[i][0]=0;
			}
			if (!bl) break;
		}
		reverse(a[i].begin(),a[i].end());
		// for (auto u:a[i]) cout<<u<<",";
		// cout<<endl;
	}
	for (int i=0;i<3;i++) md[i]=poly(3,0);
	for (int i=1;i<=n;i++) val[i]=poly(3,0);
	for (int j=0;j<3;j++)
	{
		int op=1;
		for (int i=1;i<=m;i++) op=op*10%mod[j];
		op=(op+mod[j]-1)%mod[j];
		for (int i=0;i<3;i++)
			md[i][j]=op*i%mod[j];
		for (int i=1;i<=n;i++)
		{
			val[i][j]=0;
			for (auto u:a[i])
				val[i][j]=(val[i][j]*10+u)%mod[j];
		}
	}
	map<poly,int>F;
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		F[val[i]]++;
		for (int j=i;j<=n;j++)
			for (int k=0;k<3;k++)
				if (!k||md[k]!=md[k-1])
				{
					poly now=md[k];
					for (int x=0;x<3;x++)
						now[x]=(now[x]-val[i][x]-val[j][x]+mod[x]+mod[x])%mod[x];
					ans=(ans+F[now]);
				}
	}
	cout<<ans<<'\n';
					




}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3824kb

input:

4 1
0
1
10
17

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 258ms
memory: 46472kb

input:

500 859
7118711592236878297922359501613604144948355616986970837340677671376753603836852811886591300370143151943368529129749813118476151865844255212534355441611481420938483178075143062691345257288242460282715389758789648541099090735875617822348551942134616963557723055980260082230902505269975518146286...

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 412ms
memory: 78912kb

input:

500 17336
11871159223687829792235950161360414494835561698697083734067767137675360383685281188659130037014315194336852912974981311847615186584425521253435544161148142093848317807514306269134525728824246028271538975878964854109909073587561782234855194213461696355772305598026008223090250526997551814628...

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 41ms
memory: 3704kb

input:

500 1
751324443898124078584847834484321089092662321556147445230263526014359393841194947303407593948729802551881289193716611867931891257925091769456350249725997883453296895094445731130479434019358742162771547784250401546380268386074363779242500860317042151185119666027858022664683818314351285215150806...

output:

2327631

result:

ok 1 number(s): "2327631"

Test #5:

score: 0
Accepted
time: 46ms
memory: 3984kb

input:

500 2
408542968136435277974575411503179002415404345446801430469044749372949272333801248935236224652806667129749035002588943020176263162139056819871274824302889304493205266143688886696157147111754418731401856424401766968832165255416237731963027205324149660112574729610391396555581935236134531799950318...

output:

212002

result:

ok 1 number(s): "212002"

Test #6:

score: -100
Wrong Answer
time: 342ms
memory: 58200kb

input:

500 11500
75411775796562109942642493394321873284995260953010112281856775261847503626737348402159485133662757032091519863427156582689971229143089317472838196453888261138079171290535429921921548971897026706656838415620603757605079012541561774699628665865662183868374645956694140356716037674688084770628...

output:

1

result:

wrong answer 1st numbers differ - expected: '7675', found: '1'